Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## edu.uci.ics.jung.algorithms.importance
Class WeightedNIPaths

    java.lang.Object
      edu.uci.ics.jung.algorithms.IterativeProcess
          edu.uci.ics.jung.algorithms.importance.AbstractRanker
              edu.uci.ics.jung.algorithms.importance.WeightedNIPaths

public class WeightedNIPaths
extends AbstractRanker

This algorithm measures the importance of nodes based upon both the number and length of disjoint paths that lead to a given node from each of the nodes in the root set. Specifically the formula for measuring the importance of a node is given by: I(t|R) = sum_i=1_|P(r,t)|_{alpha^|p_i|} where alpha is the path decay coefficient, p_i is path i and P(r,t) is a set of maximum-sized node-disjoint paths from r to t.

This algorithm uses heuristic breadth-first search to try and find the maximum-sized set of node-disjoint paths between two nodes. As such, it is not guaranteed to give exact answers.

A simple example of usage is:

     WeightedNIPaths ranker = new WeightedNIPaths(someGraph,2.0,6,rootSet);
     ranker.evaluate();
     ranker.printRankings();

Author:
  Scott White
See Also:
  "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"

Field Summary
`static String` | `WEIGHTED_NIPATHS_KEY`

Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
`DEFAULT_EDGE_WEIGHT_KEY`

Constructor Summary
`WeightedNIPaths(DirectedGraph graph, double alpha, int maxDepth, Set priors)` Constructs and initializes the algorithm.

Method Summary
`protected void` | `computeWeightedPathsFromSource(Vertex root, int depth)`
`protected double` | `evaluateIteration()` Evaluate the result of the current interation.
`String` | `getRankScoreKey()` Given a node, returns the corresponding rank score.
`protected void` | `incrementRankScore(Element v, double rankValue)`
`protected void` | `onFinalize(Element udc)`

Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
`assignDefaultEdgeTransitionWeights, finalizeIterations, getEdgeWeight, getEdgeWeightKeyName, getGraph, getRankings, getRankScore, getRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, printRankings, reinitialize, setEdgeWeight, setNormalizeRankings, setRankScore, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey`

Methods inherited from class edu.uci.ics.jung.algorithms.IterativeProcess
`evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations`

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### WEIGHTED_NIPATHS_KEY

    public static final String WEIGHTED_NIPATHS_KEY

See Also:
  Constant Field Values

Constructor Detail

### WeightedNIPaths

    public WeightedNIPaths(DirectedGraph graph,
                           double alpha,
                           int maxDepth,
                           Set priors)

  Constructs and initializes the algorithm.

Parameters:
  `graph` - the graph whose nodes are being measured for their importance
  `alpha` - the path decay coefficient (>= 1); 2 is recommended
  `maxDepth` - the maximal depth to search out from the root set
  `priors` - the root set (starting vertices)

Method Detail

### getRankScoreKey

    public String getRankScoreKey()

  Given a node, returns the corresponding rank score. This implementation of `getRankScore` assumes the decoration representing the rank score is of type `MutableDouble`.

  Specified by:
    `getRankScoreKey` in class `AbstractRanker`
  Returns:
    the rank score for this node

### incrementRankScore

    protected void incrementRankScore(Element v,
                                      double rankValue)

### computeWeightedPathsFromSource

    protected void computeWeightedPathsFromSource(Vertex root,
                                                  int depth)

### evaluateIteration

    protected double evaluateIteration()

  Description copied from class: `IterativeProcess`
  Evaluate the result of the current interation.

  Specified by:
    `evaluateIteration` in class `IterativeProcess`
  Returns:
    the estimated precision of the result.

### onFinalize

    protected void onFinalize(Element udc)

  Overrides:
    `onFinalize` in class `AbstractRanker`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD