使用Hadoop/MapReduce查找連接組件

Question

我需要查找大型數據集的連接組件。 （圖爲無向）

一個明顯的選擇是MapReduce。但是我是MapReduce的新手，並且很短時間就無法完成並自行編寫代碼。

我只是想知道是否有任何現有的API相同，因爲它是社交網絡分析中的一個非常常見的問題？

或者至少是否有人知道任何可靠的（經過測試的）源代碼，至少我可以從自己的實現入手？

感謝

Answer 1

我真的不知道，如果一個API可用它有方法來尋找強連通分量。但是，我實現了BFS算法來查找從源節點到圖中所有其他節點的距離（該圖是一個有65萬個節點的有向圖）。

這個想法是在一次迭代中探索每個節點的鄰居（距離爲1）並將縮小的輸出反饋給地圖，直到距離收斂。該映射從每個節點發出可能的最短距離，並且減少以距列表最短距離更新節點。我想建議檢查this out。另外，this could help。這兩個鏈接將爲您提供關於地圖縮減範例中的圖算法的基本概念（如果您已經不熟悉）。實質上，您需要扭轉算法以使用DFS而不是BFS。

Answer 2

我的博客上講述它爲我自己：

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

Answer 3

你可能想看看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壓縮）。

Answer 4

這是一個有點老的問題，但這裏是你想結帳的東西。我們在Spark平臺上使用map-reduce實現了連接組件。

https://github.com/kwartile/connected-component