巨大なデータセットの連結成分を見つける必要があります。(無向のグラフ)
明らかな選択肢の 1 つは MapReduce です。しかし、私は MapReduce の初心者であり、それを取り上げて自分でコーディングする時間はありません。
ソーシャルネットワーク分析で非常に一般的な問題であるため、同じための既存のAPIがあるかどうか疑問に思っていましたか?
または、少なくとも私が自分で実装を開始できる信頼できる(試行およびテストされた)ソースを誰かが知っている場合は?
ありがとう
6917 次
4 に答える
9
私は自分のためにそれについてブログを書きました：
http://codingwiththomas.blogspot.de/2011/04/graph-exploration-with-hadoop-mapreduce.html
しかし、MapReduce は、これらのグラフ分析には適していません。そのためには BSP (一括同期並列) を使用することをお勧めします。Apache Hama は、Hadoop HDFS の上に優れたグラフ API を提供します。
MapReduce を使用した連結成分アルゴリズムをここに記述しました: (Mindist search)
https://github.com/thomasjungblut/tjungblut-graph/tree/master/src/de/jungblut/graph/mapreduce
また、Apache Hama の BSP バージョンは次の場所にあります。
実装は MapReduce ほど難しくなく、少なくとも 10 倍高速です。興味がある場合は、TRUNK の最新バージョンをチェックアウトし、メーリング リストにアクセスしてください。
于 2012-05-21T07:57:18.457 に答える
3
強く接続されたコンポーネントを見つけるためのメソッドを持つ API が利用できるかどうかはよくわかりません。しかし、ソース ノードからグラフ内の他のすべてのノードまでの距離を見つけるために BFS アルゴリズムを実装しました (グラフは 6500 万ノードの有向グラフでした)。
アイデアは、距離が収束するまで、1 回の反復で各ノードの近隣ノード (距離 1) を探索し、reduce の出力をマップにフィードバックすることでした。マップは各ノードから可能な最短距離を出力し、reduce はリストからの最短距離でノードを更新します。
これをチェックすることをお勧めします。また、これは役立つ可能性があります。これらの 2 つのリンクは、map reduce パラダイムのグラフ アルゴリズムに関する基本的な考え方を示します (まだ慣れていない場合)。基本的に、BFS の代わりに DFS を使用するには、アルゴリズムをひねる必要があります。
于 2012-05-21T00:15:57.690 に答える
2
カーネギー メロン大学のPegasus プロジェクトを参照してください。これらは、MapReduce を使用して効率的で洗練された実装を提供します。また、バイナリ、サンプル、および非常に詳細なドキュメントも提供しています。
実装自体は、2009 年に U Kang によって提案された Generalized Iterative Matrix-Vector multiplication (GIM-V) に基づいています。
PEGASUS: ペタスケールのグラフ マイニング システム- 実装と観察 U Kang、Charalampos E. Tsourakakis、Christos Faloutsos データ マイニングに関する IEEE 国際会議 (ICDM 2009)
編集: 公式の実装は、実際には 21 億のノードに制限されています (ノード ID は整数として格納されます)。github ( https://github.com/placeiq/pegasus ) でフォークを作成して、パッチやその他の機能強化 (例: Snappy 圧縮) を共有しています。
于 2014-04-08T21:25:49.383 に答える