> 前: [[@2010__PhysRep__Community detection in graphs - Chapter VII Spectral Algorithms]] | 次: [[@2010__PhysRep__Community detection in graphs - Chapter IX Methods based on statistical inference]] | 全体: [[Community detection in graphs]] # Community detection in graphs - Chapter VIII: Dynamic Algorithms ## 要約 グラフ上を動く動的過程を利用してコミュニティを検出する手法群を概観する章。スピン模型に基づく手法(A節)、ランダムウォークに基づく手法(B節)、同期現象に基づく手法(C節)の3系統に分けて整理する(p.43-47)。 ## 分類軸(taxonomy) - **A. スピン模型(spin models)**: グラフをスピン系のハミルトニアンに写像し、基底状態(エネルギー最小状態)をシミュレーテッドアニーリング等で探索することでコミュニティを定義する。 - **B. ランダムウォーク(random walk)**: グラフ上のランダムウォークが同一コミュニティ内に長く留まりやすいという性質を利用し、頂点間の到達距離や遷移確率の持続性からコミュニティを定義する。 - **C. 同期(synchronization)**: グラフ上に振動子を配置し、結合力の強い(=密に接続された)頂点集団ほど早く同期する現象を利用してコミュニティを検出する。 ## 代表手法・システムの比較 ### A. スピン模型 - **[[Reichardt-Bornholdt method|Reichardt-Bornholdt]]**: グラフをゼロ温度 q-Potts 模型に写像し(式54)、シミュレーテッドアニーリングでハミルトニアンを最小化してコミュニティを検出する。Blatt らの有限温度 Potts 模型を先行研究として発展させたもので、式54はモジュラリティの一般化(VI.B節)の基礎になる(p.43-44)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch08-fig18-spectral-algorithm-capocci.png]] (FIG. 18. Capocci らのスペクトル法の基本原理。右確率行列の第二固有ベクトル成分が、3コミュニティからなるグラフでプラトー(平坦域)を形成する様子を示す。本図は前章VII節の議論の続きとして本章冒頭に現れる。) - **[[Son et al. FRFIM method|Son et al.]]**: 強磁性ランダム場イジングモデル(FRFIM、式56)を用い、2頂点 s, t の spin を無限大の逆符号磁場で固定して最大流最小カット問題として解く。全ての基底状態で同一クラスタに属す頂点集合を coterie(コテリー)と呼び、クラスタの核とみなす。計算量は O(n^{2+θ})(θ≈1.2)で低速なため数千頂点規模までしか実用的でないが、重要頂点が事前にわかれば s, t を制約でき O(n^θ) まで高速化できる。Ispolatov は反強磁性項を含む類似ハミルトニアンを提案した(p.44)。 ### B. ランダムウォーク - **Zhou**: ランダムウォークによる頂点間距離(平均到達エッジ数)でクラスタを定義し、global/local attractor(大域/局所アトラクタ)に基づき分割する。Zhou と Lipowsky はバイアス付きランダムウォーク手法 NetWalk を提案した(p.45)。 - **Latapy-Pons([[walktrap]])**: 固定ステップ数のランダムウォークの遷移確率から頂点間距離を定義し、Ward 法による凝集型階層的クラスタリングで分割したのち、モジュラリティで最良の断面を選ぶ。計算量は密グラフで O(n^2 d)、実グラフでは実用上 O(n^2 log n) 程度に収まる。ステップ数の選択は「十分に広く探索するが定常極限に近づきすぎない」よう非自明な調整を要する(p.45-46)。 - **Hu et al.**: シグナリング過程(拡散に類似)に基づく手法で、fuzzy k-means によりクラスタを抽出する(p.45-46)。 - **Delvenne, Lambiotte et al.**: ランダムウォークのクラスタ持続性に基づく安定性(stability)指標 r(t;H)(式58)を定義する。t=1 での最大化が Newman-Girvan モジュラリティの最大化と等価であることを示し、時間 t を分解能パラメータとして扱えることを指摘した(p.46)。 - **Weinan, E. et al.**: メタグラフのマルコフ連鎖近似に基づく手法を提案したが、クラスタ数 k を決める一般的な指針は示していない(p.46)。 - **Van Dongen([[MCL (Markov Cluster Algorithm)|MCL]])**: 遷移行列の冪乗(expansion)と要素ごとの冪(inflation)を交互に繰り返すフロー拡散シミュレーションで、バイオインフォマティクスで最も使われるクラスタリング手法の一つとされる。膨張パラメータ α によって最終分割が変わるため、どの分割が最も意味があるか不明瞭という弱点がある(p.46-47)。 ### C. 同期 - **[[Arenas-Díaz-Guilera-Pérez-Vicente synchronization method|Arenas, Díaz-Guilera, Pérez-Vicente]]**: 蔵本(Kuramoto)振動子の同期ダイナミクスを用いてコミュニティを検出した最初の研究。局所秩序パラメータ ρ_ij(t)(式60)と動的連結性行列 D_t(T) からプラトー(連結成分数が安定する区間)を検出し、構造的スケールがラプラシアン固有値のギャップに対応することを示した(p.47)。 ![[_attachments/arxiv-0906.0612-fortunato-community-detection/ch09-fig19-kuramoto-synchronization.png]] (FIG. 19. 2階層のコミュニティ構造を持つグラフでの蔵本振動子の同期。上段は時間に対する同期成分数、下段はラプラシアン固有値の逆数に対する順位。プラトーが2種類のコミュニティ構造を明らかにする(p.47)。) - **Boccaletti et al.**: opinion changing rate(OCR)モデルという蔵本モデルの変種を用い、辺の betweenness で結合強度を重み付けする手法を提案した(p.47)。同期法は時間 t を連続変数として扱うことで分解能パラメータにでき、小時間での線形化はモジュラリティの多重解像度版につながる(XII.A節参照)(p.47)。 ## 傾向と未解決課題 - ランダムウォークのステップ数 T(Latapy-Pons、Hu et al.)の最適値を選ぶことは非自明である(p.45-46)。 - Weinan et al. の手法ではクラスタ数 k を決める一般的な指針が示されていない(p.46)。 - MCL は膨張パラメータ α に対して結果が敏感であり、どの分割が最も意味のある代表かが不明瞭である(p.47)。 - 安定性(stability)測度と同期法はいずれも時間パラメータ t を分解能パラメータとして扱える点で共通しており、モジュラリティの多重解像度版(XII.A節)への接続点になっている(p.46-47)。 ## 関連 - [[Community detection in graphs]] — 本サーベイのハブ entity。 - [[@2010__PhysRep__Community detection in graphs - Chapter VII Spectral Algorithms]] — 前章。FIG. 18(Capocci らのスペクトル法)の議論が本章冒頭に続く。 - [[@2010__PhysRep__Community detection in graphs - Chapter IX Methods based on statistical inference]] — 次章。 - [[Reichardt-Bornholdt method]] — ゼロ温度 Potts 模型によるスピン模型手法。 - [[Son et al. FRFIM method]] — FRFIM・coterie 概念によるスピン模型手法。 - [[walktrap]] — ランダムウォーク距離+Ward法によるコミュニティ検出アルゴリズム。 - [[MCL (Markov Cluster Algorithm)]] — フロー拡散型のランダムウォークベース手法。 - [[Arenas-Díaz-Guilera-Pérez-Vicente synchronization method]] — Kuramoto 振動子同期による最初のコミュニティ検出手法。 - [[モジュラリティ]] — 安定性測度 r(t;H) の t=1 における最大化が Newman-Girvan モジュラリティの最大化と等価。 - [[複雑ネットワーク]] — 本章で扱う動的過程(スピン系・ランダムウォーク・同期現象)はグラフ上のダイナミクスとして複雑ネットワーク研究一般に位置づく。