Graph manipulations for fast centrality computation

Sarıyüce, Ahmet Erdem and Kaya, Kamer and Saule, Erik and Çatalyürek, Ümit V. (2014) Graph manipulations for fast centrality computation. [Working Paper / Technical Report] Sabanci University ID:UNSPECIFIED

[thumbnail of paper.pdf] PDF
paper.pdf

Download (2MB)

Abstract

The betweenness and closeness metrics have always been intriguing and used in many analyses. 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, which manipulates the graph by compressing it and splitting into pieces so that the centrality computation can be handled independently for each piece. Although BADIOS is designed and fine-tuned for exact betweenness and closeness centrality, it can easily be adapted for approximate solutions as well. 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, we achieve to decrease the closeness computation time from more than 3 days to 6 hours (12.7x speedup).
Item Type: Working Paper / Technical Report
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: 05 Dec 2014 22:23
Last Modified: 26 Apr 2022 10:51
URI: https://research.sabanciuniv.edu/id/eprint/25266

Actions (login required)

View Item
View Item