Dynamic sparse graphs with overlapping communities

論文技術要約：動的なスパースグラフにおける重なり合うコミュニティのモデル化

1. 研究の背景と問題設定

現実世界のネットワーク（ソーシャルネットワーク、情報ネットワーク、経済ネットワークなど）は、静的ではなく時間とともに変化します。リンクの生成・消滅や、コミュニティの出現・融合・消滅といった動的な挙動を捉えることが重要です。しかし、既存の動的コミュニティ検出モデルには以下の重大な課題がありました。

• スパース性と重なり（Overlapping）の両立の難しさ: 多くの既存モデル（動的 SBM や混合メンバーシップモデルなど）は、ノードの交換可能性（exchangeability）を仮定していますが、これにより生成されるグラフは理論的に「空」か「密」かのどちらかになり、現実の「スパース（疎）」かつ「べき乗則（power-law）の次数分布」を持つグラフを表現できません。
• 動的な重なりメンバーシップの欠如: 既存のスパースグラフモデルはスパース性を扱えますが、ノードが複数のコミュニティに属する「重なりメンバーシップ」が時間とともにどう進化するかをモデル化する動的な枠組みが不足していました。
• ノード数の固定: 多くのモデルは時間ステップごとにノード数が一定であることを前提としており、新しいノードの出現や既存ノードの消去を自然に扱えません。

本研究は、**「スパース性」「べき乗則次数分布」「動的な重なりメンバーシップ」「ノードの出入り」**の 4 つの特性を同時に満たす新しいベイジアン非パラメトリックモデルを提案するものです。

2. 提案手法：dynSNetOC

著者らは、dynSNetOC（Dynamic Sparse Network with Overlapping Communities）というモデルを提案しました。このモデルは、以下の構成要素に基づいています。

• 点過程と完全ランダム測度（CRM）:
  グラフを平面上の点過程として表現し、Caron & Fox (2017) の枠組みを拡張します。ノードの潜在的な「社会性（sociability）」を完全ランダム測度（CRM）でモデル化し、これによりスパース性とべき乗則次数分布を自然に導出します。
• 時間進化する重なりメンバーシップ:
  各ノードのコミュニティへの所属度（スコア）を、**隠れマルコフ過程（Latent Markov Process）**を通じて時間的に進化させます。
  • 各コミュニティ $k$ に対して、完全ランダム測度のベクトル $(W^{(t)}_1, \dots, W^{(t)}_p)$ を定義します。
  • ノード $i$ のコミュニティ $k$ への所属スコア $\beta^{(t)}_{ki}$ は、時間 $t$ においてガンマ分布からサンプリングされ、その進化は補助変数 $\gamma^{(t)}_{ki}$ を介したマルコフ過程で記述されます。
  • この構成により、ノードは複数のコミュニティに重なりを持って所属でき、その所属割合が時間とともに滑らかに変化します。
• 連結性の生成:
  時間 $t$ におけるノード $i$ と $j$ の間のリンク数 $n^{(t)}_{ij}$ は、ポアソン分布に従い、そのパラメータは両ノードの各コミュニティへの所属スコアの積の和（非負ポアソン分解）によって決定されます。
  $$n^{(t)}_{ij} \mid \mathbf{w}^{(t)} \sim \text{Poisson}\left(2 \sum_{k=1}^p w^{(t)}_{ik} w^{(t)}_{jk}\right)$$
  ここで $w^{(t)}_{ik} = w_{i0} \beta^{(t)}_{ki}$ です。

3. 理論的性質と漸近結果

モデルの数学的性質について以下の結果が証明されています。

• スパース性と密度:
  測度のレヴィ測度のパラメータ $\sigma$ によってグラフの密度が決まります。
  • $\sigma \in (0, 1)$ の場合：グラフはスパースであり、エッジ数 $E$ とノード数 $N$ の関係は $E \asymp N^{2/(1+\sigma)}$ となります。
  • $\sigma < 0$ の場合：グラフは密になります。
  • $\sigma = 0$ の場合：遷移領域（almost dense）となります。
• 次数分布:
  $\sigma \in (0, 1)$ の場合、グラフは次数 $j$ に対して $j^{-(1+\sigma)}$ のべき乗則分布に従うことが示されました。これにより、現実のスケールフリーネットワークを正確に再現できます。

4. 推論手法

無限次元の CRM を直接扱うのは計算量的に困難であるため、Lee et al. (2023) の提案に基づき、有限次元の近似を用いた推論を行います。

• etBFRY 分布の近似:
  無限活動の一般化ガンマ過程（GGP）を、指数傾斜 BFRY 分布（etBFRY）で近似します。これにより、スパース性とべき乗則の性質を保持しつつ、有限のノード数で計算可能になります。
• ハミルトニアンモンテカルロ（HMC）:
  事後分布の近似には、NUTS（No-U-Turn Sampler）アルゴリズムを用いた勾配ベースの MCMC 法を採用しました。これは高次元の連続パラメータ空間（動的な潜在変数）を効率的に探索するのに適しています。

5. 実験結果

提案モデルの有効性を、合成データと実データ（Reuters テロ報道データ）を用いて検証しました。

• 合成データ:
  既知のパラメータを持つグラフから生成されたデータに対して、モデルがスパース性、べき乗則分布、および時間とともに変化するコミュニティ構造を正確に復元できることを確認しました。事後予測区間（PPCI）が実データの次数分布を良好にカバーしています。
• Reuters テロデータ（9/11 事件後のニュース）:
  2001 年 9 月 11 日の米国同時多発テロ以降の 6 週間のニュース記事から抽出された単語ネットワークに適用しました。
  • 発見されたコミュニティ: 「9/11 攻撃」「アフガニスタン」「セキュリティ」「政治的対応」「炭疽菌（Anthrax）」の 5 つのトピックが抽出されました。
  • 動的進化の可視化:
    • 「攻撃（Attack）」コミュニティは、当初は WTC 攻撃に関連していましたが、10 月以降はアフガニスタン侵攻に関連する語彙を取り込み、意味が変化しました。
    • 「セキュリティ（Security）」は、当初は空港・航空セキュリティでしたが、後に炭疽菌事件に伴う健康・国家セキュリティへと意味がシフトしました。
    • 「政治（Political）」コミュニティは、4 週目に「攻撃」コミュニティと融合し、独立したトピックとして消滅しました。
  • 重なりメンバーシップの重要性: サンキー図やパイチャートにより、多くの単語が単一のコミュニティに属するのではなく、複数のコミュニティに重なりを持って所属し、その割合が時間とともに変化していることが示されました。

6. 既存モデルとの比較

• 静的 SNetOC (Todeschini et al., 2020): 時系列を統合して解析すると、コミュニティの時間的進化（トピックの出現・消滅・意味変化）を捉えられませんでした。
• 動的 SBM (dynSBM): スパース性と次数の不均一性を扱えず、モデルの適合度が低く、意味のあるトピック検出ができませんでした。
• 動的混合メンバーシップ SBM (dMMSB): 次数分布の再現性は向上しましたが、コミュニティ構造の推定が失敗し（すべての接続が単一のコミュニティ内に収束する）、実用的なコミュニティ検出アルゴリズムとして機能しませんでした。

7. 結論と意義

本研究は、スパースでべき乗則の次数分布を持つ動的ネットワークにおいて、重なり合うコミュニティの時間的進化を統一的にモデル化する初めての手法を提案しました。

• 主要な貢献:
  1. 完全ランダム測度と隠れマルコフ過程を結合した新しいベイジアン非パラメトリックモデルの構築。
  2. スパース性とべき乗則を理論的に保証する漸近結果の導出。
  3. 合成データおよび実データ（9/11 報道）を用いた、動的なトピック進化と重なりメンバーシップの高精度な復元。
• 意義:
  このモデルは、従来の静的モデルや非スパースな動的モデルでは捉えきれなかった、現実世界の複雑なネットワークの進化メカニズム（トピックの融合、意味の遷移、ノードの流入流出）を解釈可能に可視化することを可能にしました。将来的には、共変量の導入やコミュニティ数の推定などへの拡張が期待されます。