# モジュラリティ ## 定義 ネットワーク分割の品質を測るスカラー値(-1〜1)。コミュニティ内部のリンク密度を、コミュニティ間のリンク密度と比較して定量化する。重み付きネットワークでは次式で定義される(Newman 2004、[[@2008__JSTAT__Fast unfolding of communities in large networks]] 式1)。 $Q=\frac{1}{2m}\sum_{i,j}\left(A_{ij}-\frac{k_i k_j}{2m}\right)\delta(c_i,c_j)$ ここで $A_{ij}$ はノード $i,j$ 間のエッジ重み、$k_i$ はノード $i$ に接続する重みの総和、$c_i$ はノード $i$ が属するコミュニティ、$m$ は全リンク重みの総和の半分。 ## 子概念 - [[Louvain法]] — モジュラリティ最大化を局所探索と凝集の反復で近似する手法。 ## 未解決の問い - 厳密なモジュラリティ最適化はNP困難であり([[@2008__JSTAT__Fast unfolding of communities in large networks]] 内で言及)、近似手法の精度と計算量のトレードオフはどう体系化できるか。 - モジュラリティ最適化には「解像度限界問題」があり、一定スケールより小さいコミュニティを識別できない([[@2008__JSTAT__Fast unfolding of communities in large networks]] 内で言及、Fortunato & Barthélemy 2007)。この限界を回避する設計指針は何か。 - 疎なグラフ(平均次数一定・頂点数無限大)における planted partitioning problem のクラスタ検出可能性は、クラスタ数 q と p_in(ランダムに選ばれたエッジがクラスタ内にある確率)によって理論的な限界が決まるとされるが、この限界の一般的な特徴づけは何か(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]])。 - コミュニティ構造を持たないグラフ(null model)の精密な定義がまだ存在せず、modularity の null model(configuration model による次数保存ランダム化)はその一例に過ぎない(出自: [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]]) ## 未編纂の観察 [解像度限界] Louvain法は第1フェーズで単一ノードずつしか移動しないため、2つの異なるコミュニティが単一ノード移動だけで併合される確率が非常に低く、解像度限界問題を部分的に回避しているとされる(Source: [[@2008__JSTAT__Fast unfolding of communities in large networks]])。 - [動的過程との等価性] Delvenne et al. のランダムウォークに基づく安定性(stability)測度 r(t;H) は、時間パラメータ t=1 における最大化が Newman-Girvan モジュラリティの最大化と等価であり、t を分解能パラメータとして一般化できる(Source: [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]])。 - [解像度限界の機序] モジュラリティのnull modelは「どの頂点も他の全頂点と結合しうる」という非現実的な仮定に基づくため、総次数がm^{1/2}程度以下(mは全リンク重みの総和の半分)の小さな真のコミュニティ(クリークなど)同士を誤って併合してしまう。Reichardt and Bornholdtはスピングラス理論からランダムグラフの期待最大モジュラリティQmaxのスケーリングが⟨k^{1/2}⟩/⟨k⟩に従うことを導出し、疎なグラフほど検出が困難になることを示した(Source: [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]])。 - [統計的有意性] ランダムグラフでも大きなモジュラリティ値を持つ分割が存在しうるため、z-scoreによる統計的有意性評価が使われる(閾値2-3が慣例)が、null model分布が非ガウス的であるという問題が指摘されている(Source: [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]])。 - [局所モジュラリティ] Clauset は境界の鋭さを測る比率として局所モジュラリティ R を定義し、コミュニティサイズが未知でも貪欲局所探索により単一コミュニティを検出できるようにした。計算量は O(n_c^2 ⟨k⟩)(n_c はコミュニティサイズ)で、全体分割を要する通常のモジュラリティ最適化とは異なり、始点頂点周辺だけを探索する局所版バリアントである(Source: [[@2010__PhysRep__Community detection in graphs - Chapter X Alternative methods]])。 - [クラスタリングの有意性] モジュラリティ等の品質関数の最適化で得られた最良分割が高い値を持つことは、そのグラフに本質的な意味のあるクラスタ構造があることを保証しない。ランダムグラフでも高いQ値を取りうるため、頑健性・安定性(摂動やブートストラップに対する分割の回復可能性)やエントロピー比較に基づく有意性評価が別途必要とされる。Gfeller et al. はエッジ重み摂動によるクラスタリングエントロピー、Karrer et al. はエッジ置換によるvariation of information、Rosvall and Bergstromはブートストラップによるcluster core同定、Massen and Doyeは-Qをエネルギーとする正準集団を用いた評価手法をそれぞれ提案している(Source: [[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]])。 - [LFRベンチマークでの実証] Lancichinetti and Fortunato (2009) による [[LFR benchmark]] 上での比較評価では、モジュラリティ系手法(Blondel et al. の Louvain 法を除く)は解像度限界のため混合パラメータ µ が大きい(コミュニティ構造が弱い)領域で性能が悪化した。一方 Infomap (Rosvall and Bergstrom) と Ronhovde-Nussinov 法は良好かつほぼ線形時間で高速だった(Source: [[@2010__PhysRep__Community detection in graphs - Chapter XV Testing Algorithms]])。 - [マルチ解像度による対処] 解像度限界への対処として、解像度パラメータを掃引して安定な分割を探すマルチ解像度手法群が提案されている。Reichardt and Bornholdtの一般化スピングラス模型(パラメータγ)、Pons (2006) のマルチスケール品質関数QMα、Arenas et al. (2008b) の自己ループ強度rを導入した拡張モジュラリティQr、Lancichinetti et al. (2009) のフィットネス関数ベース手法、Ronhovde and Nussinov (2008, 2009) のnull modelを含まないPottsモデル型エネルギー関数などが該当し、パラメータ掃引時のクラスタ数のプラトー(安定領域)や分割間の類似度から意味のある分割スケールを推定する(Source: [[@2010__PhysRep__Community detection in graphs - Chapter XII Multiresolution methods and cluster hierarchy]])。 ## 関連 - ソース: [[@2010__PhysRep__Community detection in graphs - Chapter VIII Dynamic Algorithms]] / [[@2010__PhysRep__Community detection in graphs - Chapter VI Modularity-based methods]] / [[@2010__PhysRep__Community detection in graphs - Chapter X Alternative methods]] / [[@2010__PhysRep__Community detection in graphs - Chapter XIV Significance of clustering]] / [[@2010__PhysRep__Community detection in graphs - Chapter XV Testing Algorithms]] / [[@2010__PhysRep__Community detection in graphs - Chapter XII Multiresolution methods and cluster hierarchy]] / [[@2010__PhysRep__Community detection in graphs - Chapter XVIII Outlook]] - エンティティ: [[LFR benchmark]] / [[Peacock]]