A Round-Efficient Distributed Betweenness Centrality Algorithm
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.9× 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.
Tue 19 FebDisplayed time zone: Guadalajara, Mexico City, Monterrey change
14:00 - 15:15 | |||
14:00 25mTalk | Semantics-Aware Scheduling Policies for Synchronization Determinism Main Conference Qi Zhao North Carolina State University, Zhengyi Qiu North Carolina State University, Guoliang Jin North Carolina State University DOI | ||
14:25 25mTalk | Proactive Work Stealing for Futures Main Conference Kyle Singer Washington University in St. Louis, Yifan Xu Washington University in St. Louis, I-Ting Angelina Lee Washington University in St. Louis DOI | ||
14:50 25mTalk | A Round-Efficient Distributed Betweenness Centrality Algorithm Main Conference Loc Hoang University of Texas at Austin, USA, Matteo Pontecorvi Nokia Bell Labs, Roshan Dathathri University of Texas at Austin, USA, Gurbinder Gill University of Texas at Austin, USA, Bozhi You Xi'an Jiaotong University, Keshav Pingali University of Texas at Austin, USA, Vijaya Ramachandran University of Texas at Austin DOI | ||