Scaling Betweenness Approximation to Billions of Edges by MPI-based Adaptive Sampling
Scaling Betweenness Approximation to Billions of Edges by MPI-based Adaptive Sampling
复制标题
DOI：
10.1109/ipdps47924.2020.00061
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Alexander van der Grinten;Henning Meyerhenke
中科院分区：
文献类型：
--
作者：
Alexander van der Grinten;Henning Meyerhenke
介数中心性是网络分析中最常用的顶点中心性度量之一。因此，已经设计了许多(顺序和并行)算法来计算或近似介数。最近的算法进步使得在共享内存体系结构上非常有效地近似介数成为可能。然而，对于较大的图，最好的共享内存算法仍然需要数小时的运行时间，特别是对于直径较大或需要较小相对误差的图，本文提出了一种基于MPI的最新共享内存算法的推广，用于介数逼近。该算法是基于自适应采样的，我们的并行化策略同样适用于其他问题的自适应采样算法。在16节点集群上的实验中，考虑到并行化的重点--自适应采样阶段，我们基于MPI的实现比最先进的共享内存实现快了16.1倍。对于完整的算法，我们得到了一个平均值(geom.平均)加速比为现有技术的7.4倍。对于一些以前非常具有挑战性的输入，这种加速比要高得多。因此，我们的算法是第一个在不到10分钟的时间内逼近具有数十亿条边的图的中间中心度的算法，并且具有很高的精度。
Betweenness centrality is one of the most popular vertex centrality measures in network analysis. Hence, many (sequential and parallel) algorithms to compute or approximate betweenness have been devised. Recent algorithmic advances have made it possible to approximate betweenness very efficiently on shared-memory architectures. Yet, the best shared-memory algorithms can still take hours of running time for large graphs, especially for graphs with a high diameter or when a small relative error is required.In this work, we present an MPI-based generalization of the state-of-the-art shared-memory algorithm for betweenness approximation. This algorithm is based on adaptive sampling; our parallelization strategy can be applied in the same manner to adaptive sampling algorithms for other problems. In experiments on a 16-node cluster, our MPI-based implementation is by a factor of 16.1x faster than the state-of-the-art shared-memory implementation when considering our parallelization focus – the adaptive sampling phase – only. For the complete algorithm, we obtain an average (geom. mean) speedup factor of 7.4x over the state of the art. For some previously very challenging inputs, this speedup is much higher. As a result, our algorithm is the first to approximate betweenness centrality on graphs with several billion edges in less than ten minutes with high accuracy.