期刊
出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3293883.3295729
关键词
-
资金
- NSF CCF [1320675, 1337217, 1337281, 1406355, 1618425, 1725322]
- DARPA [FA8750-16-2-0004, FA8650-15-C7563]
- XSEDE grant [ACI-1548562, TG-CIE170005]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1337217] Funding Source: National Science Foundation
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1320675, 1618425] Funding Source: National Science Foundation
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.0x and the communication time by 2.8x for the graphs in our test suite. As a result, MRBC is 2.1x faster on average than Brandes BC for real-world web-crawls on 256 hosts.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据