edu.uci.ics.jung.algorithms.importance
Class WeightedNIPaths<V,E>
java.lang.Object
edu.uci.ics.jung.algorithms.util.IterativeProcess
edu.uci.ics.jung.algorithms.importance.AbstractRanker<V,E>
edu.uci.ics.jung.algorithms.importance.WeightedNIPaths<V,E>
- All Implemented Interfaces:
- IterativeContext
public class WeightedNIPaths<V,E>
- extends AbstractRanker<V,E>
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"
Constructor Summary |
WeightedNIPaths(DirectedGraph<V,E> graph,
org.apache.commons.collections15.Factory<V> vertexFactory,
org.apache.commons.collections15.Factory<E> edgeFactory,
double alpha,
int maxDepth,
Set<V> priors)
Constructs and initializes the algorithm. |
Methods inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker |
assignDefaultEdgeTransitionWeights, finalizeIterations, getEdgeRankScore, getEdgeRankScore, getEdgeRankScores, getEdgeRankScores, getEdgeWeight, getEdgeWeights, getGraph, getRankings, getRankScores, getVertexCount, getVertexRankScore, getVertexRankScore, getVertexRankScores, getVertexRankScores, getVertices, initialize, isRankingEdges, isRankingNodes, normalizeEdgeTransitionWeights, normalizeRankings, printRankings, removeEdgeRankScore, removeEdgeRankScore, removeVertexRankScore, removeVertexRankScore, reset, setEdgeRankScore, setEdgeRankScore, setEdgeWeight, setEdgeWeights, setNormalizeRankings, setRemoveRankScoresOnFinalize, setVertexRankScore, setVertexRankScore |
Methods inherited from class edu.uci.ics.jung.algorithms.util.IterativeProcess |
done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations, setPrecision |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
WEIGHTED_NIPATHS_KEY
public static final String WEIGHTED_NIPATHS_KEY
- See Also:
- Constant Field Values
WeightedNIPaths
public WeightedNIPaths(DirectedGraph<V,E> graph,
org.apache.commons.collections15.Factory<V> vertexFactory,
org.apache.commons.collections15.Factory<E> edgeFactory,
double alpha,
int maxDepth,
Set<V> priors)
- Constructs and initializes the algorithm.
- Parameters:
graph
- the graph whose nodes are being measured for their importancealpha
- the path decay coefficient (>= 1); 2 is recommendedmaxDepth
- the maximal depth to search out from the root setpriors
- the root set (starting vertices)
incrementRankScore
protected void incrementRankScore(V v,
double rankValue)
computeWeightedPathsFromSource
protected void computeWeightedPathsFromSource(V root,
int depth)
step
public void step()
- Description copied from class:
IterativeProcess
- Evaluate the result of the current iteration.
- Specified by:
step
in interface IterativeContext
- Specified by:
step
in class IterativeProcess
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<V,E>
- Returns:
- the rank score for this node
onFinalize
protected void onFinalize(Object udc)
- Overrides:
onFinalize
in class AbstractRanker<V,E>
Copyright © 2009. All Rights Reserved.