title   
  

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

[img]PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
2380Kb

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
ID Code:25266
Deposited By:Kamer Kaya
Deposited On:05 Dec 2014 22:23
Last Modified:05 Dec 2014 22:23

Repository Staff Only: item control page