Skip to content
検索結果に戻る

モジュラリティ分析

提唱者
Newman, M. E. J. & Girvan, M.
年
2004
種類
Community detection / graph partitioning
系統
Network science

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

モジュラリティ分析は、2004年にNewmanとGirvanによって形式化されたネットワーク科学の手法であり、エッジが偶然期待されるよりもグループ内に集中しているかどうかを測定することにより、グラフ内のコミュニティ構造を検出します。そのスカラー品質指数Qは、ノードを凝集クラスターに分割するアルゴリズムをガイドし、ソーシャル、生物学的、および技術的ネットワークにおけるコミュニティ検出のための最も広く採用されているフレームワークとなっています。

手法の背後にある直感

もしランダムにネットワークのすべてのエッジを再配線し、各ノードの次数を維持した場合、実際のコミュニティがないヌルモデルが得られます。モジュラリティは、実際のエッジ分布をこのヌルモデルと比較します。もし分割がヌルモデルが予測するものよりも多くのグループ内エッジを生み出す場合、Qは高くなり、真のコミュニティ構造を示唆します。オプティマイザーは、Qを最大化する分割の空間を探索し、分析者が事前にコミュニティ数を指定する必要なしに、ネットワーク構造が暗示する自然なグループ化を明らかにします。

歴史学

モジュラリティ関数Qは、2004年にNewmanとGirvanによってコミュニティ検出技術のスイートの一部として導入されました。Newmanの2006年のPNAS論文は、モジュラリティ最適化のスペクトルアプローチを形式化し、Louvain法(Blondelら、2008)は大規模最適化を実用的なものにし、社会学、生物学、およびコンピュータサイエンス全体でモジュラリティ分析を普及させました。解像度限界問題は、2007年にFortunatoとBarthélemyによって特定され、Leiden(Traagら、2019)のような改善されたアルゴリズムを動機付けました。これは、接続の悪いコミュニティも修正します。

使うべき場面

関係データセットがグラフとして表現可能で、コミュニティの数を事前に指定せずに凝集サブグループを特定したい場合にモジュラリティ分析を使用します。例えば、ソーシャルネットワーク内の派閥、タンパク質相互作用ネットワーク内の機能モジュール、または引用ネットワーク内のトピッククラスターの検出などです。これは、数十個以上のノードと明らかに非自明なエッジ構造を持つ無向グラフおよび有向グラフに適しています。ネットワークが小さすぎる(約30ノード未満)またはほぼ完全である場合、エッジ重みが単純な二値ヌルモデルが無視する重要な情報を持つ場合、コミュニティが有意に重複することがわかっている場合(重複コミュニティ手法を使用)、または最適化ヒューリスティックではなく統計的にテストされた境界が必要な場合は使用しないでください。

限界と注意点

  • 解像度限界:モジュラリティ最適化は、ネットワークサイズによって設定されたスケールよりも小さいコミュニティの検出に体系的に失敗し、真に異なる小さなモジュールをマージします。
  • NP困難な正確な最適化は、実際には近似しか使用できないことを意味し、確率的アルゴリズムの異なる実行は異なる分割をもたらす可能性があります。
  • ヌルモデルは、構成モデル(Erdos-Renyi様次数分布)を仮定しますが、これは重尾次数分布または階層構造を持つネットワークには不適切である可能性があります。
  • ハードコミュニティ境界は、現実世界の重複メンバーシップを表すことができません。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 事前にコミュニティ数を指定する必要はありません。分割はデータから現れます。
  • 単純なスカラーQを提供し、異なる分割やネットワークの直接的な比較を容易にします。
  • 高速な近似アルゴリズム(Louvain、Leiden)は、数百万ノードにスケールします。
  • 適切な拡張により、無向、有向、および重み付きネットワークに適用可能です。
  • 標準ライブラリ(NetworkX、igraph、Gephi)に広く実装されており、使用の障壁を低くしています。

応用

  • オンラインおよびオフラインのソーシャルネットワークにおけるソーシャル派閥、エコーチェンバー、またはコラボレーションクラスターの検出。
  • タンパク質間相互作用および遺伝子調節グラフなどの生物学的ネットワークにおける機能モジュールの特定。
  • 引用および共著ネットワークにおけるテーマ別または分野別クラスターの明らか化。
  • マーケティングおよびレコメンデーションシステムにおける顧客または製品ネットワークのセグメンテーション。
  • 回復力分析のためのインフラストラクチャネットワーク(電力網、交通網)のパーティショニング。
  • 計算言語学におけるハイパーリンクまたは共起グラフのトピックコミュニティの発見。

使い方

使い方

1

ネットワークは隣接行列A(または同等のエッジリスト)として表され、ここでエントリA_ijはノードiとjが接続されている場合は1、そうでない場合は0です。ノード次数(k_i、k_j)と総エッジ数mは、モジュラリティ計算の入力として計算されます。

2

モジュラリティスコアQは、コミュニティ内のエッジの割合から、構成モデルヌル(次数を維持するランダム再配線)で期待される割合を引いたものとして定義されます。Qは、約-0.5から1の範囲であり、約0.3を超える値は意味のあるコミュニティ構造を示します。

数式
Q = \frac{1}{2m}\sum_{ij}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)
3

すべての可能な分割に対する網羅的な探索はNP困難であるため、実用的なアルゴリズムは最適値を近似します。一般的なアプローチには、Louvain法(貪欲な集約)、Leidenアルゴリズム(修正され高速化されたバリアント)、モジュラリティ行列の固有ベクトルを使用したスペクトル最適化、および焼きなまし法が含まれます。

4

各ノードは、全体の分割に対してQを最大化するコミュニティに割り当てられます。アルゴリズムは通常、階層的なデンドログラムを生成し、粗いスーパーコミュニティから細かいクラスターまで、複数の解像度でコミュニティ構造を検査できます。

5

結果の分割は、最終的なQ値、複数のアルゴリズム実行にわたる安定性チェック、および真のラベルが利用可能な場合は、正規化相互情報などの外部メトリックによって評価されます。低いQまたは実行にわたる不安定な結果は、弱いまたは存在しないコミュニティ構造を示します。

よくある落とし穴

  • 安定性チェックや複数のランダムシードなしに、確率的オプティマイザーの単一実行を受け入れること。
  • 解像度限界を無視し、マージされた大きなコミュニティが実際に均質であると結論付けること。
  • 重み付きネットワークに二値モジュラリティを、エッジ重みを組み込むようにヌルモデルを適応させずに適用すること。
  • Qが0.3を超えることを、ネットワークの種類とサイズを考慮せずに「良い」構造の普遍的なしきい値として扱うこと。
  • 最適化の質(高いQ)と解釈の妥当性を混同すること。コミュニティは依然として実質的に検査される必要があります。

よくある質問

Qの良い値とは何ですか?

Qが約0.3を超えることは、意味のあるコミュニティ構造を示すと一般的に引用されますが、このしきい値はネットワークの種類とサイズに依存します。構造が弱い非常に大きなネットワークではQが0.1近くになることがありますが、解釈可能なクラスターを明らかにすることができます。一方、小さく密なネットワークはQが0.5を超えることがあります。Qだけに頼るのではなく、常にコミュニティを実質的に検査してください。

Qを最大化するためにどのアルゴリズムを使用すべきですか?

Leidenアルゴリズム(Traagら、2019)は現在推奨されるデフォルトです。Louvain法の元のバージョンよりも高速であり、接続の悪いコミュニティを生成する傾向を修正しています。非常に大きなグラフの場合、Louvainは実用的な選択肢です。スペクトル法は、小さなネットワークで再現可能で決定論的な結果が必要な場合に好まれます。

モジュラリティ分析は重複コミュニティを検出できますか?

標準的なモジュラリティ最適化は、各ノードを1つのコミュニティにのみ割り当て、重複を検出できません。ノードが同時に複数のグループに属すると予想される場合は、クリークパーコレーション法や非負行列因子分解アプローチなどの重複コミュニティ手法を使用してください。

解像度限界は私の分析にどのように影響しますか?

モジュラリティ最適化は、約sqrt(m)エッジよりも小さいコミュニティをより大きなものにマージする傾向があります。これは、真の小さなクラスターが大きなネットワークでは見えなくなる可能性があることを意味します。これを軽減するために、解像度パラメータ(Leidenおよび一部のLouvain実装で利用可能)を変更し、複数の解像度値にわたる分割を比較してください。

有向ネットワークにモジュラリティ分析を適用すべきですか?

はい、igraphのようなツールに実装されているように、入次数と出次数の両方を維持する適応されたヌルモデルを使用します。有向グラフに無向モジュラリティを単純に適用すると、関係の非対称性が失われ、誤解を招く分割につながる可能性があります。

関連する手法

参考文献

  1. Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.

    DOI 文献を開く
    コピーしました。
  2. Newman, M. E. J. (2006). Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23), 8577–8582.

    DOI 文献を開く
    コピーしました。