Graph Manipulations for Fast Centrality Computation

Citations Over TimeTop 12% of 2017 papers

Abstract

The betweenness and closeness metrics are widely used metrics in many network analysis applications. Yet, they are expensive to compute. For that reason, making the betweenness and closeness centrality computations faster is an important and well-studied problem. In this work, we propose the framework BADIOS that manipulates the graph by compressing it and splitting into pieces so that the centrality computation can be handled independently for each piece. Experimental results show that the proposed techniques can be a great arsenal to reduce the centrality computation time for various types and sizes of networks. In particular, it reduces the betweenness centrality computation time of a 4.6 million edges graph from more than 5 days to less than 16 hours. For the same graph, the closeness computation time is decreased from more than 3 days to 6 hours (12.7x speedup).

Related Papers

• → Attack Robustness and Centrality of Complex Networks(2013)469 cited
• → Factors that predict better synchronizability on complex networks(2004)241 cited
• → Characterization of weighted complex networks(2004)86 cited
• → Search in weighted complex networks(2005)55 cited
• → Investigating Attachment Behavior of Nodes during Evolution of a Complex Social Network:(2011)5 cited