> 前: [[@2010__PhysRep__Community detection in graphs - Chapter XIII Detection of dynamic communities]] | 次: [[@2010__PhysRep__Community detection in graphs - Chapter XV Testing Algorithms]] | 全体: [[Community detection in graphs]] # Community detection in graphs - Chapter XIV: Significance of clustering ## 要約 品質関数(モジュラリティ等)の最適化によって得られた最良分割が、グラフの本質的な特徴を反映しているのか、それとも次数列などの基本構造とランダム性がもたらす副産物にすぎないのかは、これまでほとんど検討されてこなかった課題である。ランダムグラフの分割でもモジュラリティは大きな値を取りうるため、Q値の高さだけではコミュニティ構造の実在を保証できない。本章はこの「クラスタリングの有意性(significance of clustering)」を評価する複数の手法と、planted partition problem による検出可能性の理論的限界を扱う。 ## 分類軸(taxonomy) 有意性評価の手法は大きく2系統に分けられる。 1. **パーティション全体の頑健性・安定性による評価**: 摂動を加えても分割が回復されるはずだという発想に基づく。摂動の与え方(エッジ重みの変化、エッジの確率的置換、ブートストラップ再サンプリング)と、評価指標(エントロピー、variation of information、cluster core、正準集団における自由エネルギー的量)の組み合わせで複数の手法が提案されている。 2. **個々のコミュニティ単位での評価**: グラフ全体が modular でない可能性がある場合、パーティション全体ではなく単一コミュニティごとに有意性を問う指標(C-score)を用いる。 さらに、これらの経験的手法とは別に、planted partitioning problem という理論モデルによってクラスタ構造の検出可能性そのものに理論的な限界があることが議論される。 ## 代表手法・システムの比較 **摂動に基づく安定性評価**: Gfeller et al. は重み付きグラフのエッジ重みを ±σ だけ変化させた多数の実現を生成し、各頂点対の in-cluster probability p_ij からクラスタリングエントロピー S(式84)を定義し、Newman-Girvan の null model と比較して有意性を評価する。ただし閾値 σ, θ の選び方が恣意的という弱点がある。Karrer et al. は非重み付きグラフに対し、確率 α でエッジを Newman-Girvan null model(確率 p_ij = k_i k_j / 2m)に従ってランダムに置換する摂動を導入し、variation of information V の変化 ⟨V(α)⟩ から安定性を評価する。 **ブートストラップによる評価**: Rosvall and Bergstrom はポアソン分布で重みを再サンプリングした多数のブートストラップサンプルを生成し、各クラスタについて95%以上のサンプルで同一クラスタに分類される最大部分集合を cluster core として同定する。 **正準集団によるエネルギー的評価**: Massen and Doye は −Q をエネルギーとみなし、温度 T のもとで分割の出現確率が exp(Q/T) に比例する正準集団を導入した。有意なクラスタ構造を持つグラフでは低温で最大モジュラリティ分割から明確なギャップが生じる一方、構造を持たないグラフでは低温でも多数の局所最大が競合して現れる。ただし Good et al.(footnote 29)は、モジュラリティランドスケープ自体に高モジュラリティ状態の縮退が多いため、この結果が誤解を招く可能性を指摘している。関連する診断量として、比熱 C = −dQ/dT の温度依存性や、頻度行列のラプラシアンのフィードラー固有値 λ2 の急激な遷移、コミュニティサイズの急減がある。ただしスケールフリーグラフではハブの存在によりこれらの遷移が鋭くなりにくい。 **エントロピー比に基づく評価**: Bianconi et al. はグラフアンサンブルのエントロピー概念を用い、与えられた次数列のもとで特定のクラスタ構造(クラスタ間エッジ数 A(q1,q2))がどれだけ起こりやすいかを、実際のエントロピーとクラスタラベルのランダム置換による平均エントロピーの比(式85、Θ)で評価する。 **個別コミュニティ単位の評価**: Lancichinetti et al. は、同じ次数列を持つランダムグラフの部分グラフである確率として定義される C-score を提案した。最も内部次数の低い「worst」頂点の統計に基づき、C-score ≤ 5% であればランダムな揺らぎの産物ではなく真のコミュニティであるという強い根拠になる。t > 1 頂点まで拡張した B-score も可能である。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch15-fig29-c-score.png]] (FIG. 29. C-score は頂点除去に伴う値の変化として計算され、急激な低下が密な部分グラフの存在を示す。) C-score の弱点は、null model が Newman-Girvan と同一(各頂点がグラフサイズに関わらず任意の他頂点と接続しうるという非現実的な仮定)であることで、より現実的な「horizon」概念に基づく null model の定義は未解決の課題として残されている。 **理論的な検出可能性限界**: Reichardt and Leone は、等サイズクラスタ・クラスタ内接続確率 p・クラスタ間接続確率 r(< p)を持つ planted partitioning problem(Condon and Karp による計算機科学分野での先行定式化を踏まえる)を用いて検出可能性を論じた。密なグラフでは p − r をどれだけ小さくしても解を回復できるアルゴリズムが存在するが、平均次数が一定で頂点数が無限大になる疎なグラフ(実ネットワークに典型的)では、クラスタ数 q とランダムに選ばれたエッジがクラスタ内にある確率 p_in によって回復可能性の限界が決まる。 ## 傾向と未解決課題 - モジュラリティなど品質関数の値が高いことのみをもって「意味のあるコミュニティ構造」と判断してはならない。ランダムグラフでも高いQ値を取りうる。 - 摂動ベースの安定性評価(Gfeller et al., Karrer et al.)はどのクラスタリング手法にも適用可能な汎用的アプローチだが、null model との比較なしには絶対的な意味を持たない。 - C-score の null model は Newman-Girvan と同一で非現実的であり、頂点ごとの「horizon」(相互作用しうる部分集合)をどう定義すべきかは未解決の問題として明記されている。 - 疎なグラフ(平均次数一定・頂点数無限大)における planted partition の一般的な回復可能性の閾値(p_in の値による限界)は本章末尾で提起され、次章(Testing Algorithms)以降で継続して扱われる可能性がある。 ## 関連 - [[Community detection in graphs]] - [[モジュラリティ]] — 本章の議論はモジュラリティなど品質関数の値の高さと構造の有意性の乖離を扱う。 - [[コミュニティ検出]] - 前: [[@2010__PhysRep__Community detection in graphs - Chapter XIII Detection of dynamic communities]] - 次: [[@2010__PhysRep__Community detection in graphs - Chapter XV Testing Algorithms]]