1. 首页
  2. 问答
  3. 使用Hadoop/MapReduce查找连接组件

使用Hadoop/MapReduce查找连接组件

2012-05-20 45 views
8

我需要查找大型数据集的连接组件。 （图为无向）使用Hadoop/MapReduce查找连接组件

一个明显的选择是MapReduce。但是我是MapReduce的新手，并且很短时间就无法完成并自行编写代码。

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

或者至少是否有人知道任何可靠的（经过测试的）源代码，至少我可以从自己的实现入手？

感谢

来源

2012-05-20 Shatu

回答

3

我真的不知道，如果一个API可用它有方法来寻找强连通分量。但是，我实现了BFS算法来查找从源节点到图中所有其他节点的距离（该图是一个有65万个节点的有向图）。

这个想法是在一次迭代中探索每个节点的邻居（距离为1）并将缩小的输出反馈给地图，直到距离收敛。该映射从每个节点发出可能的最短距离，并且减少以距列表最短距离更新节点。我想建议检查this out。另外，this could help。这两个链接将为您提供关于地图缩减范例中的图算法的基本概念（如果您已经不熟悉）。实质上，您需要扭转算法以使用DFS而不是BFS。

来源

2012-05-21 00:15:57

8

我的博客上讲述它为我自己：

http://codingwiththomas.blogspot.de/2011/04/graph-exploration-with-hadoop-mapreduce.html

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

我写了一个连接的组件算法的MapReduce在这里：（Mindist搜索）

https://github.com/thomasjungblut/tjungblut-graph/tree/master/src/de/jungblut/graph/mapreduce

另外一个BSP版本的Apache哈马可以在这里找到：

https://github.com/thomasjungblut/tjungblut-graph/blob/master/src/de/jungblut/graph/bsp/MindistSearch.java

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

http://hama.apache.org/

http://apache.org/hama/mail-lists.html

来源

2012-05-21 07:57:18

+0

至于现在，我并不关心复杂性。我正在做一个概念验证的事情，所以现在运行时间并不重要。实际上我缺乏时间，所以我没有选择正常的JAVA/C编程来实现它，而只是希望得到一个现有的实现，不管它有多脏。现在，除了Hadoop/MapReduce以外，我无法查找任何其他方法。 谢谢 – Shatu

+0

所以你在MapReduce中进行原型设计？有趣。我在博客中的解决方案就像它在那里一样工作，并且它是由我认识的许多其他人进行的生产测试。不要犹豫，拿走它。 –

2

你可能想看看Pegasus project卡内基梅隆大学。它们使用MapReduce提供了一种高效且优雅的实现。他们还提供二进制文件，样本和非常详细的文档。

实现本身是基于U康在2009年提出的广义迭代矩阵向量乘法（GIM-V）。

PEGASUS: A Peta-Scale Graph Mining System - 实施和 观察ü康，Charalampos E. Tsourakakis，克里斯托斯·法劳索斯在数据挖掘 IEEE国际会议（2009年ICDM）

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

来源

2014-04-08 21:25:49

相关问题

 相关问题