我必须从已知的图形连通分量并行计算中找到最佳算法。
这里是我的数据和计算机架构的简要概述:
- 我可以访问一个包含数千个 处理器(内存不共享，但我希望应该有 单个节点中有足够的内存来评估我对整个节点的需求 数据)。
- 我的图的边数与顶点数之比很小(大约 5)
- 我希望大多数连通分量都非常小(2-3 个顶点)
- 但是，将会有具有数百万个顶点的非常大的组件(甚至占总顶点数的 10%)。
我读过有关计算图的连通分量的并行算法。正如我所注意到的，其中一些基于序列化案例的经典 BFS 方法。老实说，我对这些算法的数量有点迷茫。谁能给我一些建议，哪种算法最适合我的目的？
最佳答案
Ligra对于单机多核实现，它要么是最先进的，要么接近它。它应该能够毫无问题地处理您的图表。
Connected Components at Scale via Local Contractions ，由我的同事 Jakub Łącki、Vahab Mirrokni 和 Michał Włodarczyk 编写，是 MapReduce 算法的最新技术水平(至少，据我所知)。我们已经在比您大一千倍的图表上使用它。
关于multithreading - 连通分量的并行算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54057160/