# Community detection in graphs ## 概要 Santo Fortunato による、グラフのコミュニティ検出(クラスタリング)に関する当時最も網羅的なサーベイ論文である。問題設定の定義から、伝統的手法・モジュラリティ最適化・スペクトル法・動的手法・統計的推論に基づく手法・重複コミュニティ検出まで、統計物理学者が考案した技術を中心に手法群を横断し、有意性判定・ベンチマークによる手法比較・実ネットワークへの応用までを一本で通観する。103 ページ・42 図からなり、Physics Reports 誌に掲載された。 > [!abstract] 概要(abstract の日本語訳) > 現代のネットワーク科学は、複雑系の理解に大きな進展をもたらした。実世界のシステムを表すグラフの最も重要な特徴の一つがコミュニティ構造、すなわちクラスタリングである。これは、頂点がクラスタへと組織化され、同一クラスタ内の頂点を結ぶ辺が多く、異なるクラスタ間の頂点を結ぶ辺が相対的に少ない状態を指す。このようなクラスタ、すなわちコミュニティは、グラフの中で比較的独立した区画とみなすことができ、例えば人体における組織や臓器と同様の役割を果たす。コミュニティ検出は、システムがしばしばグラフとして表現される社会学・生物学・計算機科学において、極めて重要である。この問題は非常に難しく、過去数年にわたり学際的な科学者集団が多大な努力を注いできたにもかかわらず、いまだ十分には解決されていない。本稿では、問題の主要な構成要素の定義から、開発された大半の手法の紹介(統計物理学者が考案した技術に特に焦点を当てる)、クラスタリングの有意性や手法の検証・比較方法といった重要な論点の議論、実ネットワークへの応用の記述に至るまで、本主題の徹底的な解説を試みる。 ## 書誌情報 - 著者: [[Santo Fortunato]](ISI Foundation, Complex Networks and Systems Lagrange Laboratory, Torino, Italy) - 媒体: Physics Reports 486 (2010), pp. 75–174 - arXiv: 0906.0612(v1: 2009-06-03, v2: 2010-01-25) - URL: https://arxiv.org/abs/0906.0612 - 構成: 全 18 節(節番号は原文のローマ数字) + 付録 A(Elements of Graph Theory) ## 構成と主要テーマ → [[@2010__PhysRep__Community detection in graphs - Chapter I Introduction]] — 序論。コミュニティ検出問題の背景と定義 → [[@2010__PhysRep__Community detection in graphs - Chapter II Communities in real-world networks]] — 社会・生物・技術・多部ネットワークでのコミュニティ構造の実例 → [[@2010__PhysRep__Community detection in graphs - Chapter III Elements of Community Detection]] — 計算複雑性、コミュニティの定義(局所的・大域的)、分割の定義 → [[@2010__PhysRep__Community detection in graphs - Chapter IV Traditional methods]] — グラフ分割、階層的クラスタリング、スペクトルクラスタリング → [[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]] — Girvan–Newman アルゴリズムとその派生 → [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]] — モジュラリティ最適化(貪欲法・焼きなまし法・スペクトル最適化)とその限界 → [[@2010__PhysRep__Community detection in graphs - Chapter VII Spectral Algorithms]] — スペクトル法によるコミュニティ検出 → [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] — スピンモデル・ランダムウォーク・同期に基づく動的手法 → [[@2010__PhysRep__Community detection in graphs - Chapter IX Methods based on statistical inference]] — 生成モデルとブロックモデリング、モデル選択 → [[@2010__PhysRep__Community detection in graphs - Chapter X Alternative methods]] — 局所モジュラリティ等の代替手法 → [[@2010__PhysRep__Community detection in graphs - Chapter XI Methods to find overlapping communities]] — クリークパーコレーション法ほか重複コミュニティ検出 → [[@2010__PhysRep__Community detection in graphs - Chapter XII Multiresolution methods and cluster hierarchy]] — マルチ解像度手法と階層構造 → [[@2010__PhysRep__Community detection in graphs - Chapter XIII Detection of dynamic communities]] — 時間発展するコミュニティの検出 → [[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]] — クラスタリングの統計的有意性 → [[@2010__PhysRep__Community detection in graphs - Chapter XV Testing Algorithms]] — ベンチマーク(GN・LFR)とアルゴリズム比較指標 → [[@2010__PhysRep__Community detection in graphs - Chapter XVI General properties of real clusters]] — 実ネットワークにおけるコミュニティの一般的性質 → [[@2010__PhysRep__Community detection in graphs - Chapter XVII Applications on real-world networks]] — 生物・社会・その他ネットワークへの応用 → [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]] — 総括と展望 → [[@2010__PhysRep__Community detection in graphs - Appendix A Elements of Graph Theory]] — グラフ理論の基礎(定義・行列・モデルグラフ) ## 位置づけと影響 Girvan–Newman(2002)によるモジュラリティの提案以降、爆発的に増加したコミュニティ検出手法群を、統計物理学者の視点から系統的に整理した決定版サーベイであり、2010年代のコミュニティ検出研究における標準的な参照点になった。特にベンチマーク(LFR)とアルゴリズム比較の方法論を確立した点で、後続研究の評価基準に大きな影響を与えている。 ## 関連 ## 出典 - Fortunato, S., Community detection in graphs, Physics Reports 486 (2010) 75–174. https://arxiv.org/abs/0906.0612