Graph manipulations for fast centrality computation
Sarıyüce, Ahmet Erdem and Kaya, Kamer and Saule, Erik and Çatalyürek, Ümit V. (2017) Graph manipulations for fast centrality computation. ACM Transactions on Knowledge Discovery from Data, 11 (3). ISSN 1556-4681 (Print) 1556-472X (Online)
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1145/3022668
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).
Repository Staff Only: item control page