PPoPP 2019
Sat 16 - Wed 20 February 2019 Washington, DC, United States
Tue 19 Feb 2019 14:50 - 15:15 at Salon 12/13 - Session 7: Scheduling Chair(s): Jidong Zhai

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 Feb

Hide past events
PPoPP-2019-papers
14:00 - 15:15: Main Conference - Session 7: Scheduling at Salon 12/13
Chair(s): Jidong ZhaiTsinghua University
PPoPP-2019-papers14:00 - 14:25
Talk
Qi ZhaoNorth Carolina State University, Zhengyi QiuNorth Carolina State University, Guoliang JinNorth Carolina State University
DOI
PPoPP-2019-papers14:25 - 14:50
Talk
Kyle SingerWashington University in St. Louis, Yifan XuWashington University in St. Louis, I-Ting Angelina LeeWashington University in St. Louis
DOI
PPoPP-2019-papers14:50 - 15:15
Talk
Loc HoangUniversity of Texas at Austin, USA, Matteo PontecorviNokia Bell Labs, Roshan DathathriUniversity of Texas at Austin, USA, Gurbinder GillUniversity of Texas at Austin, USA, Bozhi YouXi'an Jiaotong University, Keshav PingaliUniversity of Texas at Austin, USA, Vijaya RamachandranUniversity of Texas at Austin
DOI