## Class 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 Description
BetweennessCentrality​(Graph<V,​E> graph)
Construct a new instance.
BetweennessCentrality​(Graph<V,​E> graph, boolean normalize)
Construct a new instance.
• ### Method Summary

All Methods
Modifier and Type Method 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,​E>
Returns:
a map with all scores
• #### getVertexScore

public Double getVertexScore​(V v)
Get a vertex score
Specified by:
getVertexScore in interface VertexScoringAlgorithm<V,​E>
Parameters:
v - the vertex
Returns:
the score