edu.uci.ics.jung.algorithms.importance

Class RandomWalkSTBetweenness

java.lang.Object

edu.uci.ics.jung.algorithms.IterativeProcess

edu.uci.ics.jung.algorithms.importance.AbstractRanker

edu.uci.ics.jung.algorithms.importance.RandomWalkSTBetweenness

Direct Known Subclasses:

RandomWalkBetweenness

public class RandomWalkSTBetweenness
extends AbstractRanker

/** Computes s-t betweenness centrality for each vertex in the graph. The betweenness values in this case are based on random walks, measuring the expected number of times a node is traversed by a random walk from s to t. The result is that each vertex has a UserData element of type MutableDouble whose key is 'centrality.RandomWalkBetweennessCentrality' A simple example of usage is:
RandomWalkSTBetweenness ranker = new RandomWalkBetweenness(someGraph,someSource,someTarget);
ranker.evaluate();
ranker.printRankings();

Running time is: O(n^3).

Author:

Scott White

See Also:

"Mark Newman: A measure of betweenness centrality based on random walks, 2002."

Field Summary

Fields

Modifier and Type	Field and Description
static java.lang.String	CENTRALITY

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

DEFAULT_EDGE_WEIGHT_KEY

Constructor Summary

Constructors

Constructor and Description
RandomWalkSTBetweenness(UndirectedGraph g, Vertex s, Vertex t) Constructor which initializes the algorithm

Method Summary

Methods

Modifier and Type	Method and Description
protected void	computeBetweenness()
double	computeSTBetweenness(Vertex ithVertex, Vertex source, Vertex target)
protected double	evaluateIteration() Evaluate the result of the current interation.
protected Indexer	getIndexer()
java.lang.String	getRankScoreKey() the user datum key used to store the rank scores
protected cern.colt.matrix.DoubleMatrix2D	getVoltageMatrix()
protected void	setUp()

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, onFinalize, 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

CENTRALITY

public static final java.lang.String CENTRALITY

See Also:

Constant Field Values

Constructor Detail

RandomWalkSTBetweenness

public RandomWalkSTBetweenness(UndirectedGraph g,
                       Vertex s,
                       Vertex t)

Constructor which initializes the algorithm

Parameters:

g - the graph whose nodes are to be analyzed

s - the source vertex

t - the target vertex

Method Detail

getIndexer

protected Indexer getIndexer()

getVoltageMatrix

protected cern.colt.matrix.DoubleMatrix2D getVoltageMatrix()

setUp

protected void setUp()

computeBetweenness

protected void computeBetweenness()

computeSTBetweenness

public double computeSTBetweenness(Vertex ithVertex,
                          Vertex source,
                          Vertex target)

getRankScoreKey

public java.lang.String getRankScoreKey()

the user datum key used to store the rank scores

Specified by:

getRankScoreKey in class AbstractRanker

Returns:

the key

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.