Parallel Algorithm for Incremental Betweenness Centrality on Large Graphs
- 17 October 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 29 (3) , 659-672
Abstract
Betweenness centrality quantifies the importance of nodes in a graph in many applications, including network analysis, community detection and identification of influential users. Typically, graphs in such applications evolve over time. Thus, the computation of betweenness centrality should be performed incrementally. This is challenging because updating even a single edge may trigger the computation of all-pairs shortest paths in the entire graph. Existing approaches cannot scale to large graphs: they either require excessive memory (i.e., quadratic to the size of the input graph) or perform unnecessary computations rendering them prohibitively slow. We propose iCentral; a novel incremental algorithm for computing betweenness centrality in evolving graphs. We decompose the graph into biconnected components and prove that processing can be localized within the affected components. iCentral is the first algorithm to support incremental betweeness centrality computation within a graph component. This is done efficiently, in linear space; consequently, iCentral scales to large graphs. We demonstrate with real datasets that the serial implementation of iCentral is up to 3.7 times faster than existing serial methods. Our parallel implementation that scales to large graphs, is an order of magnitude faster than the state-of-the-art parallel algorithm, while using an order of magnitude less computational resources.Keywords
This publication has 32 references indexed in Scilit:
- Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality2014
- A Faster Algorithm to Update Betweenness Centrality after Node Alteration2013
- Faster Betweenness Centrality Based on Data Structure ExperimentationProcedia Computer Science, 2013
- Identifying gene-disease associations using centrality on a literature mined gene-interaction networkBioinformatics, 2008
- Better Approximation of Betweenness Centrality2008
- Approximating Betweenness Centrality2007
- Community structure in social and biological networksProceedings of the National Academy of Sciences of the United States of America, 2002
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- A Set of Measures of Centrality Based on BetweennessSociometry, 1977
- Algorithm 447: efficient algorithms for graph manipulationCommunications of the ACM, 1973