TY - GEN
T1 - Shattering and compressing networks for betweenness centrality
AU - Sariyüce, Ahmet Erdem
AU - Saule, Erik
AU - Kaya, Kamer
AU - Çatalyürek, Ümit V.
N1 - Publisher Copyright:
Copyright © SIAM.
PY - 2013
Y1 - 2013
N2 - The betweenness metric has always been intriguing and used in many analyses. Yet, it is one of the most computationally expensive kernels in graph mining. For that reason, making betweenness centrality computations faster is an important and well-studied problem. In this work, we propose the framework, BADIOS, which compresses a network and shatters it into pieces so that the centrality computation can be handled independently for each piece. Although BADIOS is designed and tuned for betweenness centrality, it can easily be adapted for other centrality metrics. 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 computation time of a 4.6 million edges graph from more than 5 days to less than 16 hours.
AB - The betweenness metric has always been intriguing and used in many analyses. Yet, it is one of the most computationally expensive kernels in graph mining. For that reason, making betweenness centrality computations faster is an important and well-studied problem. In this work, we propose the framework, BADIOS, which compresses a network and shatters it into pieces so that the centrality computation can be handled independently for each piece. Although BADIOS is designed and tuned for betweenness centrality, it can easily be adapted for other centrality metrics. 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 computation time of a 4.6 million edges graph from more than 5 days to less than 16 hours.
KW - Betweenness centrality
KW - Graph mining
KW - Network analysis
UR - https://www.scopus.com/pages/publications/84960115726
U2 - 10.1137/1.9781611972832.76
DO - 10.1137/1.9781611972832.76
M3 - Conference contribution
AN - SCOPUS:84960115726
T3 - Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013
SP - 686
EP - 694
BT - Proceedings of the 2013 SIAM International Conference on Data Mining, SDM 2013
A2 - Ghosh, Joydeep
A2 - Obradovic, Zoran
A2 - Dy, Jennifer
A2 - Zhou, Zhi-Hua
A2 - Kamath, Chandrika
A2 - Parthasarathy, Srinivasan
PB - Siam Society
T2 - SIAM International Conference on Data Mining, SDM 2013
Y2 - 2 May 2013 through 4 May 2013
ER -