Cluster-based Computation of Exact Betweenness Centrality in Large Undirected Graphs

Nowadays a large amount of data is originated by complex systems, such as social networks, transportation systems, computer and service networks. These systems can be effectively modeled through graphs and studied by exploiting graph metrics, such as Betweenness Centrality (BC), a popular metric to analyze node centrality. In spite of its great potential, this metric requires long computation time, especially for large graphs. In this paper, we present a novel very fast algorithm to compute exact BC of undirected, scale-free graphs. The algorithm is based on clustering and exploits structural properties of graphs to find classes of equivalent nodes. By selecting one representative node for each class, we are able to calculate BC by significantly reducing the number of single-source shortest path explorations adopted by the Brandes' algorithm. The experimental evaluation of both sequential and map-reduce parallel versions reveals that our solution largely outperforms Brandes and recent heuristics, especially for large graphs while preserving good scalability.