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. (Request a copy)


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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 15 May 2017 10:28
Last Modified: 16 May 2017 11:59

Actions (login required)

View Item
View Item