Graph manipulations for fast centrality computation

Warning The system is temporarily closed to updates for reporting purpose.

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).

Item Type:Article
Uncontrolled Keywords:Betweenness centrality; closeness centrality; shortest path
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:31329
Deposited By:Kamer Kaya
Deposited On:15 May 2017 10:28
Last Modified:16 May 2017 11:59

Repository Staff Only: item control page