19

MapReduceパラダイムベースのローカルクラスタリング係数アルゴリズムを実装しました。ただし、より大きなデータセットまたは特定のデータセット（ノードの平均次数が高い）で深刻な問題が発生しました。私はHadoopプラットフォームとコードを調整しようとしましたが、結果は満足のいくものではありませんでした（控えめに言っても）。いいえ、実際にアルゴリズムを変更/改善することに注意を向けました。以下は私の現在のアルゴリズム（擬似コード）です

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.5Gbに増加し、ストリームをマージします80。

Job2がアルゴリズム全体の実際の問題であることがはっきりとわかります。ソート/コピー/マージする必要のある大量のデータを生成します。これは基本的に、特定のデータセットのアルゴリズムのパフォーマンスを低下させます。誰かがアルゴリズムを改善する方法を教えてもらえますか（反復Job2を作成することを考えていました[すべてのノードが「処理」されるまで、各反復でNからMノードのみを「処理」します]が、今のところこのアイデアを放棄しました） 。私の意見では、パフォーマンスを低下させるコストのかかるソート/マージプロセスを回避するために、Job2マップ出力を減らす必要があります。

また、Giraphプラットフォームに同じアルゴリズム（3つのジョブ、同じ「通信」パターン、「Job2」の問題）も実装しました。ただし、Giraphはメモリ内プラットフォームであり、同じ「問題のある」データセットのアルゴリズムによりOutOfMemoryExceptionが発生します。

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

アップデート

アルゴリズムを「大幅に」変更します。私はこの記事「三角形を数える」を見つけました。

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

UPDATE_2

結局、NodeIterator ++アルゴリズムを自分のニーズに合わせて「変更」することを終了しました（Yahooの論文は記事のリンクから入手できます）。残念ながら、パフォーマンスの向上は見られますが、最終的な結果は思ったほど良くありません。私が到達した結論は、私が利用できるクラスターは小さすぎて、これらの特定のデータセットに対してLCC計算を実行できないということです。したがって、問題は残ります。むしろ、それは進化します。利用可能なリソースが限られているLCCまたは三角形を計算するための効率的な分散/シーケンシャルアルゴリズムを知っている人はいますか？（NodeIterator ++アルゴリズムが悪いと言っているわけではありません。私が利用できるリソースが十分ではないと単純に述べています）。

4

1 に答える 1

1

「大規模なグラフ アルゴリズムのための MPI での MapReduce」という論文で、著者は Triangle Counting の MapReduce 実装について適切に説明しています。論文はhttp://www.sciencedirect.com/science/article/pii/S0167819111000172で入手できますが、論文にアクセスするにはアカウントが必要な場合があります。(私は購読料が支払われている大学のシステムを使用しているので、彼らは既に支払いを済ませているため、私がアクセスできるのは私だけではありません。) 著者は論文のドラフトを個人の Web サイトに投稿している可能性があります。

三角形を数える別の方法がありますが、グラフがかなり密集していない限り、おそらくはるかに効率的ではありません。まず、グラフの隣接行列 A を作成します。次に、A^3 を計算します (行列の乗算を並列で簡単に実行できます)。次に、A^3 の (i,i) エントリを合計し、答えを 6 で割ります。A^k の i,j エントリは、i から k 歩く長さの数をカウントするため、三角形の数が得られます。長さ 3 の歩行のみを見ているので、i で始まり、3 ステップ後に i で終わる歩行は三角形です... 6 倍の過大評価です。行列のサイズがグラフがまばらな場合、エッジリストのサイズに比べて非常に大きくなります。

于 2014-11-04T21:44:54.960 に答える