Reducing pivots of approximated betweenness computation by hierarchically clustering complex networks

Betweenness centrality is a widely adopted metric to analyze the impact of critical nodes of graphs in several domains (social, biological, transportation, service, computer networks). Its exact computation is very demanding due to an O(nm) time complexity on a graph with n nodes and m edges. This represents an obstacle to the adoption of betweenness centrality for continuous monitoring of critical nodes in very large networks. In this paper, we analyze the performance of a parametric two-level clustering algorithm for computing approximated values of betweenness with different kinds of graph. The analysis aims at evaluating how the properties of different complex networks impact the reduction of the number of single-source shortest-paths explorations of Brandes’ algorithm. The results confirm that one-level clustering strongly reduces the number of pivots (and consequently the computation time) on scale-free graphs, while small-world (and random) graphs need an additional level of clustering to achieve acceptable results.