scratch.scott
Class NewmanBetweennessCentrality

java.lang.Object
  extended by edu.uci.ics.jung.algorithms.IterativeProcess
      extended by edu.uci.ics.jung.algorithms.importance.AbstractRanker
          extended by scratch.scott.NewmanBetweennessCentrality

public class NewmanBetweennessCentrality
extends AbstractRanker

Computes betweenness centrality for each vertex and edge in the graph. The result is that each vertex and edge has a UserData element of type MutableDouble whose key is "centrality.BetweennessCentrality." Note: Many social network researchers like to normalize the betweenness values by dividing the values by (n-1)(n-2)/2. The values given here are unnormalized.

A simple example of usage is:

 BetweennessCentrality ranker = new BetweennessCentrality(someGraph,true);
 ranker.evaluate();
 ranker.printRankings();
 
Running time is: O(mn)

Author:
Scott White
See Also:
"Mark Newman: Who is the best connected scientist? A study of scientific coauthorship networks. Physics Review, E64, 2001."

Field Summary
static String CENTRALITY
           
 
Fields inherited from class edu.uci.ics.jung.algorithms.importance.AbstractRanker
DEFAULT_EDGE_WEIGHT_KEY
 
Constructor Summary
NewmanBetweennessCentrality(Graph g, boolean rankNodes, boolean rankEdges)
          Constructor which initializes the algorithm
 
Method Summary
protected  void computeBetweenness(Graph graph)
           
protected  double evaluateIteration()
          Evaluate the result of the current interation.
 String getRankScoreKey()
          The user datum key used to store the rank scores.
 
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

NewmanBetweennessCentrality

public NewmanBetweennessCentrality(Graph g,
                                   boolean rankNodes,
                                   boolean rankEdges)
Constructor which initializes the algorithm

Parameters:
g - graph whose nodes are to be analysed
rankNodes - if true, computes node betweenness centrality; if false, computed edge betweenness centrality
Method Detail

computeBetweenness

protected void computeBetweenness(Graph graph)

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.