Betweeness Centrality
The betweenness centrality is a measure of centrality in a graph based on shortest paths. It provide useful information in any kind of situation where a network is involved. For example in a social network, it may represent the influence of a single person (based on the number of mutual connection with other people). In a computer network a high value of betweenness centrality, means that a computer is more involved in sharing information than another (important when analyzing faulttolerance). This is an implementation of Brandes’ algorithm.
Definition
Let \(G = (V, E)\) be a graph with \(V\) the set of vertices and \(E\) the set of edges, \(\sigma_{st}(v)\) be the number ofbit shortest path from \(s\) to \(t\) through \(v\) and \(\sigma_{st}\) be the number of shortest path from \(s\) to \(t\). Then the betweenness centrality index of \(v\) is defined as \(B_C(v) = \sum\limits_{s\neq v\neq t \in V} \dfrac{\sigma_{st}(v)}{\sigma_{st}}\)
Shortest Paths and Centrality Index
The problem itself can be seen and the combination of two problems:

First of all, we must calculate all shortest path in the graph. In particular we need APSP (All Pair Shortest Path), this can be done using FloydWarshall algorithm, but for sake of performances I used \(V\) times Dijkstra algorithm (in particular it allow to use an additional \(O(V)\) memory instead of \(O(V^2)\)).

The second problem require to calculate the centrality index using the formula.
Shortest Paths
It’s useful to augment Dijkstra algorithm to save some additional information. In particular for each node it’s possible to save a list of predecessor for any SP to the node and the total number of SPs. Finally, a stack is used to save the order in which the nodes are visited.
Centrality Index
With the additional information stored while finding the SPs it’s possible to calculate the centrality index in linear time using Brandes intuition.
I personally tested the algorithm using different data structure for Dijkstra algorithm (priority queue based on minheap, STL priority queue, STL set). The implementation using Fibonacci Heap performed better than expected, it can be compared to the minheap implementation. The Fibonacci Heap implementation can be found here.
Enjoy Reading This Article?
Here are some more articles you might like to read next: