# Community detection in graphs - Chapter I: Introduction > 次: [[@2010__PhysRep__Community detection in graphs - Chapter II Communities in real-world networks]] | 全体: [[Community detection in graphs]] ## 要約 コミュニティ検出(community detection)の動機と歴史を導入し、全18節の構成を提示する導入章である。実ネットワークがランダムグラフ(Erdős–Rényi)と異なり次数分布が不均一であるだけでなく、辺の分布も局所的に不均一である——すなわちコミュニティ構造(community structure)/クラスタリングを持つ——ことが、本サーベイ全体の主題として提示される (p.2)。研究の起源は1927年 Stuart Rice の投票パターン分析、1950年 Homans の行列並べ替え、1955年 Weiss & Jacobson の職場グループ分析にまで遡り、2002年の Girvan-Newman 論文をきっかけに物理学者を中心に分野が急速に発展したという歴史的経緯が語られる (p.2-3)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch01-fig01-three-communities.png]] (FIG. 1. 破線で囲まれた3つのコミュニティを持つ単純グラフの模式図 (p.2)。) ## 主要概念 - **コミュニティ構造(community structure)/クラスタリング** — 実ネットワークに特有の、局所的な辺密度の不均一性。本サーベイ全体の主題 (p.2)。 - **粗視化(coarse-graining)** — グラフをより扱いやすい小グラフへ写像する操作。必ずしもコミュニティ単位である必要はない (p.2, 脚注1)。コミュニティ間の関係を俯瞰する縮約表現を得る手段として言及される。 - **グラフ分割(graph partitioning)** — 並列計算のタスク割当問題として言及され、後続章(Section IV.A)で詳述される予定であるとされる (p.3)。 - **エッジ媒介性(edge betweenness)** — Girvan-Newman法の中心となる中心性指標として名前が挙げられる (p.3)。 - **階層組織(hierarchical organization)** — 実ネットワーク一般に見られる入れ子構造。人体や企業のピラミッド組織などが例として挙がり、Herbert Simon の議論が引かれる (p.2)。 ## 主要主張 - 実ネットワークはランダムグラフ(Erdős–Rényi)と異なり次数分布が不均一であるだけでなく、辺の分布も局所的に不均一(コミュニティ構造/クラスタリング)である。これが本サーベイの主題である (p.2)。 - コミュニティ検出の目的は、グラフの位相情報のみからモジュールとその階層組織を同定することである (p.2)。 > "The aim of community detection in graphs is to identify the modules and, possibly, their hierarchical organization, by only using the information encoded in the graph topology." (p.2) - コミュニティ研究の起源は1927年 Stuart Rice の政治団体の投票パターン分析、1950年 Homans の行列並べ替え、1955年 Weiss & Jacobson の職場グループ分析に遡る (p.2)。 - 2002年、Girvan と Newman([[M. E. J. Newman]])の論文がコミュニティ検出分野に大きな活気をもたらし、以降物理学者がスピン模型・最適化・パーコレーション・ランダムウォーク・同期などの手法を持ち込んだ (p.3)。 > "In a seminal paper appeared in 2002, Girvan and Newman proposed a new algorithm, aiming at the identification of edges lying between communities and their successive removal, a procedure that after some iterations leads to the isolation of the communities." (p.2-3) - 実ネットワークは階層組織を持つことが多い(人体、企業のピラミッド組織など、Herbert Simon の議論) (p.2)。 - コミュニティ判定の実用的応用として、Web ミラーサーバの地理的クラスタリングによるサービス性能向上、購買ネットワークでの推薦システム構築、大規模グラフの効率的データ構造化とパス探索、アドホックネットワークでのルーティングテーブル圧縮が挙げられる (p.2-3)。また、頂点の構造的位置(中心的か境界的か)による役割分類は社会・代謝ネットワークで意味を持つとされる (p.2)。 - 章立てロードマップ: II 実ネットワークの例、III 基本概念、IV 伝統的手法、V-X 現代的手法、XI 重複コミュニティ、XII 多重解像度・階層、XIII 動的コミュニティ、XIV-XV 有意性・テスト、XVI-XVII 実クラスタの性質・応用、XVIII 展望、Appendix グラフ理論 (p.3)。 ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[M. E. J. Newman]] — Girvan-Newman アルゴリズム(2002年)の提案者の一人。分野の起爆剤となった手法として言及される。 - 次章: [[@2010__PhysRep__Community detection in graphs - Chapter II Communities in real-world networks]] — 実ネットワークにおけるコミュニティ構造の具体例を扱う。