2

すべて接続されている約 10K から 100K のノードのネットワークがあります。これらのノードは通常、コミュニティのクラスターにグループ化され、それらの間には多くのエッジで強く接続され、ハブなどがあります。コミュニティ間には、コミュニティをブリッジ/接続するいくつかのエッジを持つノードがあります。これらのデータセットは隣接行列にあります

私はスペクトル クラスタリングを試しました ( Ding et al 2001 ) が、大規模なデータ セットでは非常に遅く、多くのあいまいさ (別のクラスターへの唯一のブリッジ ルートではないブリッジ - 他のコミュニティが機能する可能性があるブリッジ) があると動作が停止するようです。代替プロキシ ルート)。

モジュール性最適化のためのニューマンアルゴリズムなど、マーテロットのいくつかの方法を試しましたが、その努力に安定性最適化機能を組み込んでいませんでした (それは重要でしょうか?)。クラスターがランダム グラフ (ER グラフ) によって作成される合成データ セットでは、メソッドは機能しますが、ネストされた階層がある実際のデータ セットでは、結果が散らばっています。ただし、スタンドアロンの視覚化アプリケーション/ツールを使用すると、ブリッジは明らかです。

どのような方法を試してみることをお勧め/アドバイスしますか? 私はMATLABを使用しています。

4

1 に答える 1

6

正確に何をしたいですか？コミュニティ、またはそれらの間のブリッジを検出しますか? これらは 2 つの異なる問題です。コミュニティを取得したら、2 つの異なるコミュニティからノードを接続するエッジを特定するのは簡単です。それで、コミュニティを検出したいと思います。

この目的のために実際には何千ものメソッドがあり、そのうちのいくつかは、あなたが引用したものや一般化された Louvain アルゴリズム(これもモジュール性最適化に基づいています) など、Matlab で実装されています。ただし、それらのほとんどは、InfoMap (データ圧縮パラダイムに基づく)、WalkTrap (ランダム ウォーク ベースの距離を使用したクラスタリング)、Markov Cluster (いくつかの伝播メカニズムをシミュレートする)、およびリストなどの C または C++ プログラムとして利用できます。に行く...

これらのツールは、コミュニティ構造の概念を多かれ少なかれ異なる方法で形式化しており、同じネットワークに適用すると、異なる (推定された) コミュニティ構造につながる可能性があります。そしてもちろん、コミュニティが異なれば、架け橋も異なります。したがって、問題は、データに適した方法を選択する方法を知ることです。あなたには先入観があるようです学習しているネットワークに関する知識を使用して選択する必要があります (プログラミング言語ではなく)。たとえば、明示的に述べていなくても、階層的なコミュニティ構造を探しているようです。すべてのツールがこの種の構造を検出できるわけではありません。同様に、1 つのノードが同時に複数のコミュニティに属する可能性があると思われる場合は、たとえばCFinder (クリーク パーコレーションに基づく) を使用して、重複するコミュニティを探すことを検討する必要があります。

コミュニティ検出のこの優れたレビューをご覧になることをお勧めします。方法を選択できる興味深い情報が見つかるかもしれません:グラフでのコミュニティ検出。また、プログラミングの観点から、igraph ライブラリ(C、R、および Python で利用可能) を試すことをお勧めします。これには、いくつかの標準的なコミュニティ検出ツールが含まれています。データでそれらを試して、何が得られるかを確認できます。

于 2013-05-20T16:11:07.833 に答える