Brandes’ algorithm for betweeness centrality

# Betweeness Centrality

Implementation of Betweeness Centrality using Dijkstra and Fibonacci heap

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 of 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.