Skip to content
検索結果に戻る

コミュニティ検出 — ネットワークにおけるグラフクラスタリング

提唱者
Louvain: Blondel et al. (2008); Leiden: Traag et al. (2019); Girvan-Newman: Girvan & Newman (2002); Infomap: Rosvall & Bergstrom (2008)
年
2002–2019 (algorithm family)
種類
Graph-partitioning / clustering algorithm family

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

文字サイズ

何をする手法か?

コミュニティ検出は、ネットワーク内の密に接続されたサブグループ(コミュニティ)を発見するグラフ分割アルゴリズムのファミリである。GirvanとNewman (2002) によるモジュラリティ尺度によって最初に形式化されたこの分野は、Louvain法 (Blondel et al., 2008)、Leiden改良法 (Traag et al., 2019)、情報理論的アプローチであるInfomapによって急速に進歩した。すべてのバリアントは同じ質問に答える。すなわち、どのノードがネットワークの他の部分よりもそれ自体の間でより緊密にクラスタリングされるか?

手法の背後にある直感

人々が主に身近なサークル内で話し、時折そこから外に出るような大規模なソーシャルネットワークを想像してほしい。コミュニティ検出は、事前にラベル付けしなくても、それらのサークルを自動的に見つける。アルゴリズムは、内部接続が密で、グループ間の接続が疎になるようにノードをグループに再配置する。これにより、モジュラリティと呼ばれる品質スコア(またはInfomapでは、ネットワーク上のランダムウォークの記述長を最小化する)が最大化される。結果はパーティションである。各ノードは正確に1つのコミュニティに属し、ネットワークを凝集したクラスタのセットとして視覚化できる。

歴史学

ネットワークにおけるコミュニティ構造の研究は、GirvanとNewman (2002) によって定量的基盤が置かれた。彼らは階層的ネットワーク分割のためのツールとしてエッジ媒介性の概念を導入した。NewmanとGirvan (2004) は、標準的な品質基準となったモジュラリティ尺度Qを形式化した。Blondel et al. (2008) はLouvain法を発表した。これは、数百万ノードのネットワークで高品質なコミュニティ検出を実用的にした2フェーズの貪欲最適化である。Traag, Waltman, and van Eck (2019) は、Louvainの構造的な欠陥、すなわち内部的に切断されたコミュニティを生成する可能性があることを特定し、Leidenアルゴリズムを開発してそれを修正し、内部的に接続されたパーティションを保証した。並行して、RosvallとBergstrom (2008) はInfomapを開発した。これは、コミュニティ検出を圧縮問題として再構築する。すなわち、ネットワーク上のランダムウォークの記述長を最小化するパーティションを見つける。

使うべき場面

コミュニティ検出は、ネットワーク(少なくとも約20ノード)があり、グループを事前に指定せずに潜在的なグループ構造を発見したい場合に適切である。探索的、記述的、および分類の目的に適しており、二項または連続のエッジ重みデータ、および横断的および縦断的なネットワークデータを含む。ノード属性や正規分布は必要ない。この方法は、コミュニティの数が不明な場合に特に適している。ネットワークが小さすぎる(20ノード未満)場合は、記述的ネットワーク統計が好ましい。結果はエッジ重みの定義とネットワーク密度に敏感であるため、これらの選択には慎重な検討が必要である。

限界と注意点

  • モジュラリティ最大化は局所最適解に弱く、実行ごとに結果が異なる可能性があり、複数回の実行で最良の結果を報告する必要がある。
  • 解像度の限界により、大規模ネットワークの非常に小さなコミュニティがマージされ、細かい構造がマスクされる可能性がある。
  • 結果はエッジ重みの定義方法に敏感であり、異なる重み付けスキームは意味的に異なるパーティションをもたらす可能性がある。
  • Girvan-NewmanはO(m²n)の複雑さを持ち、大規模ネットワークには実用的ではない。スケールのためにはLouvainまたはLeidenが好ましい。

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

強み

  • コミュニティの数を事前に指定する必要がない — パーティションサイズはデータから決定される。
  • 大規模ネットワークにスケーリング可能:LouvainとLeidenはほぼ線形時間で実行され、数百万ノードのネットワークにも実用的である。
  • Leidenは、Louvainの切断されたコミュニティという欠点を修正し、内部的に接続された、凝集したコミュニティを保証する。
  • データに対する分布仮定なしに、無重みおよび重み付きネットワークの両方に適用可能。

応用

  • 科学分野をマッピングするための引用ネットワークおよび共著ネットワークにおける研究クラスターの特定。
  • 生物学におけるタンパク質間相互作用ネットワークにおける機能モジュールの検出。
  • 行動分析のためのソーシャルメディアおよびコミュニケーションネットワークにおけるユーザーコミュニティの発見。
  • 凝集した顧客グループを明らかにするためのビジネスおよびマーケティングにおける顧客ネットワークのセグメンテーション。
  • インフラストラクチャ、輸送、またはサプライチェーンネットワークにおける構造ブロックの発見。

使い方

使い方

1

入力は、ノードがエンティティ(人、ウェブページ、タンパク質、引用)を表し、エッジがそれらの間の関係を表すグラフである。エッジは有向または無向であり、重みを持つことができる。隣接構造(どのノードがどのように強く接続されているか)は、アルゴリズムが必要とする唯一の入力である。ノードのラベル、クラス、または外部属性は必要ないが、後で結果を検証するために使用できる。

2

各アルゴリズムは、ノードをコミュニティに割り当てる初期設定から始まる。LouvainとLeidenでは、すべてのノードが独自のシングルトンコミュニティとして開始される。Girvan-Newmanは、完全なネットワークから開始し、最も高い媒介中心性を持つエッジを反復的に削除し、徐々にコミュニティ構造を明らかにする。Infomapは、ネットワークのランダムウォーク記述から開始し、コード長を最小化するために2レベルマップを使用してそれをエンコードする。

3

コアフェーズは、モジュラリティQ(Louvain、Leiden)を最大化するパーティション、またはマップ方程式コード長(Infomap)を最小化するパーティションを検索する。Louvainは、Qを改善するために単一ノードをコミュニティ間で貪欲に移動させ、次にコミュニティをスーパーノードに集約して繰り返す。これは2フェーズプロセスであり、うまくスケーリングするが、切断されたコミュニティを生成する可能性がある。Leidenは、集約前にローカル移動と改良ステップを使用して、各コミュニティが内部的に接続されていることを保証することにより、Louvainを改良する。Girvan-Newmanはエッジを反復的に削除し、分割のデンドログラムを記録する。デンドログラムの任意のカットでQを最大化するパーティションが選択される。コミュニティの数はアルゴリズム自体から現れる。事前に指定する必要はない。

4

最終パーティションの品質は、モジュラリティスコアQで要約される。Qは-0.5から1の範囲である。約0.3〜0.5を超える値は、意味のあるコミュニティ構造の兆候と見なされることが多い。モジュラリティ最適化は局所最適解に陥る可能性があるため、アルゴリズムを複数回実行し、最良の結果を取ることが標準的な実践である。パーティションは、視覚的に検査され、利用可能なノード属性または真のラベルに対してクロスバリデーションされ、実質的に意味があることを確認する。

よくある落とし穴

  • アルゴリズムを1回実行して、単一の結果を真実として扱うこと — 常に複数回実行し、最良のモジュラリティを報告するか、アンサンブルメソッドを使用すること。
  • 解像度の限界を無視すること:大規模で疎なネットワークでは、小さくても実際のコミュニティが警告なしに大きなコミュニティに吸収される可能性がある。
  • 20ノード未満のネットワークにモジュラリティベースのアルゴリズムを適用すること — そのスケールではコミュニティ構造を確実に識別できない。
  • 高いモジュラリティスコアを、確認された実世界のコミュニティ構造と混同すること。モジュラリティはパーティションの品質測定値であり、コミュニティが統計的に有意であるかどうかの推論テストではない。

よくある質問

どのアルゴリズムを選択すべきか — Louvain、Leiden、Girvan-Newman、またはInfomap?

Louvainは、大規模ネットワーク向けの高速で広く使用されているベースラインである。Leidenは、正確性が重要な場合の推奨選択肢である。なぜなら、内部的に接続されたコミュニティを保証し、通常はより高いモジュラリティを達成するからである。Girvan-Newmanは階層的探索に有用なデンドログラムを生成するが、大規模ネットワークには遅すぎる。Infomapは、ランダムウォーカーの経路が意味を持つ有向またはフローベースのネットワークに適している。

事前にコミュニティ数を指定する必要はありますか?

いいえ。Louvain、Leiden、Infomapは、ネットワーク構造からコミュニティ数を自動的に決定する。Girvan-Newmanは完全なデンドログラムを生成し、そこから任意の数のコミュニティを読み取ることができる。通常はQを最大化するパーティションが選択される。

見つかったコミュニティが意味のあるものであることをどのように知ることができますか?

モジュラリティスコアQは、データ内部の品質測定値を提供する。約0.3〜0.5を超える値は、自明でないコミュニティ構造を示唆する。それ以上に、コミュニティはドメイン知識、ノード属性、または外部ラベルに対して検証されるべきである。高いQだけでは、社会学的または生物学的な有意性を証明するものではない。

実行ごとに結果が異なる場合はどうなりますか?

モジュラリティ最適化はヒューリスティックであり、特にLouvainでは、異なる実行でわずかに異なるパーティションが得られる可能性がある。アルゴリズムを複数回(大規模ネットワークでは少なくとも10〜100回)実行し、最も高いQを持つパーティションを報告すること。Leidenは、その改良ステップがより徹底的であるため、Louvainよりも安定しているが、繰り返し実行することは依然として良い実践である。

関連する手法

参考文献

  1. Blondel, V.D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. (2008). Fast Unfolding of Communities in Large Networks. Journal of Statistical Mechanics, 2008(10), P10008.

    DOI 文献を開く
    コピーしました。
  2. Traag, V.A., Waltman, L. & van Eck, N.J. (2019). From Louvain to Leiden: Guaranteeing Well-Connected Communities. Scientific Reports, 9, 5233.

    出版物の文献を開く
    コピーしました。