約 100 の igraph オブジェクトのリストがあり、典型的なオブジェクトには約 700 の頂点と 3500 のエッジがあります。
同点の可能性が高い頂点のグループを特定したいと思います。私の計画は、混合モデルを使用して、頂点とグループの属性を使用して、グループ内の頂点がいくつあるかを予測することです。
私のプロジェクトの他の側面に反応したい人もいるかもしれませんが、それは素晴らしいことですが、私が最も興味を持っているのは、頂点をグループ化するための igraph の関数に関する情報です。これらのコミュニティ検出アルゴリズムに出くわしましたが、それらの長所と短所、または他の機能が私の場合に適しているかどうかはわかりません. こちらのリンクも見ましたが、igraph に固有のものではありません。アドバイスありがとうございます。
以下は、現在 igraph に実装されているコミュニティ検出アルゴリズムに関する短い要約です。
edge.betweenness.communityは、エッジ間のスコア (つまり、特定のエッジを通過する最短パスの数) の降順でエッジが削除される階層的な分解プロセスです。これは、多くの場合、あるグループから別のグループに移動するための唯一のオプションであるため、異なるグループを接続するエッジが複数の最短パスに含まれる可能性が高いという事実によって動機付けられます。この方法では良い結果が得られますが、エッジ間の計算の計算が複雑であり、エッジを削除するたびに中間性のスコアを再計算する必要があるため、非常に時間がかかります。頂点が最大 700 個、辺が最大 3500 個のグラフは、このアプローチで分析できるグラフのサイズの上限付近です。もう一つの欠点は、edge.betweenness.communityは完全な樹状図を作成しますが、最終的なグループを取得するために樹状図のどこを切り取ればよいかについてのガイダンスは提供しません。したがって、それを決定するには他の尺度を使用する必要があります (たとえば、各レベルのパーティションのモジュール性スコア)。デンドログラム)。
fastgreedy.communityも別の階層的アプローチですが、トップダウンではなくボトムアップです。モジュール性と呼ばれる品質機能を貪欲に最適化しようとします。最初は、すべての頂点が個別のコミュニティに属し、各マージが局所的に最適になるようにコミュニティが繰り返しマージされます (つまり、現在のモジュール性の値が最大に増加します)。モジュール性をこれ以上高めることができなくなると、アルゴリズムは停止するため、樹形図だけでなくグループ化もできます。この方法は高速であり、調整するパラメーターがないため、通常、最初の概算として試行される方法です。ただし、解像度の制限に悩まされることが知られています。つまり、特定のサイズのしきい値を下回るコミュニティ (私の記憶が正しければノードとエッジの数による) は、常に隣接するコミュニティとマージされます。
walktrap.communityランダムウォークに基づくアプローチです。一般的な考え方は、グラフでランダム ウォークを実行すると、特定のコミュニティの外につながるエッジがわずかしかないため、ウォークが同じコミュニティ内にとどまる可能性が高くなるということです。Walktrap は、3-4-5 ステップの短いランダム ウォーク (そのパラメーターの 1 つに応じて) を実行し、これらのランダム ウォークの結果を使用して、個別のコミュニティを のようなボトムアップ方式でマージしますfastgreedy.community。ここでも、モジュール性スコアを使用して樹状図を切り取る場所を選択できます。これは、fast greedy アプローチよりも少し遅くなりますが、もう少し正確です (元の出版物によると)。
spinglass.communityいわゆるポッツモデルに基づく統計物理学からのアプローチです。このモデルでは、各粒子 (つまり頂点) はc個のスピン状態のいずれかになり、粒子間の相互作用 (つまりグラフのエッジ) は、どの頂点のペアが同じスピン状態にとどまることを好むか、どの頂点のペアがどのペアを好むかを指定します。異なるスピン状態を持つことを好みます。次に、モデルは特定のステップ数でシミュレートされ、最終的に粒子のスピン状態がコミュニティを定義します。その結果は次のとおりです。1) cを 200 に設定することもできますが、最終的にはコミュニティがc個を超えることはありません。目的には十分な値です。2) c未満の場合があるスピン状態の一部が空になる可能性があるため、最終的にコミュニティ。3) ネットワークの完全に離れた (または切断された) 部分にあるノードが異なるスピン状態を持つことは保証されません。これは、切断されたグラフのみで問題になる可能性が高いため、心配する必要はありません。この方法は特に高速ではなく、決定論的でもありませんが (シミュレーション自体のため)、クラスター サイズを決定する調整可能な解像度パラメーターがあります。スピングラス法の変形では、ネガティブ リンク (つまり、エンドポイントが異なるコミュニティにあることを好むリンク) も考慮に入れることができます。
leading.eigenvector.communityモジュール性関数を再度最適化するトップダウンの階層的アプローチです。各ステップで、グラフは 2 つの部分に分割され、分離自体によってモジュール性が大幅に向上します。分割は、いわゆるモジュール性行列の主要な固有ベクトルを評価することによって決定されます。また、密に接続されたグループがさらに分割されるのを防ぐ停止条件もあります。固有ベクトルの計算が関係しているため、ARPACK 固有ベクトル ソルバーが不安定な縮退グラフでは機能しない可能性があります。縮退していないグラフでは、少し遅くなりますが、fast greedy メソッドよりも高いモジュール性スコアが得られる可能性があります。
label.propagation.communityは、すべてのノードにk 個のラベルのいずれかが割り当てられる単純なアプローチです。次に、メソッドは反復的に処理を進め、各ノードがその隣接ノードの最も頻繁なラベルを同期的に取得するように、ノードにラベルを再割り当てします。各ノードのラベルがその近傍で最も頻度の高いラベルの 1 つである場合、メソッドは停止します。これは非常に高速ですが、初期構成 (ランダムに決定される) に基づいて異なる結果が得られるため、メソッドを多数回 (たとえば、グラフの場合は 1000 回) 実行してから、コンセンサス ラベル付けを構築する必要があります。面倒。
igraph 0.6 には、情報理論の原則に基づく最先端の Infomap コミュニティ検出アルゴリズムも含まれます。グラフ上のランダム ウォークの最短の記述長を提供するグループ化を構築しようとします。記述長は、ランダム ウォークのパスをエンコードするために必要な頂点あたりの期待ビット数によって測定されます。
とにかく、私はおそらく最初の概算としてfastgreedy.communityまたはwalktrap.communityを使用し、これらの2つが何らかの理由で特定の問題に適していないことが判明した場合は、他の方法を評価します.
さまざまなコミュニティ検出アルゴリズムの概要については、http ://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/ を参照してください。
特に、InfoMAP アルゴリズムは便利な最近の新機能です (有向グラフもサポートしています)。