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 java.lang.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, java.util.Set priors)
Constructs and initializes the algorithm.

Method Summary

java.lang.String

getRankScoreKey() Given a node, returns the corresponding rank score.

Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker

getEdgeWeightKeyName, getRankings, getRankScore, getRankScores, isRankingNodes, printRankings, setNormalizeRankings, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey

Methods inherited from class edu.uci.ics.jung.algorithms.IterativeProcess

evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, setDesiredPrecision, setMaximumIterations

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

WEIGHTED_NIPATHS_KEY

public static final java.lang.String WEIGHTED_NIPATHS_KEY

See Also:

Constant Field Values

Constructor Detail

WeightedNIPaths

public WeightedNIPaths(DirectedGraph graph,
                       double alpha,
                       int maxDepth,
                       java.util.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 java.lang.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