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();
- See Also:
- "Algorithms for Estimating Relative Importance in Graphs by Scott White and Padhraic Smyth, 2003"
-
-
Field Summary
Fields Modifier and Type Field Description static java.lang.String
WEIGHTED_NIPATHS_KEY
-
Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
edgeRankScores, vertexRankScores
-
-
Constructor Summary
Constructors Constructor Description WeightedNIPaths(edu.uci.ics.jung.graph.DirectedGraph<V,E> graph, org.apache.commons.collections4.Factory<V> vertexFactory, org.apache.commons.collections4.Factory<E> edgeFactory, double alpha, int maxDepth, java.util.Set<V> priors)
Constructs and initializes the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description protected void
computeWeightedPathsFromSource(V root, int depth)
java.lang.String
getRankScoreKey()
Given a node, returns the corresponding rank score.protected void
incrementRankScore(V v, double rankValue)
protected void
onFinalize(java.lang.Object udc)
void
step()
Evaluate the result of the current iteration.-
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
-
-
-
-
Field Detail
-
WEIGHTED_NIPATHS_KEY
public static final java.lang.String WEIGHTED_NIPATHS_KEY
- See Also:
- Constant Field Values
-
-
Constructor Detail
-
WeightedNIPaths
public WeightedNIPaths(edu.uci.ics.jung.graph.DirectedGraph<V,E> graph, org.apache.commons.collections4.Factory<V> vertexFactory, org.apache.commons.collections4.Factory<E> edgeFactory, double alpha, int maxDepth, java.util.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)
-
-
Method Detail
-
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 interfaceIterativeContext
- Specified by:
step
in classIterativeProcess
-
getRankScoreKey
public java.lang.String getRankScoreKey()
Given a node, returns the corresponding rank score. This implementation ofgetRankScore
assumes the decoration representing the rank score is of typeMutableDouble
.- Specified by:
getRankScoreKey
in classAbstractRanker<V,E>
- Returns:
- the rank score for this node
-
onFinalize
protected void onFinalize(java.lang.Object udc)
- Overrides:
onFinalize
in classAbstractRanker<V,E>
-
-