Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00543
An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
Matthias Bentert,
Alexander Dittmann,
Leon Kellerhals,
AndrĂ© Nichterlein, and
Rolf Niedermeier
Vol. 24, no. 3, pp. 483522, 2020. Regular paper.
Abstract Betweenness centralitymeasuring how many shortest paths pass through a vertexis one of the most important network analysis concepts for assessing the relative importance of a vertex.
The wellknown 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)$ worstcase time.
In later work, significant empirical speedups were achieved by preprocessing degreeone vertices and by graph partitioning based on cut vertices.
We contribute an algorithmic treatment of degreetwo vertices, which turns out to be much richer in mathematical structure than the case of degreeone vertices.
Based on these three algorithmic ingredients, we provide a strengthened worstcase 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.

Submitted: May 2020.
Reviewed: August 2020.
Revised: October 2020.
Accepted: October 2020.
Final: October 2020.
Published: October 2020.
Communicated by
Yoshio Okamoto
