## 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 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