Ahmet Erdem Sariyüce
Abstract
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).
- M. Baglioni, F. Geraci, M. Pellegrini, and E. Lastres. 2012. Fast exact computation of betweenness centrality in social networks. In Proceedings of IEEE/ACM International Conference on Advances in Social Network Analysis and Mining (ASONAM). Google Scholar
Digital Library
- U. Brandes. 2001. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology 25, 2 (2001), 163--177. Google ScholarCross Ref
- U. Brandes. 2008. On variants of shortest-path betweenness centrality and their generic computation. Social Networks 30, 2 (2008), 136--145. Google Scholar
- U. Brandes and C. Pich. 2007. Centrality estimation in large networks. International Journal of Bifurcation and Chaos 17, 7 (2007), 2303--2318. Google Scholar
- Ö. Şimşek and A. G. Barto. 2008. Skill characterization based on betweenness. In Neural Information Processing Systems.Google Scholar
- L. Freeman. 1977. A set of measures of centrality based upon betweenness. Sociometry 4 (1977), 35--41. Google ScholarCross Ref
- R. Geisberger, P. Sanders, and D. Schultes. 2008. Better approximation of betweenness centrality. In Proceedings of ALENEX. Google ScholarCross Ref
- Y. Jia, V. Lu, J. Hoberock, M. Garland, and J. C. Hart. 2011. Edge vs. node parallelism for graph centrality metrics. In Proceedings of GPU Computing Gems: Jade Edition.Google Scholar
- S. Jin, Z. Huang, Y. Chen, D. Chavarria-Miranda, J. Feo, and P. C. Wong. 2010. A novel application of parallel betweenness centrality to power grid contingency analysis. In Proceedings of IEEE International Parallel 8 Distributed Processing Symposium. Google ScholarCross Ref
- S. Kintali. 2008. Betweenness Centrality: Algorithms and Lower Bounds. Arxiv preprint arXiv:0809.1906 (2008).Google Scholar
- D. Koschützki and F. Schreiber. 2008. Centrality analysis methods for biological networks and their application to gene regulatory networks. Gene Regulation and Systems Biology 2 (2008), 193--201.Google ScholarCross Ref
- V. Krebs. 2002. Mapping networks of terrorist cells. Connections 24, 3 (2002), 43--52.Google Scholar
- R. Lichtenwalter and N. V. Chawla. 2011. DisNet: A framework for distributed graph computation. In Proceedings of IEEE/ACM International Conference on Advances in Social Network Analysis and Mining (ASONAM). Google ScholarDigital Library
- J.-K. Lou, S. D. Lin, K.-T. Chen, and C.-L. Lei. 2010. What can the temporal social behavior tell us? An estimation of vertex-betweenness using dynamic social information. In Proceedings of IEEE/ACM International Conference on Advances in Social Network Analysis and Mining (ASONAM). Google ScholarDigital Library
- A. Lugowski, D. Alber, A. Buluç, J. Gilbert, S. Reinhardt, Y. Teng, and A. Waranis. 2012. A flexible open-source toolbox for scalable complex graph analysis. In Proceedings of SDM. Google ScholarCross Ref
- K. Madduri, D. Ediger, K. Jiang, D. A. Bader, and D. G. Chavarria-Miranda. 2009. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets. In Proceedings of IEEE International Parallel 8 Distributed Processing Symposium. Google ScholarDigital Library
- R. Puzis, Y. Elovici, P. Zilberman, S. Dolev, and U. Brandes. 2015. Topology manipulations for speeding betweenness centrality computation. Journal of Complex Networks 3, 1 (2015), 84--112. Google ScholarCross Ref
- R. Puzis, P. Zilberman, Y. Elovici, S. Dolev, and U. Brandes. 2012. Heuristics for speeding up betweenness centrality computation. In Proceedings of SocialCom. Google ScholarDigital Library
- M. Riondato and E. Upfal. 2016. ABRA: Approximating betweenness centrality in static and dynamic graphs with rademacher averages. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1145--1154. Google ScholarDigital Library
- A. E. Sarıyüce, K. Kaya, E. Saule, and Ü. V. Çatalyürek. 2013a. Betweenness centrality on GPUs and heterogeneous architectures. In Proceedings of Workshop on General Purpose Processing Using GPUs (GPGPU), in Conjunction with ASPLOS. Google ScholarDigital Library
- A. E. Sarıyüce, E. Saule, K. Kaya, and Ü. V. Çatalyürek. 2013b. Shattering and compressing networks for betweenness centrality. In Proceedings of the SIAM International Conference on Data Mining, SDM. An extended version is available as a Tech Rep on ArXiv http://arxiv.org/abs/1209.6007.Google ScholarCross Ref
- A. E. Sarıyüce, E. Saule, K. Kaya, and Ü. V. Çatalyürek. 2014. Hardware/software vectorization for closeness centrality on multi-/many-core architectures. In Proceedings of the 28th International Symposium on Parallel and Distributed Processing, Workshops and PhD Forum (IPDPSW), Workshop on Multithreaded Architectures and Applications (MTAAP).Google ScholarDigital Library
- A. E. Sarıyüce, E. Saule, K. Kaya, and Ü. V. Çatalyürek. 2015. Regularizing graph centrality computations. Journal of Parallel and Distributed Computing 76, C (Feb. 2015), 106--119. Google ScholarDigital Library
- Z. Shi and B. Zhang. 2011. Fast network centrality analysis using GPUs. BMC Bioinformatics 12 (2011), 149. Google ScholarCross Ref
Index Terms
- Graph Manipulations for Fast Centrality Computation
Recommendations
Laplacian centrality: A new centrality measure for weighted networks
The centrality of vertices has been a key issue in network analysis. For unweighted networks where edges are just present or absent and have no weight attached, many centrality measures have been presented, such as degree, betweenness, closeness, ...
Alpha Current Flow Betweenness Centrality
Algorithms and Models for the Web GraphAbstractA class of centrality measures called betweenness centralities reflects degree of participation of edges or nodes in communication between different parts of the network. The original shortest-path betweenness centrality is based on counting ...
Regularizing graph centrality computations
Centrality metrics such as betweenness and closeness have been used to identify important nodes in a network. However, it takes days to months on a high-end workstation to compute the centrality of today's networks. The main reasons are the size and the ...
Comments