org.jgrapht.alg.scoring

Class BetweennessCentrality<V,E>

java.lang.Object

org.jgrapht.alg.scoring.BetweennessCentrality<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

VertexScoringAlgorithm<V,Double>

public class BetweennessCentrality<V,E>
extends Object
implements VertexScoringAlgorithm<V,Double>

Betweenness centrality.

Computes the betweenness centrality of each vertex of a graph. The betweenness centrality of a node $v$ is given by the expression: $g(v)= \sum_{s \neq v \neq t}\frac{\sigma_{st}(v)}{\sigma_{st}}$ where $\sigma_{st}$ is the total number of shortest paths from node $s$ to node $t$ and $\sigma_{st}(v)$ is the number of those paths that pass through $v$. For more details see wikipedia. The algorithm is based on

• Brandes, Ulrik (2001). "A faster algorithm for betweenness centrality". Journal of Mathematical Sociology. 25 (2): 163–177.

The running time is $O(nm) and $O(nm +n^2 \log n)$ for unweighted and weighted graph respectively, where $n$ is the number of vertices and $m$ the number of edges of the graph. The space complexity is $O(n + m)$.

Author:

Assaf Mizrachi

Constructor Summary

Constructors

Constructor and Description
BetweennessCentrality(Graph<V,E> graph) Construct a new instance.
BetweennessCentrality(Graph<V,E> graph, boolean normalize) Construct a new instance.

Method Summary

Modifier and Type	Method and Description
Map<V,Double>	getScores() Get a map with the scores of all vertices
Double	getVertexScore(V v) Get a vertex score

Methods inherited from class java.lang.Object

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

Constructor Detail

BetweennessCentrality

public BetweennessCentrality(Graph<V,E> graph)

Construct a new instance.

Parameters:

graph - the input graph

BetweennessCentrality

public BetweennessCentrality(Graph<V,E> graph,
                             boolean normalize)

Construct a new instance.

Parameters:

graph - the input graph

normalize - whether to normalize by dividing the closeness by $(n-1) \cdot (n-2)$, where $n$ is the number of vertices of the graph

Method Detail

getScores

public Map<V,Double> getScores()

Get a map with the scores of all vertices

Specified by:

getScores in interface VertexScoringAlgorithm<V,Double>

Returns:

a map with all scores

getVertexScore

public Double getVertexScore(V v)

Get a vertex score

Specified by:

getVertexScore in interface VertexScoringAlgorithm<V,Double>

Parameters:

v - the vertex

Returns:

the score