research-article

Scalable and high performance betweenness centrality on the GPU

Authors:

Adam McLaughlin,

David A. BaderAuthors Info & Claims

SC '14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

Pages 572 - 583

https://doi.org/10.1109/SC.2014.52

Published: 16 November 2014 Publication History

Abstract

Graphs that model social networks, numerical simulations, and the structure of the Internet are enormous and cannot be manually inspected. A popular metric used to analyze these networks is betweenness centrality, which has applications in community detection, power grid contingency analysis, and the study of the human brain. However, these analyses come with a high computational cost that prevents the examination of large graphs of interest.

Prior GPU implementations suffer from large local data structures and inefficient graph traversals that limit scalability and performance. Here we present several hybrid GPU implementations, providing good performance on graphs of arbitrary structure rather than just scale-free graphs as was done previously. We achieve up to 13x speedup on high-diameter graphs and an average of 2.71x speedup overall over the best existing GPU algorithm. We observe near linear speedup and performance exceeding tens of GTEPS when running betweenness centrality on 192 GPUs.

References

[1]

ORNL Debuts Titan Supercomputer. 2012 (accessed April 10, 2014). {Online}. Available: https://www.olcf.ornl.gov/wp-content/themes/olcf/titan/Titan_Debuts.pdf

[2]

M. Anderson, "Better Benchmarking for Supercomputers," Spectrum, IEEE, vol. 48, no. 1, pp. 12--14, 2011.

Digital Library

[3]

D. A. Bader, S. Kintali, K. Madduri, and M. Mihail, "Approximating Betweenness Centrality," in Algorithms and models for the web-graph. Springer, 2007, pp. 124--137.

Digital Library

[4]

D. A. Bader, H. Meyerhenke, P. Sanders, and D. Wagner, Eds., Graph Partitioning and Graph Clustering - 10th DIMACS Implementation Challenge, ser. Contemporary Mathematics, vol. 588, 2013.

[5]

A.-L. Barabási and R. Albert, "Emergence of Scaling in Random Networks," science, vol. 286, no. 5439, pp. 509--512, 1999.

[6]

S. Beamer, K. Asanović, and D. Patterson, "Direction-optimizing breadth-first search," Scientific Programming, vol. 21, no. 3, pp. 137--148, 2013.

Digital Library

[7]

U. Brandes, "A Faster Algorithm for Betweenness Centrality," Journal of Mathematical Sociology, vol. 25, pp. 163--177, 2001.

[8]

U. Brandes, "On Variants of Shortest-Path Betweenness Centrality and their Generic Computation," Social Networks, vol. 30, no. 2, pp. 136--145, 2008.

[9]

U. Brandes and C. Pich, "Centrality Estimation in Large Networks," International Journal of Bifurcation and Chaos, vol. 17, no. 07, pp. 2303--2318, 2007.

[10]

E. Bullmore and O. Sporns, "Complex Brain Networks: Graph Theoretical Analysis of Structural and Functional Systems," Nature Reviews Neuroscience, vol. 10, no. 3, pp. 186--198, 2009.

[11]

D. Chakrabarti, Y. Zhan, and C. Faloutsos, "R-MAT: A Recursive Model for Graph Mining." in SDM, vol. 4. SIAM, 2004, pp. 442--446.

[12]

E. Cho, S. A. Myers, and J. Leskovec, "Friendship and Mobility: User Movement in Location-Based Social Networks," in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2011, pp. 1082--1090.

Digital Library

[13]

A. A. Davidson, S. Baxter, M. Garland, and J. D. Owens, "Work-Efficient Parallel GPU Methods for Single-Source Shortest Paths," in International Parallel and Distributed Processing Symposium, vol. 28, 2014.

Digital Library

[14]

T. A. Davis and Y. Hu, "The University of Florida Sparse Matrix Collection," ACM Trans. Math. Softw., vol. 38, no. 1, pp. 1:1--1:25, Dec. 2011.

Digital Library

[15]

J. J. Dongarra, H. W. Meuer, and E. Strohmaier, "Top500 Supercomputer Sites," 1994.

[16]

D. Ediger, K. Jiang, J. Riedy, D. A. Bader, C. Corley, R. Farber, and W. N. Reynolds, "Massive Social Network Analysis: Mining Twitter for Social Good," 2010.

[17]

R. W. Floyd, "Algorithm 97: Shortest path," Commun. ACM, vol. 5, no. 6, pp. 345--, Jun. 1962.

Digital Library

[18]

L. C. Freeman, "A Set of Measures of Centrality Based on Betweenness," Sociometry, pp. 35--41, 1977.

[19]

O. Green and D. A. Bader, "Faster Betweenness Centrality Based on Data Structure Experimentation," Procedia Computer Science, vol. 18, no. 0, pp. 399--408, 2013, 2013 International Conference on Computational Science.

[20]

J. Hoberock and N. Bell, "Thrust: A Parallel Template Library," Online at http://thrust. googlecode. com, vol. 42, p. 43, 2010.

[21]

M. Holtgrewe, P. Sanders, and C. Schulz, "Engineering a Scalable High Quality Graph Partitioner," in Parallel Distributed Processing (IPDPS), 2010 IEEE International Symposium on, April 2010, pp. 1--12.

[22]

S. Hong, N. C. Rodia, and K. Olukotun, "On Fast Parallel Detection of Strongly Connected Components (SCC) in Small-World Graphs," in Proceedings of SC13: International Conference for High Performance Computing, Networking, Storage and Analysis. ACM, 2013, p. 92.

Digital Library

[23]

Y. Jia, V. Lu, J. Hoberock, M. Garland, and J. C. Hart, "Edge v. Node Parallelism for Graph Centrality Metrics," GPU Computing Gems, vol. 2, pp. 15--30, 2011.

[24]

S. Jin, Z. Huang, Y. Chen, D. Chavarria-Miranda, J. Feo, and P. C. Wong, "A Novel Application of Parallel Betweenness Centrality to Power Grid Contingency Analysis," in IEEE International Symposium on Parallel Distributed Processing (IPDPS), 2010, pp. 1--7.

[25]

F. Liljeros, C. R. Edling, L. A. Amaral, H. E. Stanley, and Y. Aberg, "The Web of Human Sexual Contacts," Nature, vol. 411, no. 6840, pp. 907--908, 2001.

[26]

K. Madduri, D. Ediger, K. Jiang, D. Bader, and D. Chavarria-Miranda, "A Faster Parallel Algorithm and Efficient Multithreaded Implementations for Evaluating Betweenness Centrality on Massive Datasets," in IEEE International Symposium on Parallel & Distributed Processing (IPDPS), May 2009, pp. 1--8.

Digital Library

[27]

A. McLaughlin and D. Bader, "Revisiting Edge and Node Parallelism for Dynamic GPU Graph Analytics," in 2014 IEEE 28th International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2014.

Digital Library

[28]

M. Mendez-Lojo, M. Burtscher, and K. Pingali, "A GPU Implementation of Inclusion-based Points-to Analysis," in Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP '12. New York, NY, USA: ACM, 2012, pp. 107--116.

Digital Library

[29]

D. Merrill. CUDA Unbound. 2013 (accessed April 11, 2014). {Online}. Available: http://nvlabs.github.io/cub/

[30]

D. Merrill, M. Garland, and A. Grimshaw, "Policy-based Tuning for Performance Portability and Library Co-Optimization," in Innovative Parallel Computing (InPar), 2012. IEEE, 2012, pp. 1--10.

[31]

D. Merrill, M. Garland, and A. Grimshaw, "Scalable GPU Graph Traversal," in Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP '12. New York, NY, USA: ACM, 2012, pp. 117--128.

Digital Library

[32]

S. Porta, V. Latora, F. Wang, E. Strano, A. Cardillo, S. Scellato, V. Iacoviello, and R. Messora, "Street Centrality and Densities of Retail and Services in Bologna, Italy," Environment and Planning B: Planning and design, vol. 36, no. 3, pp. 450--465, 2009.

[33]

A. E. Sariyüce, E. Saule, K. Kaya, and Ü. Çatalyürek, "Regularizing Graph Centrality Computations," Journal of Parallel and Distributed Computing (JPDC), 2014 (to appear).

[34]

Z. Shi and B. Zhang, "Fast Network Centrality Analysis using GPUs," BMC bioinformatics, vol. 12, no. 1, p. 149, 2011.

[35]

J. Soman and A. Narang, "Fast Community Detection Algorithm with GPUs and Multicore Architectures," in International Parallel & Distributed Processing Symposium (IPDPS). IEEE, 2011, pp. 568--579.

Digital Library

[36]

J. S. Vetter, R. Glassbrook, J. Dongarra, K. Schwan, B. Loftis, S. McNally, J. Meredith, J. Rogers, P. Roth, K. Spafford, and S. Yalamanchili, "Keeneland: Bringing Heterogeneous GPU Computing to the Computational Science Community," Computing in Science & Engineering, vol. 13, no. 5, pp. 90--95, 2011.

Digital Library

[37]

D. J. Watts and S. H. Strogatz, "Collective Dynamics of Small-World Networks," nature, vol. 393, no. 6684, pp. 440--442, 1998.

[38]

J. Yang and J. Leskovec, "Defining and Evaluating Network Communities Based on Ground-Truth," in Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics. ACM, 2012, p. 3.

Digital Library

Cited By

Cousins CWohlgemuth CRiondato M(2023) Bavarian: Betweenness Centrality Approximation with Variance-aware Rademacher AveragesACM Transactions on Knowledge Discovery from Data10.1145/357702117:6(1-47)Online publication date: 6-Mar-2023
https://dl.acm.org/doi/10.1145/3577021
Ewing ERen JKansara DSathiyanarayanan VAyanian NPelachaud CTaylor MFaliszewski PMascardi V(2022)Betweenness Centrality in Multi-Agent Path FindingProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3535896(400-408)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3535896
Singh SShah TNasre R(2021)ParTBC: Faster Estimation of Top-k Betweenness Centrality Vertices on GPUACM Transactions on Design Automation of Electronic Systems10.1145/348661327:2(1-25)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3486613
Show More Cited By

Index Terms

Scalable and high performance betweenness centrality on the GPU

Recommendations

Accelerating GPU betweenness centrality

Graphs that model social networks, numerical simulations, and the structure of the Internet are enormous and cannot be manually inspected. A popular metric used to analyze these networks is Betweenness Centrality (BC), which has applications in ...
Betweenness centrality on GPUs and heterogeneous architectures
GPGPU-6: Proceedings of the 6th Workshop on General Purpose Processor Using Graphics Processing Units

The betweenness centrality metric has always been intriguing for graph analyses and used in various applications. Yet, it is one of the most computationally expensive kernels in graph mining. In this work, we investigate a set of techniques to make the ...
High-Performance and Scalable GPU Graph Traversal
Special Issue on PPOPP 2012

Breadth-First Search (BFS) is a core primitive for graph traversal and a basis for many higher-level graph analysis algorithms. It is also representative of a class of parallel computations whose memory accesses and work distribution are both irregular ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SC '14: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis

November 2014

1054 pages

ISBN:9781479955008

General Chair:
Trish Damkroger
Lawrence Livermore National Laboratory, Livermore, California
,
Program Chair:
Jack Dongarra
University of Tennessee, Knoxville, Tennessee

Sponsors

Publisher

IEEE Press

Publication History

Published: 16 November 2014

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SC '14

Sponsor:

SIGHPC
SIGARCH
IEEE-CS

SC '14: International Conference for High Performance Computing, Networking, Storage and Analysis

November 16 - 21, 2014

Louisana, New Orleans

Acceptance Rates

SC '14 Paper Acceptance Rate 83 of 394 submissions, 21%;

Overall Acceptance Rate 1,516 of 6,373 submissions, 24%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
494
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cousins CWohlgemuth CRiondato M(2023) Bavarian: Betweenness Centrality Approximation with Variance-aware Rademacher AveragesACM Transactions on Knowledge Discovery from Data10.1145/357702117:6(1-47)Online publication date: 6-Mar-2023
https://dl.acm.org/doi/10.1145/3577021
Ewing ERen JKansara DSathiyanarayanan VAyanian NPelachaud CTaylor MFaliszewski PMascardi V(2022)Betweenness Centrality in Multi-Agent Path FindingProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3535896(400-408)Online publication date: 9-May-2022
https://dl.acm.org/doi/10.5555/3535850.3535896
Singh SShah TNasre R(2021)ParTBC: Faster Estimation of Top-k Betweenness Centrality Vertices on GPUACM Transactions on Design Automation of Electronic Systems10.1145/348661327:2(1-25)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3486613
Artiles OSaeed F(2021)TurboBC: A Memory Efficient and Scalable GPU Based Betweenness Centrality Algorithm in the Language of Linear Algebra50th International Conference on Parallel Processing Workshop10.1145/3458744.3474047(1-10)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3458744.3474047
Singh SNasre R(2020)Graffix: Efficient Graph Processing with a Tinge of GPU-Specific ApproximationsProceedings of the 49th International Conference on Parallel Processing10.1145/3404397.3404406(1-11)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1145/3404397.3404406
Shukla KRegunta STondomker SKothapalli KAyguadé EHwu WBadia RHofstee H(2020)Efficient parallel algorithms for betweenness- and closeness-centrality in dynamic graphsProceedings of the 34th ACM International Conference on Supercomputing10.1145/3392717.3392743(1-12)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1145/3392717.3392743
Gaihre AWu ZYao FLiu HWeissman JButt ASmirni E(2019)XBFSProceedings of the 28th International Symposium on High-Performance Parallel and Distributed Computing10.1145/3307681.3326606(121-131)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3307681.3326606
Wang HGeng LLee RHou KZhang YZhang XHollingsworth JKeidar I(2019)SEP-graphProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295733(38-52)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295733
Meng KLi JTan GSun NHollingsworth JKeidar I(2019)A pattern based algorithmic autotuner for graph processing on GPUsProceedings of the 24th Symposium on Principles and Practice of Parallel Programming10.1145/3293883.3295716(201-213)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.1145/3293883.3295716
García JCarriegos M(2019)On parallel computation of centrality measures of graphsThe Journal of Supercomputing10.1007/s11227-018-2654-575:3(1410-1428)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s11227-018-2654-5
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents