0

何百万ものエッジとノードを持つ巨大な無向グラフでグラフ クラスタリングを実行したいと考えています。グラフは、いくつかのノード (複数のクラスターに関連付けることができるあいまいなノードの一種) によってのみ結合された異なるクラスターでほぼクラスター化されています。2 つのクラスターの間にエッジはほとんどないか、ほとんどありません。この問題は、グラフの頂点カット セットを見つけることとほぼ同じですが、グラフを多くのコンポーネントに分割する必要があるという 1 つの例外があります (その数は不明です)。(この図https://docs.google.com/file/dを参照してください) /0B7_3zLD0X​​dtAd3ZwMFAwWDZuU00/edit?pli=1 )

それらの間でいくつかのノードを共有するさまざまな強く接続されたコンポーネントのようであり、それらのノードを削除してそれらの強く接続されたコンポーネントを分離することになっています。エッジは重み付けされますが、この問題はグラフ内の構造を見つけることに似ているため、エッジの重みは関係ありません。(問題を考える別の方法は、いくつかの点で互いに接触している固体球を視覚化することです。球はそれらの強く接続されたコンポーネントであり、接触点はそれらのあいまいなノードです)

私は何かのプロトタイプを作成しているので、自分でグラフ クラスタリング アルゴリズムを取り上げて、可能な限り最良のものを選択する時間はありません。さらに、私の場合、異なるクラスターがエッジではなくノードを共有するため、エッジではなくノードをカットするソリューションが必要です。

この問題または関連する問題に対処する研究論文、ブログはありますか? または、誰もがこの問題の解決策を考え出すことができますか?

何百万ものノードとエッジが関係しているため、ソリューションのMapReduce実装が必要になります。そのための入力、リンクもありますか?

直接使用できる MapReduce の現在のオープン ソース実装はありますか?

この問題は、オンライン ソーシャル ネットワークで頂点を削除してコミュニティを見つけることに似ていると思います。

4

2 に答える 2

1

あなたの問題はそれほど単純ではありません。NP完全なクリーク問題に関連しているのではないかと心配しているので、「クラスター間にほとんどエッジがない」というステートメントを何らかの形で定量化しない限り、あなたの問題は依然として非常に難しいかもしれません. しかし、あなたの立場で私がすることは、ノードを次の種類の準ニューラルネットと見なす、汚い、貪欲なアプローチを試すことです。

各頂点には、入力、出力、および入力値 (入力の合計) を出力値に変換するシグモイド活性化関数があると考えられます。出力値は、これが重要であると考えていますが、複製されてすべてのネイバーに送信されるのではなく、ネイバー間で均等に分割されます。これに加えて、ネットワークのグローバルな減衰パラメーターによって定義される、ニューロンの活動の対数減衰 (自己抑制、それ自体への抑制接続) を定義します。

ここで、非常に高い減衰パラメーターを使用してアクティビティ 0.5 (アクティビティ範囲は 0 ～ 1) から開始するすべてのニューロンでシミュレーションを開始します。これにより、すべてのニューロンが 0 の状態ですばやく安定します。次に、定常状態の結果がゼロ以外の安定したアクティビティを持つ最初のクリークを生成するまで、減衰パラメーターを徐々に減らします。

問題は、次に何をするかです。1 つの可能性は、見つかったクリークをグラフから差し引き、すべてのクリークが見つかるまで同じプロセスを再度実行することです。この貪欲なアプローチは、あなたが言うようにグラフが実際に適切に動作している (実際にはほぼクラスター化されている) 場合に成功する可能性がありますが、そうでない場合は予期しない結果につながる可能性があります。別の可能性は、見つかったクリークに他のクリークに反発する (相互抑制) ユニークなクリークの匂いを与え、2 番目のクリークが見つかるまでアルゴリズムを再実行し、他のすべてのクリークに反発する別のクリークの匂いを与えることです。独自の割り当てられた匂いがあります。

これは、私がこれについて持っているのと同じくらい多くの大きなアイデアになると思います。

重要なのは、一般的なケース (おそらく NP 完全) でこの問題を解決することはおそらく不可能であるため、グラフが持つ特別なプロパティを利用する必要があるということです。つまり、アルゴリズムが遭遇するケースの 99% を解決するまで、しばらくパラメーターをいじる必要があります。あなたが遭遇する実際のデータセットで長い実験をしなければ、あなたの質問に数値的に正確な答えを出すことはできないと思います.

于 2012-05-26T09:05:52.383 に答える
0

何百万ものノードとエッジが関係しているため、ソリューションの MapReduce 実装が必要になります。そのための入力、リンクもありますか？

私の経験では、ここで Map/Reduce を使用することが本当に有利かどうかは疑問です。ノードの最初の 10^6 オーダーは実際にはそれほど大きくなく [クラスタリングを検討しているため、ハイパー接続されていないグラフでも]、[ハードウェア/ソフトウェアを既にセットアップしていない限り] Map/Reduce を使用するオーバーヘッドそれのために]あなたの問題はそれだけの価値がないからです。

Map/Reduce は、クラスタリングの問題を解決したら、同様の分析で各クラスターを処理したい場合に、はるかにうまく機能します。基本的に、タスクを並行して実行できる比較的分離されたサブタスクに分割できる場合。もちろん、これは複数のレイヤーにカスケードできます。

比較的似たような状況で、私は最初に自分のグラフをグラフ データベースにモデル化し (Neo4J を使用しましたが、強くお勧めします)、それに対して分析とクエリを実行しました。このソリューションがホワイト ボード フレンドリーであることに驚かれることでしょう。大規模に結合および接続されたクエリでさえ、特にわずか数百万ノードの規模でほぼ瞬時に実行されます。たとえば、分離の程度に基づいてフィルター処理された分析を実行した後、共通点を一覧表示できます。

于 2012-05-26T16:42:22.190 に答える