> 前: [[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]] | 次: [[@2010__PhysRep__Community detection in graphs - Chapter VII Spectral Algorithms]] | 全体: [[Community detection in graphs]] # Community detection in graphs - Chapter VI: Modularity-based methods ## 要約 [[モジュラリティ]] Q は Girvan-Newman 法の樹形図から最終分割を選ぶ停止基準として導入されたが、以後コミュニティ検出手法群の中核的な品質関数になった(p.27)。本章は、モジュラリティを目的関数として最適化するあらゆる手法(貪欲法・焼きなまし・極値最適化・スペクトル法・数理計画法・遺伝的アルゴリズム)を網羅し、モジュラリティ自体の拡張(重み付き・有向・重複・二部グラフ・符号付き)と、解像度限界を中心とする本質的な限界を論じる。章は A. モジュラリティ最適化、B. モジュラリティの修正・拡張、C. モジュラリティの限界、という三部構成を取る。 モジュラリティ最大化は NP 完全であることが証明されており(Brandes et al., 2006)、厳密解は事実上求まらないため、近似アルゴリズム群が発展した(p.27)。 ## 分類軸(taxonomy) ### A. モジュラリティ最適化アルゴリズム - **貪欲最適化(greedy optimization)**: Newman の凝集法(O(n^2))は大規模ネットワークを扱えるが、大きなコミュニティに偏り最適値が悪化しやすい。Clauset et al. のヒープ実装(O(n log^2 n))は現在も超大規模グラフでのモジュラリティ近似の主要手段の一つ。Wakita and Tsurumi は "consolidation ratio" によりバランス化を改良し、Schuetz and Caflisch は複数中心を同時成長させる改良を加えた(p.27-28)。 - **[[Louvain法]](Blondel et al.)**: 階層的な貪欲最適化で O(m) と極めて高速、10^9 辺規模まで扱えるが、局所近傍でのコミュニティ形成が不正確な場合がある(p.28-29)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch06-fig12-louvain-method.png]] (FIG. 12. Blondel et al. の階層的モジュラリティ最適化〈Louvain法〉の2反復の模式図。局所的なノード移動フェーズと、見つかったコミュニティを1ノードに凝集するフェーズを交互に繰り返す。) - **焼きなまし法(simulated annealing)**: 真の最大値に近づけるが低速で、10^4 頂点程度が実用上の限界(Guimerà and Amaral の実装が代表的)(p.29)。 - **極値最適化(extremal optimization, EO)**: Boettcher and Percus が提案し、Duch and Arenas がモジュラリティ最適化に応用。焼きなましに匹敵する精度をより高速(O(n^2 log n))に達成する妥協案(p.29-30)。 - **スペクトル最適化(spectral optimization)**: モジュラリティ行列 B = A - k_i k_j / 2m の最大固有値に対応する固有ベクトルの符号でグラフを二分し、Kernighan-Lin 型の後処理で精度を上げる(Newman)。Sun et al. は頂点移動ステップを追加、Wang et al. / Richardson et al. は複数固有ベクトルによる三分割手法を提案。二分割には強いが多クラスタでは精度が落ちる(p.30-31)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch06-fig13-spectral-modularity.png]] (FIG. 13. Newman のスペクトル最適化。最初の2固有ベクトルによる頂点の平面表現と、直線による分割の模式図。) White and Smyth のスペクトル法(遷移行列 + k-means)や Ruan and Zhang の Kcut は、クラスタ数 K を事前指定し White-Smyth 法を再帰的に適用することで複雑度を抑える(p.32-33)。 - **数理計画法**: Agarwal and Kempe による線形/二次計画定式化、Xu et al. の混合整数計画、Chen et al. の整数線形計画によるクリーク分解は理論的に魅力的だが大規模グラフには計算量的に不向き(p.33-34)。Lehmann and Hansen は平均場焼きなましを用いた(p.34)。 - **遺伝的アルゴリズム**: Tasgin et al. / Liu et al. による最適化も試みられ、既存手法と同程度の性能を出す例がある(p.34)。 ### B. モジュラリティの修正・拡張 - モジュラリティは重み付きグラフ(Eq.35-36)、有向グラフ(Eq.37; Arenas et al.)、重み付き有向グラフ(Eq.38)へ自然に拡張できる(p.34-35)。 - 有向モジュラリティには欠陥があり、Kim et al. は PageRank に着想を得た拡散ベースの代替を提案した。Rosvall and Bergstrom も同様の批判を行っている(p.35)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch06-fig14-directed-modularity-problem.png]] (FIG. 14. 有向モジュラリティの問題点。Arenas et al. の定義では、有向流のある状況と無い状況の2つを区別できないことを示す図。) - 重複コミュニティへのモジュラリティ拡張には一意な処方箋がなく、Shen et al.(Eq.39)と Nicosia et al.(Qov、Eq.40, 43)がそれぞれ異なる定式化を提示している(p.35-36)。 - Gaertler et al. はモジュラリティを「被覆度(coverage)と null model 期待値との差」として一般化し、比を取る変種等も比較した。Massen and Doye、Muff et al. は null model 自体を修正(多重辺・自己ループを禁止、局所近傍のみを考慮する局所モジュラリティ LQ)した(p.36-38)。 - Reichardt and Bornholdt はコミュニティ検出をスピングラス模型の基底状態探索として再定式化し、γ を分解能パラメータとして導入した。標準モジュラリティは γ=1 の特殊ケースに一致する(p.37-38)。 - モチーフ密度に基づく一般化(motif modularity)、三角形モジュラリティ Q4、符号付き(正負)重みグラフへの拡張(correlation clustering との関連。Gómez et al. の Q+/Q-、Kaplan and Forrest、Traag and Bruggeman)も導入されている(p.37-39)。 - 二部グラフ専用のモジュラリティ(Guimerà et al.、Barber の BRIM 法)も提案されている(p.38-39)。 ### C. モジュラリティの限界 - ランダムグラフでも大きなモジュラリティ値を持つ分割が存在しうるため、z-score による統計的有意性評価が使われる(「Cutoff values of 2-3 for the z-scores are customary」, p.39)。ただし null model 分布が非ガウス的であるという問題がある(p.39)。 - Reichardt and Bornholdt はスピングラス理論から、ランダムグラフの期待最大モジュラリティ Qmax のスケーリングが ⟨k^{1/2}⟩/⟨k⟩ に従うことを導出し、疎なグラフほどモジュラリティによる検出が困難になることを示した(p.39-40)。 - **解像度限界(resolution limit)**: Fortunato and Barthélemy による発見。モジュラリティの null model は「どの頂点も他の全頂点と結合しうる」という非現実的な仮定に基づくため、総次数が √m 程度以下の小さな真のコミュニティ(クリークなど)同士を誤って併合してしまう。「modularity optimization has a resolution limit that may prevent it from detecting clusters which are comparatively small with respect to the graph as a whole, even when they are well defined communities like cliques.」(p.40) ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch06-fig15-resolution-limit.png]] (FIG. 15. モジュラリティの解像度限界。同一構造のクリーク集合が、個別クリークとしてではなくクリークの対として検出されてしまう例。) - 解像度限界への対処として、Li et al. の modularity density(null model 不要、分解能パラメータ付き)や、クラスタを独立グラフとして再帰的に細分割する手法が提案されているが、後者について本章は「信頼できる手続きではない」と述べており、その理由の説明は章末で途切れている(次章冒頭に続く可能性がある。p.40)。 ## 代表手法・システムの比較 | 規模・要件 | 推奨手法 | 根拠 | |---|---|---| | 超大規模(10^7〜10^9 辺) | [[Louvain法]](Blondel et al.)、Wakita-Tsurumi 版貪欲法 | O(m) 級の計算量で最速級(p.28-29) | | 中規模・精度重視 | 極値最適化(EO)、スペクトル最適化 + Kernighan-Lin 型後処理 | 速度と精度のバランスが良い(p.29-32) | | 小規模(〜10^4 頂点)・最高精度 | 焼きなまし法(Guimerà & Amaral 実装) | 真の最大値に近づくが低速(p.29) | | クラスタ数既知・少数(二部割) | 数理計画法・BRIM 等の専用手法 | 大規模データには不向き(p.33-34, 38-39) | | 総次数 √m 以下の小コミュニティ探索 | modularity density・局所モジュラリティ | 標準モジュラリティは解像度限界のため信頼できない(p.39-40) | モジュラリティ最大値の有意性は z-score で評価できるが、閾値(2〜3)は目安に過ぎず、非ガウス分布への注意が必要(p.39)。 ## 傾向と未解決課題 - BRIM アルゴリズムの収束ステップ数を n や m の関数として表す式はまだ導出されていない(p.39)。 - 「局所的な視界」に基づくベクトル頂点の一般的定義は、局所モジュラリティ以外に確立されていない(p.40)。 - 解像度限界を回避する再帰的細分割は「信頼できる手続きではない」とされるが、その理由の説明は本文書境界(ch-06→ch-07)で途切れており、次章との重複・欠落の要確認事項として申し送る。 - 脚注10(p.27、「モジュラリティが高いことは必ずしも良い分割を意味しない」)と脚注11(p.31、Richardson et al. のクラスタ単位最適化との違い)は本文の主張に条件を付ける注記であり、本要約には収まらないため原文参照を推奨する。 ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[@2010__PhysRep__Community detection in graphs - Chapter V Divisive algorithms]] — 前章(Girvan-Newman 法とモジュラリティの導入)。 - [[@2010__PhysRep__Community detection in graphs - Chapter VII Spectral Algorithms]] — 次章(スペクトルアルゴリズム、本章のスペクトル最適化と接続)。 - [[Girvan-Newman algorithm]] — モジュラリティが停止基準として初めて導入された文脈。 - [[M. E. J. Newman]] — 貪欲最適化法・スペクトル最適化法(モジュラリティ行列)の提案者。 - [[Vincent D. Blondel]] — Louvain法(階層的貪欲最適化)の提案者。 - [[モジュラリティ]] — 本章全体の中心的品質関数。 - [[Louvain法]] — 本章 A 節の代表的最適化アルゴリズム。 - [[コミュニティ検出]] — モジュラリティ最適化はコミュニティ検出の主要な方法論の一つ。