graph - 使用 Hadoop/MapReduce 查找连接的组件

Question

我需要为庞大的数据集找到连接的组件。（图是无向的）

一个明显的选择是 MapReduce。但我是 MapReduce 的新手，我很安静，没有时间去学习它并自己编写代码。

我只是想知道是否有任何现有的 API，因为它是社交网络分析中非常常见的问题？

或者至少如果有人知道任何可靠的（经过试验和测试的）来源，我至少可以自己开始实施？

谢谢

score 9 · Accepted Answer

我为自己写了一篇博客：

但是 MapReduce 不太适合这些 Graph 分析的东西。最好使用 BSP（批量同步并行），Apache Hama 在 Hadoop HDFS 之上提供了一个很好的图形 API。

我在这里用 MapReduce 编写了一个连接组件算法：（Mindist search）

也可以在这里找到 Apache Hama 的 BSP 版本：

实现并不像在 MapReduce 中那么困难，而且速度至少快 10 倍。如果您有兴趣，请查看 TRUNK 中的最新版本并访问我们的邮件列表。

score 3 · Accepted Answer

我真的不知道是否有可用的 API 具有查找强连接组件的方法。但是，我实现了 BFS 算法来查找图中从源节点到所有其他节点的距离（该图是一个有 6500 万个节点的有向图）。

这个想法是在一次迭代中探索每个节点的邻居（距离为 1），并将 reduce 的输出反馈给 map，直到距离收敛。map 发出与每个节点可能的最短距离，并 reduce 更新与列表距离最短的节点。

我建议检查一下。此外，这可能会有所帮助。这两个链接将为您提供有关 map reduce 范式中图算法的基本概念（如果您还不熟悉）。本质上，您需要扭曲算法以使用 DFS 而不是 BFS。

score 2 · Accepted Answer

您可能想查看卡内基梅隆大学的Pegasus 项目。它们使用 MapReduce 提供了高效且优雅的实现。他们还提供二进制文件、示例和非常详细的文档。

该实现本身基于 U Kang 在 2009 年提出的广义迭代矩阵向量乘法 (GIM-V)。

PEGASUS: A Peta-Scale Graph Mining System - 实施和观察 U Kang、Charalampos E. Tsourakakis、Christos Faloutsos 在 IEEE 国际数据挖掘会议 (ICDM 2009)

编辑：官方实现实际上仅限于 21 亿个节点（节点 ID 存储为整数）。我正在 github ( https://github.com/placeiq/pegasus ) 上创建一个 fork 来分享我的补丁和其他增强功能（例如 Snappy 压缩）。

score 1 · Accepted Answer

这是一个有点老的问题，但这里有一些你想检查的东西。我们在 Spark 平台上使用 map-reduce 实现了连接组件。

4 回答 4