Journal
JOURNAL OF BIG DATA
Volume 8, Issue 1, Pages -Publisher
SPRINGERNATURE
DOI: 10.1186/s40537-021-00483-1
Keywords
Complex networks analysis; Betweenness centrality; Distributed computation; Big data processing
Categories
Funding
- French ANR research project PROMENADE [ANR-18-CE22-0008]
- Italian MIUR PRIN research project GAUSS [2015KWREMX]
Ask authors/readers for more resources
The study introduces a fast algorithm for computing BC of undirected graphs by using clustering, which outperforms Brandes' algorithm and significantly improves known heuristics.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available