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

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.IterativeProcess
      extended by edu.uci.ics.jung.algorithms.importance.AbstractRanker
          extended by 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