Heuristics for Speeding Up Betweenness Centrality Computation
The authors propose and evaluate two complementary heuristics to speed up exact computation of the shortest-path betweenness centrality. Both heuristics are relatively simple adaptations of the standard algorithm for betweenness centrality. Consequently, they generalize the computation of edge betweenness and most other variants, and can be used to further speed up betweenness estimation algorithms, as well. In the first heuristic, structurally equivalent vertices are contracted based on the observation that they have the same centrality and also contribute equally to the centrality of others. In the second heuristic, they first apply a linear-time betweenness algorithm on the block-cutpoint tree and then compute the remaining contributions separately in each biconnected component.