Dimitrios Prountzos
Keshav Pingali
Abstract
Betweenness centrality is an important metric in the study of social networks, and several algorithms for computing this metric exist in the literature. This paper makes three contributions. First, we show that the problem of computing betweenness centrality can be formulated abstractly in terms of a small set of operators that update the graph. Second, we show that existing parallel algorithms for computing betweenness centrality can be viewed as implementations of different schedules for these operators, permitting all these algorithms to be formulated in a single framework. Third, we derive a new asynchronous parallel algorithm for betweenness centrality that (i) works seamlessly for both weighted and unweighted graphs, (ii) can be applied to large graphs, and (iii) is able to extract large amounts of parallelism. We implemented this algorithm and compared it against a number of publicly available implementations of previous algorithms on two different multicore architectures. Our results show that the new algorithm is the best performing one in most cases, particularly for large graphs and large thread counts, and is always competitive against other algorithms.
- Galois system. http://iss.ices.utexas.edu/?p=projects/galois.Google Scholar
- 9th DIMACS Implementation Challenge. http://www.dis.uniroma1.it/~challenge9/download.shtml, 2009.Google Scholar
- D. Bader., J. Gilbert, J. Kepner, and K. Madduri. Hpcs scalable synthetic compact applications graph analysis (SSCA2) benchmark v2.2, 2007. http://www.graphanalysis.org/benchmark/.Google Scholar
- D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating betweenness centrality. In WAW, Berlin, Heidelberg, 2007. Google ScholarDigital Library
- D. A. Bader and K. Madduri. Parallel algorithms for evaluating centrality indices in real-world networks. In ICPP, 2006. Google ScholarDigital Library
- G. Blelloch, J. Fineman, P. Gibbons, and H. Simhadri. Scheduling irregular parallel computations on hierarchical caches. In SPAA, 2011. Google ScholarDigital Library
- R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: An efficient multithreaded runtime system. In PPOPP, 1995. Google ScholarDigital Library
- R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. Journal of the ACM, 46(5), 1999. Google ScholarDigital Library
- U. Brandes. A faster algorithm for betweenness centrality. Journal of Mathematical Sociology, 25, 2001.Google Scholar
- U. Brandes and C. Pich. Centrality Estimation in Large Networks. International Journal of Birfucation and Chaos, 17(7), 2007.Google Scholar
- N. Bulkley and M. V. Alstyne. Does e-mail make white collar workers more productive? Technical report, University of Michigan, 2004.Google Scholar
- A. Buluc and J. Gilbert. The combinatorial BLAS: design, implementation, and applications. Int. Journal of High Perf. Computing Applications, 2011. Google ScholarDigital Library
- D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In In SIAM Data Mining, 2004.Google ScholarCross Ref
- R. Chowdhury, F. Silvestri, B. Blakeley, and V. Ramachandran. Oblivious algorithms for multicores and network of processors. In IPDPS, 2010.Google ScholarCross Ref
- T. Coffman, S. Greenblatt, and S. Marcus. Graph-based technologies for intelligence analysis. Commun. ACM, 47, 2004. Google ScholarDigital Library
- G. Cong and K. Makarychev. Optimizing large-scale graph analysis on a multi-threaded, multi-core platform. In IPDPS, 2011. Google ScholarDigital Library
- A. Del Sol, H. Fujihashi, and P. O'Meara. Topology of small-world networks of protein--protein complex structures. Bioinformatics, 2005. Google ScholarDigital Library
- D. Ediger, K. Jiang, J. Riedy, D. A. Bader, and C. Corley. Massive social network analysis: Mining twitter for social good. In ICPP, 2010. Google ScholarDigital Library
- N. Edmonds, T. Hoefler, and A. Lumsdaine. A space-efficient parallel algorithm for computing betweenness centrality in distributed memory. In HiPC, 2010.Google ScholarCross Ref
- L. C. Freeman. A set of measures of centrality based on betweenness. 1977.Google Scholar
- R. Geisberger, P. Sanders, and D. Schultes. Better approximation of betweenness centrality. In ALENEX, 2008.Google ScholarDigital Library
- M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12), 2002.Google ScholarCross Ref
- R. Guimer`a, S. Mossa, A. Turtschi, and L. A. N. Amaral. The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles. NAS, 102(22), 2005.Google Scholar
- M. Hassaan, M. Burtscher, and K. Pingali. Ordered vs unordered: a comparison of parallelism and work-efficiency in irregular algorithms. In PPOPP, 2011. Google ScholarDigital Library
- H. Jeong, S. P. Mason, A. L. Barabasi, and Z. N. Oltvai. Lethality and centrality in protein networks. Nature, 411, May 2001.Google Scholar
- S. Jin, Z. Huang, Y. Chen, D. G. Chavarr1a-Miranda, J. Feo, and P. C. Wong. A novel application of parallel betweenness centrality to power grid contingency analysis. In IPDPS, 2010.Google ScholarCross Ref
- V. Krebs. Mapping networks of terrorist cells. Connections, 2002.Google Scholar
- F. Liljeros, C. Edling, L. Amaral, H. Stanley, and Y. Aberg. The web of human sexual contacts. Nature, 411, 2001.Google Scholar
- K. Madduri, D. Ediger, K. Jiang, D. A. Bader, and D. G. Chavarramiranda. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets. In IPDS, 2009. Google ScholarDigital Library
- U. Meyer and P. Sanders. Delta-stepping: A parallel single source shortest path algorithm. In ESA, 1998. Google ScholarDigital Library
- D. Nguyen and K. Pingali. Synthesizing concurrent schedulers for irregular algorithms. In ASPLOS, 2011. Google ScholarDigital Library
- G. Palla, I. J. Farkas, P. Pollner, I. Derenyi, and T. Vicsek. Fundamental statistical features and self-similar properties of tagged networks. New Journal of Physics, 10, 2008. http://cfinder.org/wiki/?n=Main.Data#toc2.Google Scholar
- R. Pearce, M. Gokhale, and N. Amato. Multithreaded asynchronous graph traversal for in-memory and semi-external memory. In SC, 2010. Google ScholarDigital Library
- K. Pingali, D. Nguyen, M. Kulkarni, M. Burtscher, M. A. Hassaan, R. Kaleem, T. Lee, A. Lenharth, R. Manevich, M. Mendez-Lojo, D. Prountzos, and X. Sui. The TAO of parallelism in algorithms. In PLDI, 2011. Google ScholarDigital Library
- D. Prountzos and K. Pingali. Betweenness centrality: Algorithms and implementations. Technical Report TR-13-31, UT Austin, Jan 2013.Google ScholarDigital Library
- Z. Shi and B. Zhang. Fast network centrality analysis using gpus. BMC Bioinformatics, 2011.Google ScholarCross Ref
- J. G. Siek. and a. A. L. L.Q. Lee. The Boost Graph Library: User Guide and Reference Manual (C++ In-Depth Series). Addison-Wesley Professional, 2001.Google Scholar
- G. Tan, V. C. Sreedhar, and G. R. Gao. Analysis and performance results of computing betweenness centrality on ibm cyclops64. J. Supercomput., 56, 2011. Google ScholarDigital Library
- G. Tan, D. Tu, and N. Sun. A parallel algorithm for computing betweenness centrality. In ICPP, 2009. Google ScholarDigital Library
- J. Yang and Y. Chen. Fast computing betweenness centrality with virtual nodes on large sparse networks. PLoS ONE, 6(7), 2011.Google Scholar
- Q. Yang and S. Lonardi. A parallel algorithm for clustering proteinprotein interaction networks. Comp. Systems Bioinformatics, 2005. Google ScholarDigital Library
Index Terms
- Betweenness centrality: algorithms and implementations
Recommendations
Betweenness centrality: algorithms and implementations
PPoPP '13: Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programmingBetweenness centrality is an important metric in the study of social networks, and several algorithms for computing this metric exist in the literature. This paper makes three contributions. First, we show that the problem of computing betweenness ...
Effective co-betweenness centrality computation
WSDM '14: Proceedings of the 7th ACM international conference on Web search and data miningBetweenness centrality of vertices is essential in the analysis of social and information networks, and co-betweenness centrality is one of two natural ways to extend it to sets of vertices. Existing algorithms for co-betweenness centrality computation ...
Sink Group Betweenness Centrality
IDEAS '21: Proceedings of the 25th International Database Engineering & Applications SymposiumThis article introduces the concept of Sink Group Node Betweenness centrality to identify those nodes in a network that can “monitor” the geodesic paths leading towards a set of subsets of nodes; it generalizes both the traditional node betweenness ...
Comments