A Multi-Perturbation Stability Framework for Assessing Community Structure in Complex Networks

技術的要約：複雑ネットワークにおけるコミュニティ構造を評価するための多重摂動安定性フレームワーク

問題提起
複雑ネットワークにおけるコミュニティ構造の強度の評価は、依然として未解決の課題である。Louvain、Leiden、Infomapといった数多くの検出アルゴリズムが存在する一方で、得られた分割の堅牢性や「強さ」を評価するための手法は乏しい。モジュラリティ（$Q$）のような既存の指標は、解像度の限界、疎なグラフにおける偽の高値、および弱いコミュニティ領域における感度の低下といった問題を抱えている。さらに、既存の堅牢性研究は、単一の摂動モードや特定のアルゴリズムに焦点を当てることが多く、複数の損傷タイプをネットワークレベルのサマリーへと統合できておらず、真の構造とランダムな変動を区別するための形式的な統計的有意性テストを欠いている。安定した分割が、真のトポロジー構造を反映しているのか、それとも単に特定の検出アルゴリズムの自己整合性を反映しているのかを区別するという決定的なギャップが存在する。

手法
著者らは、進行的なトポロジー的損傷の下でコミュニティ分割がいかに安定して持続するかを定量化する、多重摂動安定性フレームワークを提案する。このフレームワークは、以下の3つの逐次的なステージで構成される：

1. 多重モード摂動： 3つの補完的な摂動オペレータが、異なる強度（$\alpha$）で適用される：

   • ランダム・エッジ除去 (RER): エッジの希薄化をシミュレートする。
   • ランダム・エッジ再配線 (REW): ノード数とエッジ数を維持しながら、エッジの削除と新規追加を行うことで、接続のランダム化をシミュレートする。
   • ランダム・ノード除去 (RNR): ノードの消失をシミュレートする。
     各強度において、ネットワークに摂動が加えられ、コミュニティ検出アルゴリズムが再実行される。元の分割と摂動後の分割の類似性は、正規化相互情報量 (NMI) を用いて測定される。

2. 複合スコアリング ($S(G)$):

   • 各摂動タイプにおける強度の変化に伴うNMIの保持率は、保持曲線（retention curve）を形成する。
   • これら3つの保持曲線の曲線下面積 (AUC) が算出される。
   • これら3つのAUC指標は、CRITIC (CRiteria Importance Through Intercriteria Correlation) 客観的重み付け法を用いて、単一の複合安定性スコア $S(G)$ に統合される。この手法は、指標のコントラスト強度（標準偏差）と競合度（相関）に基づいて重みを割り当てるため、主観的な重み付けを排除できる。

3. 統計的有意性テスト:

   • ランダムグラフが高いスコアを示す問題を解決するため、本フレームワークは次数保存構成モデルを帰無モデルのベースラインとして採用する。
   • 実験的な $p$ 値は、観測された $S(G)$ を500個のランダムな帰無ネットワークから得られたスコアの分布と比較することで算出される。
   • 検出器への依存性を定量化するために、対称的クロス検出器設計（Louvain、Leiden、Infomapを用いた3 $\times$ 3行列）が用いられ、安定性が単一アルゴリズムの自己整合性の産物ではないことを保証する。

主な貢献

1. 検出器条件付き安定性の定式化： 本論文は、$S(G)$ をネットワーク固有の特性としてではなく、特定の「検出パイプライン」の分割が損傷に対してどの程度安定して持続するかを定量化する診断指標として定義し、モジュラリティのような静的な指標を補完するものである。
2. 摂動の客観的な統合： 本フレームワークは、3つの異なる損傷モード（希薄化、ランダム化、ノード消失）をCRITIC重み付けを用いて統合している。アブレーション研究により、これらの指標は高度に冗長（ピアソン相関係数 $r > 0.98$）であることが明らかになった。これは、CRITICの主な価値が識別力の向上ではなく、主観的な重み付けの排除にあることを示している。
3. 統計的較正： 本手法は、実証的な $p$ 値とType-Iエラー制御を備えた厳格な帰無モデルの枠組みの中に $S(G)$ を組み込んでおり、絶対的な指標値を超えた統計的推論を実現している。
4. 包括的な検証： 本フレームワークは、SBM（Stochastic Block Model）ベンチマークおよび4つの実世界のネットワーク（Karate, Dolphins, Football, Polbooks）によって検証されており、完全に対称的なクロス検出器実験とスケール正規化研究を含んでいる。

主な結果

• グラウンドトゥルースとの相関： SBMベンチマークにおいて、$S(G)$ はグラウンドトゥルースである調整ランド指数（ARI）と強い相関（$r = 0.974$）を示し、アルゴリズムの自己整合性ではなく、真の構造の回復を測定していることが確認された。
• モジュラリティとの補完性： $S(G)$ とモジュラリティ（$Q$）は補完的な強みを持つ。$Q$ は静的なエッジ密度の偏差を測定し、$S(G)$（動的な保持を測定）が低下する非常に弱い領域でも有意性を保つ。逆に、$S(G)$ は構造的損傷に対する堅牢性を捉える。
• 摂動の順序： 破壊的な強度は REW > RER > RNR の順となる。エッジの再配線（REW）は、コミュニティ内の密度コントラストを能動的に侵食するため、最も破壊的であり、これは二チャネルの損傷計算メカニックによって支持されている。
• 検出器依存性： 構造が明確なネットワークでは、コミュニティ強度のランク順位はLouvain、Leiden、Infomapの間で不変である。しかし、弱い領域においては、絶対的な $S(G)$ 値は検出器間で大きく乖離する。特に、Infomapはランダムに近い領域で非単調な挙動を示し、構造的に意味のない、しかし内部的に一貫した分割によって保持スコアを膨張させる。
• スケール感受性： 単純なzスコア正規化ではスケール依存性を排除できない。$S(G)$ はネットワークサイズやコミュニティ密度に応じて系統的に変化しており、これはスケールの影響が単純なベースラインのシフトではなく、より深いトポロジー的メカニズム（例：解像度の限界）に起因することを示唆している。
• 実世界ネットワークでの検証： 実世界のネットワークにおいて、$S(G)$ は有意なコミュニティ構造を正しく特定（$p < 0.05$）する一方で、Erdős–Rényiランダムグラフを非有意として正しく分類した。本フレームワークは、公称レベルである5%に近い約4%でType-Iエラーを制御している。

意義と主張
本論文は、$S(G)$ をコミュニティ構造の安定性を評価するための、摂動に基づくモジュラリティの補完的手段として位置づけている。コミュニティの評価には、マルチメトリックなアプローチが有益であると主張している。すなわち、モジュラリティがエッジ密度の組織化という「静的な質」を捉えるのに対し、$S(G)$ は構造的損傷下におけるその組織化の「動的な堅牢性」を捉えるものである。

著者らは、$S(G)$ は検出器に条件付けられた診断指標であり、アルゴリズムに依存しない固有の特性ではないことを強調している。したがって、絶対値の解釈には注意が必要であり、特に異なるスケールや検出パイプライン間での比較においては注意を要する。本フレームワークは、ランダムな変動から生じる安定したパターンを排除するための原理的な手法を提供し、同様のスケールと密度を持つネットワーク内でのコミュニティの強さを比較するための標準化された方法を提示している。結論として、$S(G)$ はモジュラリティに取って代わるものではないが、複雑ネットワークのコミュニティ構造を包括的に評価するために不可欠な、境界条件と動的な視点を提供するものである。