连通部件的并行算法

Question

我必须从已知的图的连通分量并行计算中找到最好的算法。

以下是我的数据和计算机体系结构的简要概述：

• 我可以访问具有数千个处理器的计算集群(内存不是共享的，但我希望单个节点中应该有足够的内存来评估我对整个数据的需求)。
• 我的图有相当小的边数与顶点数之比(约5)
• 我预计大部分连通组件都非常小(2-3个顶点)。
• 然而，也会有数以百万计的顶点组成非常大的分量(甚至占顶点总数的10% )。

我读过关于计算图的连通分量的并行算法。正如我所注意到的，其中一些是基于序列化案例的经典BFS方法。老实说，我对这些算法的数量有点迷茫。有人能给我一些建议吗，哪种算法最适合我的目的？

Answer 1

利格拉要么是最先进的，要么接近它的单机多核实现。它应该能处理你的图表没有问题。

通过局部收缩的规模连通分量，由我的同事JakubŁącki，Vahab Mirrokni，和MichałWłodarczyk，是MapReduce算法的最先进的(至少，我知道)。我们把它用在比你的大一千倍的图表上。