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
private com.google.common.base.Supplier<E>	edgeFactory
private double	mAlpha
private int	mMaxDepth
private Set<V>	mPriors
private Map<E,Number>	pathIndices
private Map<V, Set<Number>>	pathsSeenMap
private Map<Object,V>	roots
private com.google.common.base.Supplier<V>	vertexFactory
static final String	WEIGHTED_NIPATHS_KEY

Fields inherited from class AbstractRanker

edgeRankScores, vertexRankScores

Constructor Summary

Constructors

Constructor	Description
WeightedNIPaths(DirectedGraph<V,E> graph, com.google.common.base.Supplier<V> vertexFactory, com.google.common.base.Supplier<E> edgeFactory, double alpha, int maxDepth, Set<V> priors)	Constructs and initializes the algorithm.

Method Summary

Modifier and Type	Method	Description
protected void	computeWeightedPathsFromSource(V root, int depth)
String	getRankScoreKey()	Given a node, returns the corresponding rank score.
protected void	incrementRankScore(V v, double rankValue)
private void	newVertexEncountered(int sourcePathIndex, V dest, V root)
protected void	onFinalize(Object udc)
void	step()	Evaluate the result of the current iteration.

Methods inherited from class 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 IterativeProcess

done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations, setPrecision

Methods inherited from class Object

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

Field Details

WEIGHTED_NIPATHS_KEY

public static final String WEIGHTED_NIPATHS_KEY

See Also:

• Constant Field Values

mAlpha

private double mAlpha

mMaxDepth

private int mMaxDepth

mPriors

private Set<V> mPriors

pathIndices

private Map<E,Number> pathIndices

roots

private Map<Object,V> roots

pathsSeenMap

private Map<V, Set<Number>> pathsSeenMap

vertexFactory

private com.google.common.base.Supplier<V> vertexFactory

edgeFactory

private com.google.common.base.Supplier<E> edgeFactory

Constructor Details

WeightedNIPaths

public WeightedNIPaths(DirectedGraph<V,E> graph,
 com.google.common.base.Supplier<V> vertexFactory,
 com.google.common.base.Supplier<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 importance

vertexFactory - used to generate instances of V

edgeFactory - used to generate instances of E

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 Details

incrementRankScore

protected void incrementRankScore(V v,
 double rankValue)

computeWeightedPathsFromSource

protected void computeWeightedPathsFromSource(V root,
 int depth)

newVertexEncountered

private void newVertexEncountered(int sourcePathIndex,
 V dest,
 V root)

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>