7

karypis Lab ( http://glaros.dtc.umn.edu/gkhome/metis/metis/overview )によって実装されている METIS のような有名なグラフ パーティション アルゴ ツールがあることは知っています。

しかし、Neo4jに保存されているグラフを分割する方法はありますか? または、Neo4j のデータをダンプし、METIS 入力形式に合わせてノードとエッジの形式を手動で変換する必要がありますか?

4

2 に答える 2

8

新しくて興味深いアルゴリズムに関しては、これは決して網羅的でも最先端でもありませんが、私が最初に見る場所は次のとおりです。

特定のアルゴリズム: DiDiC (Distributed Diffusive Clustering) - 論文で一度使用しました ( Partitioning Graph Databases )

  • すべてのノードを反復処理し、各ノードに対してすべてのネイバーを取得して、「いくつかのユニット」の一部をすべてのネイバーに分散させます
  • 実装が簡単。
  • 決定論的にできる
  • 反復 - (Pregel のスーパー ステップのように) 反復に基づいているため、いつでも停止できます。理論的には、長く放置するほど結果は良くなります (ただし、場合によっては、特定のグラフ形状では不安定になる可能性があります)。
  • これを実装したとき、最大 400 万ノードまで、最大 30 GB の RAM を搭載したマシンで 100 回の反復を実行しました。完了までに 2 日もかかりませんでした。

特定のアルゴリズム: EvoCut「進化するセットを使用してローカルでスパース カットを見つける」 - Microsoft のローカル確率的アルゴリズム -これらの論文に関連する

  • 実装が難しい
  • ローカル アルゴリズム - BFS のようなアクセス パターン (ランダム ウォーク)
  • その論文を読んでからしばらく経ちましたが、きれいな抽象化に基づいて構築されていたことを覚えています。
    • EvoNibble (プラグ可能 - 現在のクラスターに追加する近隣の量を決定します
    • EvoCut (ローカル クラスターを見つけるために EvoNibble を複数回呼び出します)
    • EvoPartition (グラフ全体を分割するために EvoCut を繰り返し呼び出します)
  • 決定論的ではない

一般的なアルゴリズム ファミリー:階層グラフ クラスタリング

高レベルから：

  • ノードを集約ノードに折りたたんでグラフを粗くする
    • 粗大化戦略が選択可能
  • 粗い/小さいグラフでクラスターを見つける
    • クラスタリング戦略が選択可能
  • 段階的にグラフをデコアーズし、各ステップでクラスタリングを調整します
    • 精製戦略は選択可能です

ノート：

  • グラフの変化が遅い (または結果が最新である必要がない) 場合は、1 回 (またはまれに) 粗くしてから、粗くしたグラフを操作して計算を節約することができます。
  • 推奨する具体的なアルゴリズムがわからない

一般的な制限- いくつかのクラスタリング アルゴリズムが行うこと:

  • ノード タイプが認識されない - つまり、すべてのノードが同等に扱われる
  • 認識されない関係タイプ - つまり、すべての関係が同等に扱われる
  • 関係の方向性が認められていない - つまり、方向性のないものとして扱われる関係
于 2013-08-08T14:35:14.693 に答える
4

過去に METIS と Neo4j を個別に使用していたので、Neo4j から METIS ファイルを生成するツールを知りません。そうは言っても、そのようなツールを作成するのは簡単な作業であり、コミュニティへの大きな貢献になるはずです。

METIS を Neo4j と統合する別の方法として、JNI を介して C++ から METIS を Neo4j に接続する方法があります。ただし、トランザクション、同時実行などを処理する必要があるため、これはより複雑になります。

グラフを分割するというより一般的な問題については、合理的な努力をすれば、より知られている単純なアルゴリズムのいくつかを実装することは十分に可能です。

于 2013-08-08T13:46:05.383 に答える