# An Adaptive Version of Brandes' Algorithm for Betweenness Centrality

arXiv: https://arxiv.org/abs/1802.06701 · HTML: https://mlsanity.com/paper/1802.06701/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2018.

## Built on by (most cited first, 1 of 1)

- [Functional Connectivity Methods for EEG-based Biometrics on a Large, Heterogeneous Dataset](https://mlsanity.com/paper/2206.01475/) (2022)

## Abstract (arXiv)

Betweenness centrality---measuring how many shortest paths pass through a vertex---is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [J. Math. Sociol.~'01] computes, on an n-vertex and m-edge graph, the betweenness centrality of all vertices in O(nm) worst-case time. In later work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound O(kn), where k < m is the size of a minimum feedback edge set of the input graph.