Class BetweennessCentrality<V,E>

java.lang.Object

edu.uci.ics.jung.algorithms.util.IterativeProcess

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

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

All Implemented Interfaces:

IterativeContext

public class BetweennessCentrality<V,E>
extends AbstractRanker<V,E>

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);
ranker.evaluate();
ranker.printRankings();

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

See Also:

• "Ulrik Brandes: A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25(2):163-177, 2001."

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
(package private) class	BetweennessCentrality.BetweennessData

Field Summary

Fields

Modifier and Type	Field	Description
static final String	CENTRALITY

Fields inherited from class AbstractRanker

edgeRankScores, vertexRankScores

Constructor Summary

Constructors

Constructor	Description
BetweennessCentrality(Graph<V,E> g)	Constructor which initializes the algorithm
BetweennessCentrality(Graph<V,E> g, boolean rankNodes)
BetweennessCentrality(Graph<V,E> g, boolean rankNodes, boolean rankEdges)

Method Summary

Modifier and Type	Method	Description
protected void	computeBetweenness(Graph<V,E> graph)
String	getRankScoreKey()	the user datum key used to store the rank scores
private void	initializeData(Graph<V,E> g, Map<V, BetweennessCentrality<V,E>.BetweennessData> decorator)
void	step()	Evaluate the result of the current iteration.

Methods inherited from class 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 IterativeProcess

done, evaluate, getDesiredPrecision, getIterations, getMaximumIterations, getPrecision, hasConverged, initializeIterations, relativePrecision, setDesiredPrecision, setMaximumIterations, setPrecision

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

CENTRALITY

public static final String CENTRALITY

See Also:

• Constant Field Values

Constructor Details

BetweennessCentrality

public BetweennessCentrality(Graph<V,E> g)

Constructor which initializes the algorithm

Parameters:

g - the graph whose nodes are to be analyzed

BetweennessCentrality

public BetweennessCentrality(Graph<V,E> g,
 boolean rankNodes)

BetweennessCentrality

public BetweennessCentrality(Graph<V,E> g,
 boolean rankNodes,
 boolean rankEdges)

Method Details

computeBetweenness

protected void computeBetweenness(Graph<V,E> graph)

initializeData

private void initializeData(Graph<V,E> g,
 Map<V, BetweennessCentrality<V,E>.BetweennessData> decorator)

getRankScoreKey

public String getRankScoreKey()

the user datum key used to store the rank scores

Specified by:

getRankScoreKey in class AbstractRanker<V,E>

Returns:

the key

step

public void step()

Description copied from class: IterativeProcess

Evaluate the result of the current iteration.

Specified by:

step in interface IterativeContext

Specified by:

step in class IterativeProcess