连通分量的并行算法

Question

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

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

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

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

Answer 1

对于单机多核实现来说，Ligra要么是最先进的，要么是接近最先进的。它应该能够毫无问题地处理你的图表。

\n\n

我的同事 Jakub \xc5\x81\xc4\x85cki、Vahab Mirrokni 和 Micha\xc5\x82 W\xc5\x82odarczyk通过 Local\nContractions 大规模连接组件，是最先进的（至少，我知道）关于）MapReduce 算法。我们已经在比你的大一千倍的图表上使用了它。

\n