分散ローカルクラスタリング係数アルゴリズム（MapReduce/Hadoop）

Question

私はMapReduceパラダイムをlocal clustering coefficient algorithmに基づいて実装しました。しかし、私は大きなデータセットや特定のデータセット（ノードの平均度数が高い）では重大な問題に遭遇しました。私は自分のハープのプラットフォームとコードを調整しようとしましたが、結果は不満足でした。いいえ、私は実際にアルゴリズムを変更/改善するために注意を向けていません。私の現在のアルゴリズム（擬似コード）は以下の通りです

foreach(Node in Graph) { 
    //Job1 
    /* Transform edge-based input dataset to node-based dataset */ 

    //Job2 
    map() { 
    emit(this.Node, this.Node.neighbours) //emit myself data to all my neighbours 
    emit(this.Node, this.Node) //emit myself to myself 
    } 

    reduce() { 
    NodeNeighbourhood nodeNeighbourhood; 
    while(values.hasNext) { 
     if(myself) 
     this.nodeNeighbourhood.setCentralNode(values.next) //store myself data 
     else 
     this.nodeNeighbourhood.addNeighbour(values.next) //store neighbour data 
    } 

    emit(null, this.nodeNeighbourhood) 
    } 

    //Job3 
    map() { 
    float lcc = calculateLocalCC(this.nodeNeighbourhood) 
    emit(0, lcc) //emit all lcc to specific key, combiners are used 
    } 

    reduce() { 
    float combinedLCC; 
    int numberOfNodes; 
    while(values.hasNext) { 
     combinedLCC += values.next; 
    } 

    emit(null, combinedLCC/numberOfNodes); // store graph average local clustering coefficient 
    } 
} 

コードの詳細は少しです。有向グラフの場合、隣接データはノードIDおよびOUTエッジ宛先ID（データサイズを小さくする）に制限され、無向はノードIDおよびエッジ宛先IDにもなります。ソートとマージバッファは、1.5 GBに増加したマージ明らかにJOB2は、アルゴリズム全体の実際の問題であることがわかる80

ストリームされています。それはソート/コピー/マージする必要がある大量のデータを生成します。これは、基本的に、特定のデータセットのアルゴリズム性能を殺します。誰かがアルゴリズムを改善する方法について私を導くことができますか（私は、各ノードが "処理"されるまで反復的なJob2 ["プロセス" N個のノードからN個のノードだけを作成することを考えていましたが、 。私の意見では、パフォーマンスを犠牲にする高価なソート/マージプロセスを避けるために、Job2のマップ出力を減らす必要があります。

IはまたGiraphプラットフォームに対して同じアルゴリズム（ならびに3つのジョブ、同じ「通信」パターン、また、「JOB2」問題）を実装しています。しかし、Giraphはメモリ内のプラットフォームであり、同じ "問題のある"データセットのアルゴリズムはOutOfMemoryExceptionを引き起こします。

コメント、発言、ガイドラインについては感謝します。

---

UPDATE

私は "大幅に" アルゴリズムを変更するつもりです。私はこの記事を見つけましたCounting Triangles。

コードが実装されたら、ここで私の意見と詳細なコードを投稿します（このアプローチが成功する場合）。最後に

---

UPDATE_2

私は（ヤフー紙が記事内のリンクを介して使用可能である）私のニーズにのNodeIterator ++アルゴリズムを「修正」終了しました。残念ながら、私はパフォーマンスの改善を見ることができますが、最終結果は私が望むほど良くはありません。私が到達した結論は、私にとって利用可能なクラスターが、これらの特定のデータセットに対してLCC計算を実行可能にするには小さすぎるということです。だから問題は残るか、むしろ進化する。利用可能なリソースが限られているLCCや三角形を計算するための効率的な分散/順次アルゴリズムを知っている人はいますか？ （私がNodeIterator ++アルゴリズムが悪いと言っているわけではありません。私には利用可能なリソースだけでは不十分です）。論文で

Answer 1

「大規模なグラフアルゴリズムのためのMPIでのMapReduce」と著者らは、トライアングルカウントのMapReduceの実装の素敵な説明を与えます。この用紙はhttp://www.sciencedirect.com/science/article/pii/S0167819111000172から入手できますが、用紙にアクセスするにはアカウントが必要な場合があります。 （私はサブスクリプションのために支払われた大学システムにいるので、すでに支払っているためにアクセスできるものは決してわかりません）。

三角形を数える別の方法があります。グラフがかなり濃密でないと、効率が低下する可能性があります。まず、グラフの隣接行列を作成します。次に、A^3を計算します（行列の乗算をかなり簡単に並列処理できます）。次に、A^3の（i、i）項目を合計し、その答えを6で割る。それは、A^kのi、j項目がiからの長さkの数を数えるので、三角形の数を与える私たちは長さ3の散歩しか見ていないので、私は3つのステップの後でiで始まり、3つのステップの後で終わる散歩は三角です... 6の倍率でオーバーカウントします。これは、行列のサイズあなたのグラフが疎な場合は、エッジゲルのサイズに比べて非常に大きくなります。