Title: An Adaptive Version of Brandes' Algorithm for Betweenness Centrality,
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 [2001]
computes, on an $n$-vertex and $m$-edge graph, the betweenness centrality of
all vertices in $O(nm)$ worst-case time. In follow-up work, significant
empirical speedups were achieved by preprocessing degree-one vertices and by
graph partitioning based on cut vertices. We further 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.