research-article

Public Access

A round-efficient distributed betweenness centrality algorithm

Authors:

Matteo Pontecorvi,

Roshan Dathathri,

Gurbinder Gill,

Keshav Pingali,

Vijaya RamachandranAuthors Info & Claims

PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming

Pages 272 - 286

https://doi.org/10.1145/3293883.3295729

Published: 16 February 2019 Publication History

Abstract

We present Min-Rounds BC (MRBC), a distributed-memory algorithm in the CONGEST model that computes the betweenness centrality (BC) of every vertex in a directed unweighted n-node graph in O(n) rounds. Min-Rounds BC also computes all-pairs-shortest-paths (APSP) in such graphs. It improves the number of rounds by at least a constant factor over previous results for unweighted directed APSP and for unweighted BC, both directed and undirected.

We implemented MRBC in D-Galois, a state-of-the-art distributed graph analytics system, incorporated additional optimizations enabled by the D-Galois model, and evaluated its performance on a production cluster with up to 256 hosts using power-law and road networks. Compared to the BC algorithm of Brandes, on average, MRBC reduces the number of rounds by 14.0× and the communication time by 2.8× for the graphs in our test suite. As a result, MRBC is 2.1× faster on average than Brandes BC for real-world web-crawls on 256 hosts.

References

[1]

{n. d.}. Galois System. http://iss.ices.utexas.edu/?p=projects/galois.

[2]

2018. The Lonestar Benchmark Suite. http://iss.ices.utexas.edu/?p=projects/galois/lonestar

[3]

2018. Texas Advanced Computing Center (TACC), The University of Texas at Austin. https://www.tacc.utexas.edu/

[4]

U. Agarwal and V. Ramachandran. 2019. Distributed weighted all pairs shortest paths through pipelining. In Proceedings of the 33rd IEEE International Parallel and Distributed Processing (IPDPS '19). To appear.

[5]

L. Arge, M. T. Goodrich, and F. van Walderveen. 2013. Computing betweenness centrality in external memory. In 2013 IEEE International Conference on Big Data. 368--375.

[6]

David A. Bader, Shiva Kintali, Kamesh Madduri, and Milena Mihail. 2007. Approximating Betweenness Centrality. In Proceedings of the 5th International Workshop on Algorithms and Models for the Web-Graph (WAW '07). 124--137.

Digital Library

[7]

D. A. Bader and K. Madduri. 2006. Parallel Algorithms for Evaluating Centrality Indices in Real-world Networks. In 2006 International Conference on Parallel Processing (ICPP'06). 539--550.

Digital Library

[8]

Massimo Bernaschi, Giancarlo Carbone, and Flavio Vella. 2016. Scalable Betweenness Centrality on multi-GPU Systems. In Proceedings of the ACM International Conference on Computing Frontiers (CF '16). ACM, New York, NY, USA, 29--36.

Digital Library

[9]

Paolo Boldi, Andrea Marino, Massimo Santini, and Sebastiano Vigna. 2014. BUbiNG: Massive Crawling for the Masses. In Proceedings of the 23rd International Conference on World Wide Web (WWW '14 Companion). ACM, New York, NY, USA, 227--228.

Digital Library

[10]

Paolo Boldi, Marco Rosa, Massimo Santini, and Sebastiano Vigna. 2011. Layered Label Propagation: A Multiresolution Coordinate-free Ordering for Compressing Social Networks. In Proceedings of the 20th International Conference on World Wide Web (WWW '11). ACM, New York, NY, USA, 587--596.

Digital Library

[11]

P. Boldi and S. Vigna. 2004. The Webgraph Framework I: Compression Techniques. In Proceedings of the 13th International Conference on World Wide Web (WWW '04). ACM, New York, NY, USA, 595--602.

Digital Library

[12]

E. G. Boman, K. D. Devine, and S. Rajamanickam. 2013. Scalable matrix computations on large scale-free graphs using 2D graph partitioning. In 2013 SC - International Conference for High Performance Computing, Networking, Storage and Analysis (SC). 1--12.

Digital Library

[13]

U. Brandes. 2001. A Faster Algorithm for Betweenness Centrality. Journal of Mathematical Sociology 25 (2001).

[14]

Deepayan Chakrabarti, Yiping Zhan, and Christos Faloutsos. {n. d.}. R-MAT: A Recursive Model for Graph Mining. 442--446.

[15]

T. Coffman, S. Greenblatt, and S. Marcus. 2004. Graph-based technologies for intelligence analysis. Commun. ACM 47 (2004). Issue 3.

Digital Library

[16]

Roshan Dathathri, Gurbinder Gill, Loc Hoang, Hoang-Vu Dang, Alex Brooks, Nikoli Dryden, Marc Snir, and Keshav Pingali. 2018. Gluon: A Communication-optimizing Substrate for Distributed Heterogeneous Graph Analytics. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '18). ACM, New York, NY, USA, 752--768.

Digital Library

[17]

A. Del Sol, H. Fujihashi, and P. O'Meara. 2005. Topology of small-world networks of protein-protein complex structures. Bioinformatics (2005).

Digital Library

[18]

Laxman Dhulipala, Guy E. Blelloch, and Julian Shun. 2018. Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures (SPAA '18). ACM, New York, NY, USA, 393--404.

Digital Library

[19]

Nicoletta Di Blas and Bianca Boretti. 2009. Interactive Storytelling in Pre-school: A Case-study. (2009), 44--51.

Digital Library

[20]

N. Edmonds, T. Hoefler, and A. Lumsdaine. 2010. A space-efficient parallel algorithm for computing betweenness centrality in distributed memory. In HiPC.

[21]

Michael Elkin. 2006. An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36, 2 (2006), 433--456.

Digital Library

[22]

L. C. Freeman. 1977. A set of measures of centrality based on betweenness. (1977).

[23]

Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. 2012. Networks Cannot Compute Their Diameter in Sublinear Time. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '12). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1150--1162. http://dl.acm.org/citation.cfm?id=2095116.2095207

Digital Library

[24]

Karlsruher Institut fur Technologie. 2014. OSM-Europe. https://i11www.iti.kit.edu/resources/roadgraphs.php

[25]

Juan A. Garay, Shay Kutten, and David Peleg. 1998. A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees. SIAM J. Comput. 27, 1 (Feb. 1998), 302--316.

Digital Library

[26]

Gurbinder Gill, Roshan Dathathri, Loc Hoang, Andrew Lenharth, and Keshav Pingali. 2018. Abelian: A Compiler for Graph Analytics on Distributed, Heterogeneous Platforms. In Euro-Par 2018: Parallel Processing, Marco Aldinucci, Luca Padovani, and Massimo Torquati (Eds.). Springer International Publishing, Cham, 249--264.

[27]

Gurbinder Gill, Roshan Dathathri, Loc Hoang, and Keshav Pingali. 2018. A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms (PVLDB), Vol. 12.

[28]

Oded Green and David A. Bader. 2013. Faster Betweenness Centrality Based on Data Structure Experimentation. Procedia Computer Science 18 (2013), 399 -- 408. 2013 International Conference on Computational Science.

[29]

Stephan Holzer and Roger Wattenhofer. 2012. Optimal Distributed All Pairs Shortest Paths and Applications. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC '12). ACM, New York, NY, USA, 355--364.

Digital Library

[30]

Q. S. Hua, M. Ai, H. Jin, D. Yu, and X. Shi. 2017. Distributively Computing Random Walk Betweenness Centrality in Linear Time. In 2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). 764--774.

[31]

Q. S. Hua, H. Fan, M. Ai, L. Qian, Y. Li, X. Shi, and H. Jin. 2016. Nearly Optimal Distributed Algorithm for Computing Betweenness Centrality. In 36th ICDCS. 271--280.

[32]

Qiang-Sheng Hua, Haoqiang Fan, Lixiang Qian, Ming Ai, Yangyang Li, Xuanhua Shi, and Hai Jin. 2016. Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications. In SPAA '16. 439--441.

Digital Library

[33]

H. Jeong, S. P. Mason, A. L. Barabási, and Z. N. Oltvai. 2001. Lethality and centrality in protein networks. Nature 411 (May 2001).

[34]

S. Jin, Z. Huang, Y. Chen, D. G. Chavarría-Miranda, J. Feo, and P. C. Wong. 2010. A novel application of parallel betweenness centrality to power grid contingency analysis. In IPDPS.

[35]

N. Kourtellis, G. De Francisci Morales, and F. Bonchi. 2016. Scalable online betweenness centrality in evolving graphs. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE). 1580--1581.

[36]

V. Krebs. 2002. Mapping Networks of Terrorist Cells. Connections (2002).

[37]

Christoph Lenzen and Boaz Patt-Shamir. 2013. Fast Routing Table Construction Using Small Messages: Extended Abstract. In Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing (STOC '13). ACM, New York, NY, USA, 381--390.

Digital Library

[38]

Christoph Lenzen and David Peleg. 2013. Efficient Distributed Source Detection with Limited Bandwidth. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC '13). ACM, New York, NY, USA, 375--382.

Digital Library

[39]

Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker Graphs: An Approach to Modeling Networks. J. Mach. Learn. Res. 11 (March 2010), 985--1042. http://dl.acm.org/citation.cfm?id=1756006.1756039

Digital Library

[40]

Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data.

[41]

F. Liljeros, C.R. Edling, L. Amaral, H.E. Stanley, and Y. Åberg. 2001. The web of human sexual contacts. Nature 411 (2001).

[42]

Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

Digital Library

[43]

Kamesh Madduri, David Ediger, Karl Jiang, David A. Bader, and Daniel G. Chavarría-Miranda. 2009. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets. In IPDPS. IEEE, 1--8.

Digital Library

[44]

Fragkiskos D. Malliaros and Michalis Vazirgiannis. 2013. Clustering and community detection in directed networks: A survey. Physics Reports 533, 4 (2013), 95 -- 142.

[45]

Danupon Nanongkai. 2014. Distributed Approximation Algorithms for Weighted Shortest Paths. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing (STOC '14). ACM, New York, NY, USA, 565--573.

Digital Library

[46]

Donald Nguyen and Keshav Pingali. 2011. Synthesizing concurrent schedulers for irregular algorithms. In Proc. Intl Conf. Architectural Support for Programming Languages and Operating Systems (ASPLOS '11). 333--344.

Digital Library

[47]

David Peleg. 2000. Distributed Computing: A Locality-sensitive Approach. SIAM, Philadelphia, PA, USA.

[48]

David Peleg, Liam Roditty, and Elad Tal. 2012. Distributed Algorithms for Network Diameter and Girth. In ICALP'12. 660--672.

Digital Library

[49]

David Peleg and Vitaly Rubinovich. 2000. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM J. Comput. 30, 5 (May 2000), 1427--1442.

Digital Library

[50]

Matteo Pontecorvi and Vijaya Ramachandran. 2018. Distributed Algorithms for Directed Betweenness Centrality and All Pairs Shortest Paths. (2018). http://arxiv.org/abs/1805.08124

[51]

The Lemur Project. 2013. The ClueWeb12 Dataset. http://lemurproject.org/clueweb12/

[52]

Dimitrios Prountzos and Keshav Pingali. 2013. Betweenness Centrality: Algorithms and Implementations. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '13). ACM, New York, NY, USA, 35--46.

Digital Library

[53]

Edgar Solomonik, Maciej Besta, Flavio Vella, and Torsten Hoefler. 2017. Scaling Betweenness Centrality Using Communication-efficient Sparse Matrix Multiplication. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC '17). ACM, New York, NY, USA, Article 47, 14 pages.

Digital Library

[54]

Edgar Solomonik, Devin Matthews, Jeff Hammond, and James Demmel. 2013. Cyclops Tensor Framework: Reducing Communication and Eliminating Load Imbalance in Massively Parallel Contractions. In Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing (IPDPS '13). IEEE Computer Society, Washington, DC, USA, 813--824.

Digital Library

[55]

Dan Stanzione, Bill Barth, Niall Gaffney, Kelly Gaither, Chris Hempel, Tommy Minyard, S. Mehringer, Eric Wernert, H. Tufo, D. Panda, and P. Teller. 2017. Stampede 2: The Evolution of an XSEDE Supercomputer. In Proceedings of the Practice and Experience in Advanced Research Computing 2017 on Sustainability, Success and Impact (PEARC17). ACM, New York, NY, USA, Article 15, 8 pages.

Digital Library

[56]

G. Tan, V. C. Sreedhar, and G. R. Gao. 2011. Analysis and performance results of computing betweenness centrality on IBM Cyclops64. J. Supercomput. 56 (2011). Issue 1.

Digital Library

[57]

Guangming Tan, Dengbiao Tu, and Ninghui Sun. 2009. A Parallel Algorithm for Computing Betweenness Centrality. In Proceedings of the 2009 International Conference on Parallel Processing (ICPP '09). IEEE Computer Society, Washington, DC, USA, 340--347.

Digital Library

[58]

Leslie G. Valiant. 1990. A bridging model for parallel computation. Commun. ACM 33, 8 (1990), 103--111.

Digital Library

[59]

W. Wang and C. Y. Tang. 2013. Distributed computation of node and edge betweenness on tree graphs. In 52nd Conf. on Decis. and Contr. 43--48.

[60]

K. You, R. Tempo, and L. Qiu. 2017. Distributed Algorithms for Computation of Centrality Measures in Complex Networks. Trans. on Autom. Contr. 62, 5 (2017), 2080--2094.

[61]

Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma. 2016. Gemini: A Computation-centric Distributed Graph Processing System. In Proceedings of the 12th USENIX Conference on Operating Systems Design and Implementation (OSDI'16). USENIX Association, Berkeley, CA, USA, 301--316. http://dl.acm.org/citation.cfm?id=3026877.3026901

Digital Library

Cited By

Tang JGao MXiao YLi CChen Y(2024)EGGPU: Enabling Efficient Large-Scale Network Analysis with Consumer-Grade GPUsProceedings of the Third International Workshop on Social and Metaverse Computing, Sensing and Networking10.1145/3698387.3699997(25-30)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3698387.3699997
Meng LShao YYuan LLai LCheng PLi XYu WZhang WLin XZhou J(2024)A Survey of Distributed Graph Algorithms on Massive GraphsACM Computing Surveys10.1145/3694966Online publication date: 5-Sep-2024
https://dl.acm.org/doi/10.1145/3694966
Zhang TGao YZhao JChen LJin LYang ZCao BFan JChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Efficient Exact and Approximate Betweenness Centrality Computation for Temporal GraphsProceedings of the ACM Web Conference 202410.1145/3589334.3645438(2395-2406)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645438
Show More Cited By

Index Terms

A round-efficient distributed betweenness centrality algorithm
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Approximating betweenness centrality
WAW'07: Proceedings of the 5th international conference on Algorithms and models for the web-graph

Betweenness is a centrality measure based on shortest paths, widely used in complex network analysis. It is computationally-expensive to exactly determine betweenness; currently the fastest-known algorithm by Brandes requires O(nm) time for unweighted ...
A Parallel Algorithm for Computing Betweenness Centrality
ICPP '09: Proceedings of the 2009 International Conference on Parallel Processing

In this paper we present a multi-grained parallel algorithm for computing betweenness centrality, which is extensively used in large-scale network analysis. Our method is based on a novel algorithmic handling of access conflicts for a CREW PRAM ...
Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
Algorithms and Computation
Abstract
We consider the all pairs all shortest paths (APASP) problem, which maintains the shortest path dag rooted at every vertex in a directed graph with positive edge weights. For this problem we present a decremental algorithm (that supports the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming

February 2019

472 pages

ISBN:9781450362252

DOI:10.1145/3293883

General Chair:
Jeff Hollingsworth
University of Maryland
,
Program Chair:
Idit Keidar
Technion, Israel

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication Notes

Badge change: Article originally badged under Version 1.0 guidelines https://www.acm.org/publications/policies/artifact-review-badging

Publication History

Published: 16 February 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Qualifiers

Research-article

Funding Sources

Conference

PPoPP '19

Sponsor:

PPoPP '19: 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

February 16 - 20, 2019

District of Columbia, Washington

Acceptance Rates

PPoPP '19 Paper Acceptance Rate 29 of 152 submissions, 19%;

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
1,049
Total Downloads

Downloads (Last 12 months)192
Downloads (Last 6 weeks)17

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tang JGao MXiao YLi CChen Y(2024)EGGPU: Enabling Efficient Large-Scale Network Analysis with Consumer-Grade GPUsProceedings of the Third International Workshop on Social and Metaverse Computing, Sensing and Networking10.1145/3698387.3699997(25-30)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3698387.3699997
Meng LShao YYuan LLai LCheng PLi XYu WZhang WLin XZhou J(2024)A Survey of Distributed Graph Algorithms on Massive GraphsACM Computing Surveys10.1145/3694966Online publication date: 5-Sep-2024
https://dl.acm.org/doi/10.1145/3694966
Zhang TGao YZhao JChen LJin LYang ZCao BFan JChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Efficient Exact and Approximate Betweenness Centrality Computation for Temporal GraphsProceedings of the ACM Web Conference 202410.1145/3589334.3645438(2395-2406)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645438
Xu YZhang MWu RLi LZhou X(2024)Efficient processing of coverage centrality queries on road networksWorld Wide Web10.1007/s11280-024-01248-527:3Online publication date: 12-Apr-2024
https://doi.org/10.1007/s11280-024-01248-5
Manoharan VRamachandran V(2024)Computing Replacement Paths in the CONGEST ModelStructural Information and Communication Complexity10.1007/978-3-031-60603-8_23(420-437)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_23
Menguc KYilmaz A(2024)Improving model performance of shortest‐path‐based centrality measures in network models through scale spaceConcurrency and Computation: Practice and Experience10.1002/cpe.808236:14Online publication date: 26-Mar-2024
https://doi.org/10.1002/cpe.8082
Zheng ZDu BZhao CXie P(2023)Path Merging Based Betweenness Centrality Algorithm in Delay Tolerant NetworksIEEE Journal on Selected Areas in Communications10.1109/JSAC.2023.331007141:10(3133-3145)Online publication date: Oct-2023
https://doi.org/10.1109/JSAC.2023.3310071
Zheng ZZhao CXie PDu B(2023)Galliot: Path Merging Based Betweenness Centrality Algorithm on GPUIEEE INFOCOM 2023 - IEEE Conference on Computer Communications10.1109/INFOCOM53939.2023.10229018(1-10)Online publication date: 17-May-2023
https://doi.org/10.1109/INFOCOM53939.2023.10229018
Sengupta SPeri SAggarwal VGupta A(2022)A Heuristic for Constructing Minimum Average Stretch Spanning Tree Using Betweenness Centrality2022 30th Euromicro International Conference on Parallel, Distributed and Network-based Processing (PDP)10.1109/PDP55904.2022.00019(67-74)Online publication date: Mar-2022
https://doi.org/10.1109/PDP55904.2022.00019
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

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Table of Contents