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

Question

我需要为庞大的数据集找到连接的组件.(图形未指向)

一个显而易见的选择是MapReduce.但我是MapReduce的新手,我很安静,没时间去挑选它并自己编写代码.

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

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

谢谢

Answer 1

我为自己写了一篇博文:

但MapReduce不适合这些Graph分析.为此更好地使用BSP(批量同步并行),Apache Hama在Hadoop HDFS之上提供了一个很好的图形API.

我在这里用MapReduce编写了一个连通组件算法:( Mindist搜索)

此外,还可以在此处找到Apache Hama的BSP版本:

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

Answer 2

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

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

我建议检查一下。另外，这可能会有所帮助。这两个链接将为您提供有关地图缩减范例中图算法的基本概念（如果您已经不熟悉）。本质上，您需要改变算法以使用 DFS 而不是 BFS。