Two-level clustering fast betweenness centrality computation for requirement-driven approximation

Betweenness centrality is a metric widely used in several domains (social, biological, transportation, computer) to identify critical nodes of networks. Its exact computation is very demanding, with an O(nm) time complexity for unweighted graphs (where n is the number of nodes and m is the number of edges). Such complexity becomes an obstacle to the adoption of betweenness centrality for continuous monitoring of critical nodes in very large networks. Several solutions have been proposed to reduce computation time, mainly via parallelism, approximation or incremental recalculation. In this paper, we propose an algorithm for computing approximated values of betweenness that allows for tuning its performance on the basis of a tolerable error. The algorithm aims at reducing the number of single-source shortest-paths explorations via a pivot-based technique that exploits topological properties of graphs and clustering. It is evaluated by identifying the vulnerabilities (critical nodes) of a real-world, very-large road network. The evaluation shows that the approximation error does not significantly affect the most critical nodes, thus making the algorithm well-suited for on-line operational monitoring of road networks.