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

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.IterativeProcess
      extended by edu.uci.ics.jung.algorithms.importance.AbstractRanker
          extended by 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
static String CENTRALITY
           
 
Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
DEFAULT_EDGE_WEIGHT_KEY
 
Constructor Summary
RandomWalkSTBetweenness(UndirectedGraph g, Vertex s, Vertex t)
          Constructor which initializes the algorithm
 
Method Summary
protected  void computeBetweenness()
           
 double computeSTBetweenness(Vertex ithVertex, Vertex source, Vertex target)
           
protected  double evaluateIteration()
          Evaluate the result of the current interation.
protected  Indexer getIndexer()
           
 String getRankScoreKey()
          the user datum key used to store the rank scores
protected  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 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 DoubleMatrix2D getVoltageMatrix()

setUp

protected void setUp()

computeBetweenness

protected void computeBetweenness()

computeSTBetweenness

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

getRankScoreKey

public 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.