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 fault-tolerance). 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 Floyd-Warshall 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 min-heap, STL priority queue, STL set). The implementation using Fibonacci Heap performed better than expected, it can be compared to the min-heap implementation. The Fibonacci Heap implementation can be found here.