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

java.lang.Object
  edu.uci.ics.jung.algorithms.IterativeProcess
      edu.uci.ics.jung.algorithms.importance.AbstractRanker
          edu.uci.ics.jung.algorithms.importance.RandomWalkSTBetweenness
              edu.uci.ics.jung.algorithms.importance.RandomWalkBetweenness

public class RandomWalkBetweenness

extends RandomWalkSTBetweenness

Computes 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 averaged over all pairs of nodes. The result is that each vertex has a UserData element of type MutableDouble whose key is 'centrality.RandomWalkBetweennessCentrality' A simple example of usage is:
RandomWalkBetweenness ranker = new RandomWalkBetweenness(someGraph);
ranker.evaluate();
ranker.printRankings();

Running time is: O((m+n)*n^2).

Author:

Scott White

See Also:

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

Field Summary

static java.lang.String

CENTRALITY

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

DEFAULT_EDGE_WEIGHT_KEY

Constructor Summary

RandomWalkBetweenness(UndirectedGraph g)
Constructor which initializes the algorithm

Method Summary

java.lang.String

getRankScoreKey() the user datum key used to store the rank scores

Methods inherited from class edu.uci.ics.jung.algorithms.importance.RandomWalkSTBetweenness

computeSTBetweenness

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

getEdgeWeightKeyName, getRankings, getRankScore, getRankScores, isRankingNodes, printRankings, setNormalizeRankings, setRemoveRankScoresOnFinalize, setUserDefinedEdgeWeightKey

Methods inherited from class edu.uci.ics.jung.algorithms.IterativeProcess

evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, relativePrecision, setDesiredPrecision, setMaximumIterations

Methods inherited from class java.lang.Object

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

RandomWalkBetweenness

public RandomWalkBetweenness(UndirectedGraph g)

Constructor which initializes the algorithm

Parameters:

g - the graph whose nodes are to be analyzed

Method Detail

getRankScoreKey

public java.lang.String getRankScoreKey()

the user datum key used to store the rank scores

Overrides:

getRankScoreKey in class RandomWalkSTBetweenness

Returns:

the key