scratch.scott

Class NewmanBetweennessCentrality

java.lang.Object

edu.uci.ics.jung.algorithms.IterativeProcess

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

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

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
NewmanBetweennessCentrality(Graph g, boolean rankNodes, boolean rankEdges) Constructor which initializes the algorithm

Method Summary

Methods

Modifier and Type	Method and Description
protected void	computeBetweenness(Graph graph)
protected double	evaluateIteration() Evaluate the result of the current interation.
java.lang.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 java.lang.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 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.