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. 483-522, 2020. Regular paper.
Abstract 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.
|
Submitted: May 2020.
Reviewed: August 2020.
Revised: October 2020.
Accepted: October 2020.
Final: October 2020.
Published: October 2020.
Communicated by
Yoshio Okamoto
|
Journal Supporters
|