edu.uci.ics.jung.algorithms.importance
Class RandomWalkBetweenness<V,E>

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.util.IterativeProcess
      extended by edu.uci.ics.jung.algorithms.importance.AbstractRanker<V,E>
          extended by edu.uci.ics.jung.algorithms.importance.RandomWalkSTBetweenness<V,E>
              extended by edu.uci.ics.jung.algorithms.importance.RandomWalkBetweenness<V,E>
All Implemented Interfaces:
IterativeContext

public class RandomWalkBetweenness<V,E>
extends RandomWalkSTBetweenness<V,E>

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 String CENTRALITY
           
 
Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
edgeRankScores, vertexRankScores
 
Constructor Summary
RandomWalkBetweenness(UndirectedGraph<V,E> g)
          Constructor which initializes the algorithm
 
Method Summary
protected  void computeBetweenness()
           
protected  double evaluateIteration()
           
 String getRankScoreKey()
          the user datum key used to store the rank scores
 
Methods inherited from class edu.uci.ics.jung.algorithms.importance.RandomWalkSTBetweenness
computeSTBetweenness, getIndexer, getVoltageMatrix, setUp, step
 
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, onFinalize, 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
 
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

RandomWalkBetweenness

public RandomWalkBetweenness(UndirectedGraph<V,E> g)
Constructor which initializes the algorithm

Parameters:
g - the graph whose nodes are to be analyzed
Method Detail

computeBetweenness

protected void computeBetweenness()
Overrides:
computeBetweenness in class RandomWalkSTBetweenness<V,E>

getRankScoreKey

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

Overrides:
getRankScoreKey in class RandomWalkSTBetweenness<V,E>
Returns:
the key

evaluateIteration

protected double evaluateIteration()


Copyright © 2009. All Rights Reserved.