[解決済み] igraphにおけるコミュニティ検出アルゴリズムの違いは何ですか？

質問

典型的なオブジェクトは約700の頂点と3500のエッジを持つ、約100のIGGオブジェクトのリストを持っています。

私は、結びつきがより起こりやすい頂点のグループを識別したいと思います。 私の計画は、頂点とグループの属性を使用して、頂点がグループ内の結びつきをどれだけ持っているかを予測するために、混合モデルを使用することです。

いくつかの人々は私のプロジェクトの他の側面に反応したいかもしれません、それは素晴らしいことですが、私が最も興味を持っていることは、頂点をグループ化するためのigraphの関数についての情報です。 私は、以下のものに出会いました。 コミュニティ検出アルゴリズム が、その利点と欠点、あるいは他の関数が私のケースに適しているかどうか、よくわかりません。 私はリンク先を見ました はこちら も見ましたが、これらはigraphに特化したものではありません。 アドバイスありがとうございました。

どのように解決するのですか？

現在igraphに実装されているコミュニティ検出アルゴリズムについて、簡単にまとめてみました。

• edge.betweenness.community は階層的な分解処理で、エッジはエッジのbetweennessスコア（つまり、与えられたエッジを通る最短パスの数）の降順で削除されます。これは、異なるグループをつなぐエッジは複数の最短経路に含まれる可能性が高いという事実に基づくもので、多くの場合、あるグループから別のグループに行くための唯一の選択肢であるためである。この方法は良い結果をもたらしますが、エッジの間 隔の計算が複雑で、エッジを削除するたびに間 隔のスコアを再計算しなければならないため、非常に時間がかかり ます。頂点数700、エッジ数3500のグラフは、この手法で解析可能なグラフの上限サイズにあたります。もう一つの欠点は edge.betweenness.community は完全なデンドログラムを構築し、最終的なグループを得るためにデンドログラムをどこで切断するかのガイダンスを与えないので、それを決定するために他の指標（例えば、デンドログラムの各レベルでのパーティションのモジュール性スコア）を使用しなければならないでしょう。

• fastgreedy.community はもうひとつの階層的アプローチですが、トップダウンではなくボトムアップです。モジュール性と呼ばれる品質関数を貪欲に最適化しようとするものである。初期状態では、すべての頂点は別々のコミュニティに属しており、各マージが局所的に最適となるように（すなわち、モジュール性の現在値の最大の増加をもたらすように）コミュニティは反復的にマージされる。アルゴリズムは、これ以上モジュラリティを増加させることができないときに停止するので、デンドログラムだけでなくグループ化も得られます。この方法は高速で、調整するパラメータがないため、通常、第一近似として試される方法である。つまり、与えられたサイズ閾値（私の記憶が正しければ、ノードとエッジの数に依存する）以下のコミュニティは、常に近隣のコミュニティとマージされることになるのです。

• walktrap.community は、ランダムウォークに基づくアプローチです。一般的な考え方は、グラフ上でランダムウォークを実行すると、与えられたコミュニティの外につながるエッジがわずかしかないため、ウォークは同じコミュニティ内にとどまる可能性が高くなる、というものです。Walktrapは3-4-5ステップの短いランダムウォークを実行し（パラメータの1つに依存）、これらのランダムウォークの結果を使用して、ボトムアップ方式で別々のコミュニティをマージします。 fastgreedy.community . ここでも、モジュール化スコアを用いてデンドログラムを切断する場所を選択することができます。これは高速な貪欲アプローチより少し遅いですが、また少し正確です（原著論文によると）。

• spinglass.community は統計物理学からのアプローチで、いわゆるPottsモデルに基づいています。このモデルでは、各粒子 (すなわち頂点) は以下のうちのひとつになります。 c スピン状態のいずれかになり、粒子間の相互作用（グラフのエッジ）は、どのペアの頂点が同じスピン状態にあることを好み、どのペアが異なるスピン状態にあることを好むかを指定します。そして、このモデルは与えられたステップ数だけシミュレーションされ、最終的に粒子のスピン状態がコミュニティを定義します。その結果は以下の通りである。1)2個以上存在することはない c を設定することができますが、最終的には c を200まで設定することができ、目的には十分であると思われます。2) c を下回る可能性があります。これは、いくつかのスピン状態が空になるためです。3) ネットワークの完全に離れた（または切断された）部分のノードが異なるスピン状態を持つことは保証されない。これは、切断されたグラフのみの問題である可能性が高いので、気にする必要はないでしょう。この方法は特に高速ではなく、決定論的でもありません（シミュレーション自体のため）。しかし、クラスタサイズを決定する調整可能な解像度パラメータを持ちます。spinglass法の変形は、負のリンク（すなわち、端点が異なるコミュニティにあることを好むリンク）を考慮することも可能です。

• leading.eigenvector.community は、モジュール性関数を再度最適化するトップダウン型の階層的アプローチである。各ステップにおいて、グラフは、分離自体がモジュール性の大幅な増加をもたらすような方法で2つの部分に分割される。分割は、いわゆるモジュール性行列の先頭の固有ベクトルを評価することによって決定され、また、強く結合したグループがそれ以上分割されないようにする停止条件もある。固有ベクトル計算を伴うため、ARPACK固有ベクトルソルバーが不安定な縮退グラフでは動作しないことがあります。非縮退グラフでは、少し遅いですが、高速な貪欲法よりも高いモジュール性スコアが得られる可能性があります。

• label.propagation.community は単純な方法で、各ノードには k のラベルのいずれかが割り当てられる。その後、この方法は反復的に進み、各ノードがその近傍の最も頻度の高いラベルを同期的に取るように、ノードにラベルを再割り当てする。この方法は、各ノードのラベルがその近傍で最も頻度の高いラベルの1つとなった時点で停止する。非常に高速であるが、初期設定（ランダムに決定される）により結果が異なるため、この方法を多数回（例えばグラフで1000回）実行し、コンセンサスラベルを構築する必要があるが、これは面倒な作業となる可能性がある。

igraph 0.6では、情報理論的な原則に基づく、最先端のInfomapコミュニティ検出アルゴリズムも含まれます。これは、グラフ上のランダムウォークに対して最短の記述長を提供するグループ化を構築しようとするもので、記述長はランダムウォークのパスをエンコードするために必要な頂点ごとのビット数の予想値で測定されます。

とにかく、私はおそらく fastgreedy.community または walktrap.community を第一近似とし、何らかの理由でこの2つが特定の問題に適していないことが判明した場合に、他の方法を評価します。