Fast cluster-based computation of exact betweenness centrality in large graphs

Journal of Big Data

Lorenzo Goglia¹  Eugenio Zimeo¹  Angelo Furno²  Cecile Daniel² 

[1] Department of Engineering, University of Sannio, 82100, Benevento, Italy;LICIT UMR_T9401, University Gustave Eiffel, University of Lyon, ENTPE, Lyon, France;

关键词: Complex networks analysis;    Betweenness centrality;    Distributed computation;    Big data processing;   

DOI  :  10.1186/s40537-021-00483-1

来源: Springer

【 摘 要 】

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 modeled by using graphs and studied by exploiting graph metrics, such as betweenness centrality (BC), a popular metric to analyze node centrality of graphs. In spite of its great potential, this metric requires long computation time, especially for large graphs. In this paper, we present a very fast algorithm to compute BC of undirected graphs by exploiting clustering. The algorithm leverages structural properties of graphs to find classes of equivalent nodes: by selecting one representative node for each class, we are able to compute BC by significantly reducing the number of single-source shortest path explorations adopted by Brandes’ algorithm. We formally prove the graph properties that we exploit to define the algorithm and present an implementation based on Scala for both sequential and parallel map-reduce executions. The experimental evaluation of both versions, conducted with synthetic and real graphs, reveals that our solution largely outperforms Brandes’ algorithm and significantly improves known heuristics.

【 授权许可】

CC BY