Community Detection 続編 — 高次構造・動的ネットワーク・多重ネットワークの最前線

はじめに — 前編の手法に共通する仮定

前編では、コミュニティー検出の基本的な歴史、Modularity Q の定式化、Louvain / Leiden / Infomap / SBM といった標準的なアルゴリズム、そして Resolution Limit や検出限界といった本質的な困難を解説しました。

前編で扱った手法は、次の 3 つを暗黙に仮定しています:

1. ペアワイズな辺のみを考慮する — ノード $i$ と $j$ の間に辺があるかないか、という 2 体関係だけでコミュニティーを定義
2. 静的（単一スナップショット）のグラフ — ネットワークは時間とともに変化しないと仮定
3. 単一種類の関係 — ノード間の関係は 1 種類のみ

現実のネットワークは、これらの仮定をいずれも破ります。SNS では「友人の友人は友人」という三角形の閉包（triadic closure）が起こり、ノード間の関係は時間とともに変化し、同じ人物の間にも「友人関係」「仕事関係」「趣味のつながり」など複数種類の関係があります。

本稿では、それぞれの仮定を外す 3 つの研究の流れを扱います:

• 高次構造 (Higher-Order) に基づくコミュニティー検出 — モチーフ、ハイパーグラフ、単体複体
• 動的ネットワークにおけるコミュニティー検出 — 時間発展するグラフへの対応
• 多重 (Multiplex) ネットワークにおけるコミュニティー検出 — 複数レイヤーの統合

第 I 部: 高次構造 (Higher-Order) に基づくコミュニティー検出

なぜ「辺」だけでは不十分なのか

前編で紹介した Modularity ベースの手法を含む多くのアルゴリズムは、コミュニティーを「辺が密な部分グラフ」として定義します。この定義では、次の 2 つのグラフを区別できません:

• グラフ A: 6 ノード、9 辺。全ての辺がいずれかの三角形に含まれる
• グラフ B: 6 ノード、9 辺。三角形は 0 個。完全二部グラフ $K_{3,3}$ の構造

ノード数と辺の数が同じなので、辺密度も等しくなります。しかしグラフ A には三角形の閉包（triadic closure）による強い局所的な凝集があり、社会ネットワークでいえば「友人の友人は友人」という現象にあたります。グラフ B には三角形が 1 つもありません。

この違いを捉えるため、三角形のような高次構造 (higher-order structure) を考慮する手法が研究されてきました。

クリーク・パーコレーション法 (CPM) — 高次構造を使った初期の手法

高次構造を使った最初期の代表的な手法が、Palla, Derényi, Farkas, Vicsek (2005) によるクリーク・パーコレーション法 (Clique Percolation Method, CPM) です。CPM は次の手順でコミュニティーを求めます:

1. ネットワーク中の $k$-クリーク（$k$ ノードの完全部分グラフ）を全て列挙する
2. $k-1$ 個のノードを共有する 2 つの $k$-クリークを「隣接」と定義する
3. 隣接する $k$-クリークを辿って到達可能な全ての $k$-クリークの和集合を 1 つのコミュニティーとする

例えば、タンパク質間相互作用ネットワーク（PPI）において $k=4$ で CPM を適用すると、4 つのタンパク質が全て相互作用している密な複合体をビルディングブロックとして、より大きな機能モジュールを検出できます。

CPM は、ノードが複数のコミュニティーに同時に属する重複コミュニティー (overlapping communities) も検出できます。異なる $k$-クリークの連鎖どうしがノードを共有できるため、複数の連鎖に含まれるノードは、それぞれの連鎖が作るコミュニティーに同時に属するからです。社会ネットワークでは、1 人が「会社の同僚」「大学の友人」「趣味のサークル」など複数のコミュニティーに属するのが普通なので、この性質は現実の構造に合っています。

ただし、結果はパラメーター $k$ の選び方に大きく左右され、スパースなネットワークでは $k$-クリーク自体がほとんど存在しません。また、CPM が使う高次構造は $k$-クリークに限られます。これを任意のネットワークモチーフに一般化したのが、次に紹介するモチーフベースの手法です。

ネットワークモチーフの基礎

ネットワークモチーフ (network motif) とは、ネットワーク中に統計的に有意に多く現れる小さな部分グラフのパターンです。この概念は、生物学者 Uri Alon らの研究 (Milo et al., 2002) で確立されました。彼らは、大腸菌の遺伝子調節ネットワークではフィードフォワードループなどのパターンが、ランダムネットワークよりはるかに多く現れることを示しました。

モチーフに注目するのは、モチーフがネットワークの中で機能的な意味を持つからです:

• 三角形: 社会ネットワークにおける信頼の形成や効率的な情報伝達。「A が B を信頼し、B が C を信頼するなら、A も C を信頼しやすい」
• フィードフォワードループ: 遺伝子調節における信号のフィルタリング
• 4-サイクル: 二部ネットワーク（ユーザー–商品）における協調フィルタリングの基盤

Benson-Gleich-Leskovec のモチーフベース・コミュニティー検出 (2016)

高次構造に基づくコミュニティー検出で広く参照されているのが、Benson, Gleich, Leskovec による "Higher-order organization of complex networks" (Science, 2016) です。基本的な考え方は次のとおりです:

辺の密度ではなく、モチーフの密度に基づいてコミュニティーを定義する。

中心となる指標: Motif Conductance

前編で扱った通常の Conductance は、次のように定義されます:

Benson らはこれをモチーフ $M$ に拡張し、Motif Conductance を定義しました:

ここで:

• $\text{cut}_M(S, \bar{S})$: モチーフ $M$ のインスタンスのうち、$S$ と $\bar{S}$ の両方にノードを持つもの（「境界をまたぐモチーフ」）の数
• $\text{vol}_M(S)$: $S$ 内のノードのモチーフ重み付き次数の合計。形式的には $\text{vol}_M(S) = \sum_{i \in S} d_i^{(M)}$、ここで $d_i^{(M)} = \sum_j W_{ij}^{(M)}$（後述するモチーフ重み付き隣接行列の行和）

$\phi_M(S)$ が小さいほど、コミュニティー $S$ の内部でモチーフ $M$ が密で、境界をまたぐモチーフが少なくなります。

モチーフ重み付き隣接行列

Motif Conductance を厳密に最小化する集合を求めるのは計算量的に困難なので、Benson らはモチーフ重み付き隣接行列 $W^{(M)}$ を構築し、この最小化をスペクトラル法で近似します:

アンカー集合は、モチーフのノードのうち重みを数える対象として選んだものです。三角形のようにモチーフの全ノードをアンカーにする場合、$W^{(M)}_{ij}$ はペア $(i,j)$ を含むインスタンスの数そのものです。一部のノードだけをアンカーにするモチーフでは、どのノードをアンカーに選ぶかで値が変わります。この行列からモチーフ重み付きラプラシアンを作り、スペクトラルクラスタリングを適用します:

ここで $D^{(M)}$ は $W^{(M)}$ の行和を対角要素とする次数行列です。

Benson ら (2016) は、これを正規化した $\mathcal{L}^{(M)} = (D^{(M)})^{-1/2} L^{(M)} (D^{(M)})^{-1/2}$ について、Cheeger 不等式の類似物を示しました。三角形のようにアンカーが 3 ノードのモチーフでは、Motif Conductance は $W^{(M)}$ を重みとするグラフの通常の Conductance と一致し、次の不等式が成り立ちます:

ここで $\lambda_2^{(M)}$ は $\mathcal{L}^{(M)}$ の 2 番目に小さい固有値、$\phi_M^*$ は最適な Motif Conductance です。スペクトラル法で得たクラスター $S$ については $\phi_M(S) \leq 4\sqrt{\phi_M^*}$ が保証され、最適解からのずれに上限があります。前編で紹介した通常のスペクトラルクラスタリングにおける Cheeger 不等式と同じ構造の結果です。

次のデモは、三角形モチーフに基づくコミュニティー検出の手順を示します:

モチーフベース手法の利点

辺ベースの手法と比べると、モチーフベースの手法には次の利点があります:

1. 情報量の増加: 2 体関係の辺に加えて、3 ノード以上の関係パターンを使える
2. ドメイン知識の統合: 分析対象に合ったモチーフを選べる。例えば、生物ネットワークではフィードフォワードループ、社会ネットワークでは三角形
3. ノイズ耐性: ランダムに張られた辺はモチーフを作りにくいため、モチーフの密度はランダムなノイズの影響を受けにくい

ハイパーグラフによるコミュニティー検出

モチーフベースの手法は、グラフの辺から高次のパターンを数えます。これに対し、多体関係をそのままデータとして表すのがハイパーグラフ (hypergraph) に基づくアプローチです。

通常のグラフでは辺は 2 ノード間の関係ですが、ハイパーグラフではハイパーエッジが任意の数のノードの集合を直接結びます:

ハイパーエッジで表せる多体関係には、例えば次のものがあります:

• 論文の共著関係（3 人以上の共著）
• メールの CC（複数人に同時送信）
• 化学反応（複数の物質が同時に関与）

ハイパーグラフ上のコミュニティー検出には、主に次の方法があります:

クリークへの展開 (Clique Expansion): ハイパーエッジ $e = \{v_1, ..., v_k\}$ を $\binom{k}{2}$ 個のペアワイズ辺に変換し、通常のグラフとして処理します。この変換では、全員が同時に関わったという情報が失われます。4 人が 1 つの会議に同席する（1 つのハイパーエッジ）ことと、4 人の全ペアが個別に会話する（6 本の辺）ことは、変換後のグラフでは区別できません。

ハイパーグラフ直接法: ハイパーグラフ上のスペクトラルクラスタリングでは、次のハイパーグラフラプラシアンを用います:

ここで $H$ は接続行列（ノード $\times$ ハイパーエッジ）、$D_v$ はノード次数行列、$W_e$ はハイパーエッジの重み行列、$D_e$ はハイパーエッジ次数（サイズ）の対角行列です。Zhou, Huang, Schölkopf (2006) が導入したのは、これを両側から $D_v^{-1/2}$ で正規化した $I - D_v^{-1/2} H W_e D_e^{-1} H^T D_v^{-1/2}$ です。

Kumar et al. (2020) は、ハイパーエッジの情報を保ったまま重み付き Modularity を反復的に最大化する手法を提案しました。Modularity の定義には、ハイパーエッジのサイズを反映させています。

単体複体 (Simplicial Complex) によるアプローチ

単体複体 (simplicial complex) はトポロジー（位相幾何学）の概念で、ハイパーグラフに包含条件を加えた構造とみなせます。$k$-単体（$k$-simplex）は $k+1$ 個のノードの集合で、単体複体は、含まれる単体の部分集合も全て単体として含みます。

• 0-単体: ノード
• 1-単体: 辺
• 2-単体: 三角形（3 ノード + 3 辺）
• $k$-単体: $(k+1)$ ノードの完全グラフ（とその全ての部分面）

単体複体上では、境界作用素を使ってホッジラプラシアン (Hodge Laplacian) を定義でき、$k$-チェイン（各 $k$-単体に値を割り当てたもの）の「滑らかさ」を測れます。1-チェインは辺上のフローにあたるので、辺のフローに基づくコミュニティー検出にも使えます。Schaub et al. (2020) は、単体複体上のランダムウォークと正規化ホッジ 1-ラプラシアンを結び付けました。

第 I 部の手法は、辺 → クリーク → モチーフ → ハイパーエッジ → 単体と、表せる関係を広げてきました。ただし、いずれも時間とともに変化しない静的なグラフを対象にしています。

第 II 部: 動的ネットワークにおけるコミュニティー検出

動的ネットワークの定式化

友人関係の形成と解消、論文の出版と引用、タンパク質の発現パターンの変化のように、時間とともに構造が変わるネットワークを動的ネットワークと呼びます。

動的ネットワークの表現方法は主に 2 つあります:

離散スナップショットモデル: 時刻 $t_1, t_2, ..., t_T$ におけるグラフのスナップショット $G_1, G_2, ..., G_T$ として表現。各 $G_t = (V_t, E_t)$ は静的グラフ。

連続時間モデル: 辺の出現・消失をイベントとして扱い、$(i, j, t_{\text{start}}, t_{\text{end}})$ の形でタイムスタンプ付きで記録。より詳細な情報を保持するが、分析が複雑。

実用上はスナップショットモデルが広く使われますが、スナップショットを取る間隔（時間粒度）によって結果が大きく変わります。

コミュニティーのライフサイクル

動的ネットワークでは、各時刻のコミュニティーを見つけるだけでなく、時間を通じてコミュニティーを追跡する必要があります。コミュニティーには次のようなライフサイクルイベントが起こります:

これらのイベントを同定するには、連続するスナップショットの間でコミュニティーを対応付けます（マッチング）。

次のデモは、動的ネットワークにおけるコミュニティーのライフサイクルを示します:

アプローチ 1: 独立検出 + 対応付け (Two-Stage Approach)

最もシンプルな手法は、各時刻のスナップショットに独立にコミュニティー検出を適用し、その後、連続する時刻間でコミュニティーの対応を取るというものです。

Two-Stage Approach:
  1. 各時刻 t でコミュニティ C_t = {C_t^1, C_t^2, ...} を独立に検出
  2. 隣接する時刻 t, t+1 間で Jaccard 係数によるマッチング:
     J(C_t^i, C_{t+1}^j) = |C_t^i ∩ C_{t+1}^j| / |C_t^i ∪ C_{t+1}^j|
  3. J が閾値以上のペアを対応とし、ライフサイクルイベントを同定:
     - 対応先がない C_t^i → 消滅 (Death)
     - 対応元がない C_{t+1}^j → 誕生 (Birth)
     - 1 対多 → 分裂 (Split)
     - 多対 1 → 統合 (Merge)

この手法では、静的なコミュニティー検出アルゴリズムをそのまま使えます。前編で紹介した Louvain、Leiden、Infomap のどれでも、各スナップショットに適用できます。

一方で、時間的一貫性 (temporal coherence) は保証されません。辺がわずかに増減しただけでも検出されるコミュニティー構造が大きく変わることがあり、実際には安定しているコミュニティーが激しく変動しているように見える場合があります。

アプローチ 2: Evolutionary Clustering (2006)

Chakrabarti, Kumar, Tomkins (KDD 2006) が提案した Evolutionary Clustering は、この時間的一貫性を目的関数に組み込みます。

具体的には、現在のスナップショットへの適合度と、前時刻の分割との類似度の重み付き和を最大化します:

• $\text{quality}(C_t, G_t)$: 時刻 $t$ のグラフ $G_t$ に対するコミュニティー分割 $C_t$ の品質（例: Modularity Q）
• $\text{similarity}(C_t, C_{t-1})$: 前時刻のコミュニティー分割 $C_{t-1}$ との類似度（例: 正規化相互情報量 (NMI) や Jaccard 係数）
• $\alpha \in [0, 1]$: 「現時点のデータへの適合」と「過去との一貫性」のトレードオフパラメーター

$\alpha = 1$ なら完全な独立検出（前時刻を無視）、$\alpha = 0$ なら前時刻と完全に同じ構造の維持（新しいデータを無視）になります。

実用上の課題は $\alpha$ の設定です。ネットワークが急激に変化する時期（例: SNS における世界的イベント）には $\alpha$ を大きく、安定期には小さくするのが望ましいものの、いつ切り替えるかの判断自体が困難です。

Evolutionary Clustering は「動的コミュニティー検出」を明示的な最適化問題として定式化した最初の体系的研究で、後続の多くの手法に影響を与えました。

アプローチ 3: Multislice Modularity (Mucha et al., 2010)

Mucha, Richardson, Macon, Porter, Onnela による "Community Structure in Time-Dependent, Multiscale, and Multiplex Networks" (Science, 2010) は、動的コミュニティー検出で最も広く使われている枠組みの 1 つを示しました。

この手法では、時間スナップショットを「スライス」として積み重ね、同じノードをスライス間の結合辺でつないだ 1 つの大きなグラフとして扱います。このグラフ上で、次の Multislice Modularity を定義します:

各記号と項の意味は次のとおりです:

インデックスの意味:

• $i, j$: ノード
• $s, r$: スライス（時刻やレイヤーのインデックス）
• $g_{is}$: ノード $i$ のスライス $s$ におけるコミュニティー割り当て

第 1 項: $\left( A_{ijs} - \gamma_s \frac{k_{is} k_{js}}{2m_s} \right) \delta_{sr}$

これは「同一スライス内」の Modularity です。$\delta_{sr}$ があるので、$s = r$（同じスライス）のときだけ寄与します。$\gamma_s$ は resolution parameter（前編参照）で、スライスごとに異なる値を設定できます。

第 2 項: $\delta_{ij} \omega_{jsr}$

この項が Mucha らの定式化で新しく加わった部分です。$\delta_{ij}$ によって「同一ノード」のみに適用され、$\omega_{jsr}$ はスライス間結合強度です。直感的には「時刻 $s$ のノード $i$ と時刻 $r$ の同じノード $i$ を仮想的な辺でつなぐ」操作です。

$\omega_{jsr}$ の選択:

• 時間的に隣接するスナップショット間のみ結合: $\omega_{jsr} = \omega$ if $|s - r| = 1$
• 全スナップショット間を一様に結合: $\omega_{jsr} = \omega$ for all $s \neq r$
• ノードごと・時刻ごとに異なる結合: $\omega_{jsr}$ が $j, s, r$ に依存

$\omega$ が大きいほど「同じノードは時刻が変わっても同じコミュニティーにいるべき」という時間的一貫性が強くなり、小さいほど各スナップショットの独立性が高まります。

正規化: $2\mu = \sum_{jr} \kappa_{jr}$ で、$\kappa_{jr} = k_{jr} + c_{jr}$（ノード $j$ のスライス $r$ における次数 $k_{jr}$ とスライス間結合の強度 $c_{jr}$ の合計）

この定式化には次の特徴があります:

1. 動的ネットワークと多重ネットワークの統一: スライスを「時刻」と解釈すれば動的ネットワーク、「レイヤー」と解釈すれば多重ネットワーク
2. 既存手法の利用: この拡張 Modularity は、通常の Modularity と同様に Louvain/Leiden 型の貪欲法で最適化できる
3. マルチスケール解析: $\gamma_s$ と $\omega$ を変えることで、異なるスケールの構造を探索できる

アプローチ 4: テンソル分解

De Domenico et al. (2013) は、多重・動的ネットワークをテンソルとして表現する数学的枠組みを提案しました。

$L$ 個のレイヤー（または時間スナップショット）を持つ多重ネットワークは、4 階テンソル $\mathcal{M}$ として表現できます:

• $i, j$: ノード
• $\alpha, \beta$: レイヤー
• $\mathcal{M}_{ij\alpha\alpha}$: レイヤー $\alpha$ におけるノード $i$ と $j$ の間の辺の重み
• $\mathcal{M}_{ii\alpha\beta}$: ノード $i$ のレイヤー $\alpha$ と $\beta$ の間の結合（inter-layer coupling）

このテンソルに対してテンソル分解 (CP 分解や Tucker 分解) を適用し、コミュニティー構造を抽出します。テンソル分解は行列分解（PCA や NMF）の多次元版で、ノードとレイヤーの両方の構造を同時に捉えられます。

テンソルによる表現は数学的な一般性が高い反面、大規模ネットワークへのスケーラビリティーに課題があります。Gauvin, Panisson, Cattuto (2014) は、対面接触ネットワークに非負テンソル因子分解 (NTF) を適用し、コミュニティーのメンバーシップとその時間的な活動パターンを同時に推定しました。

ここで扱った Multislice Modularity とテンソル分解は、スライスを時刻ではなく関係の種類とみなせば、多重ネットワークにもそのまま適用できます。

第 III 部: 多重 (Multiplex) ネットワークにおけるコミュニティー検出

多重ネットワークとは何か

多重ネットワーク (multiplex network) とは、同じノード集合の間に複数種類の関係（レイヤー）が存在するネットワークです。

例:

• SNS: 「フォロー」「メッセージ」「いいね」が別レイヤー
• 交通: 「鉄道」「バス」「航空」が別レイヤー
• 生物: 「タンパク質-タンパク質相互作用」「遺伝子調節」「代謝経路」が別レイヤー

多重ネットワークは多層ネットワーク (multilayer network) の一種です。多層ネットワークの一般的な定式化は Kivelä et al. (2014) のサーベイにまとめられており、そのうち全レイヤーでノード集合が同じものを多重ネットワークと呼びます。

アプローチ 1: レイヤー集約 (Layer Aggregation)

最も単純なのは、全レイヤーの隣接行列を足し合わせた集約グラフに、通常のコミュニティー検出を適用する方法です:

ここで $A^{(\alpha)}$ はレイヤー $\alpha$ の隣接行列、$w_\alpha$ は重みです。

実装は簡単ですが、レイヤー固有の情報が失われます。あるレイヤーではコミュニティー A に、別のレイヤーではコミュニティー B に属するノードがあっても、集約後のグラフにはその違いが残りません。

アプローチ 2: Multislice Modularity（再訪）

第 II 部の Multislice Modularity (Mucha et al., 2010) は、スライスを「レイヤー」と読み替えるだけで多重ネットワークに適用できます。

結合パラメーター $\omega$ は、異なるレイヤー間でのコミュニティーの一貫性を制御します。$\omega$ が大きいほど、同じノードは全てのレイヤーで同じコミュニティーに属しやすくなります。

アプローチ 3: レイヤーごとの検出結果の統合

各レイヤーで独立にコミュニティーを検出し、その結果を統合する方法もあります。Magnani, Hanteer, Interdonato, Rossi, Tagarelli (2021) のサーベイは、ネットワーク全体のコミュニティーを求める多重ネットワークの手法を、レイヤーの扱い方によって次の 3 クラスに分類しています:

1. フラット化 (flattening): レイヤーを 1 つのグラフにまとめてから、通常のコミュニティー検出を適用する
2. レイヤー単位 (layer-by-layer): 各レイヤーを独立に処理し、その結果を統合する
3. 多層型 (multilayer): 全レイヤーを同時に考慮して検出する

アプローチ 1 のレイヤー集約はフラット化に、この節の方法はレイヤー単位に、アプローチ 2 の Multislice Modularity は多層型にあたります。多層型は全レイヤーの情報を同時に使える反面、計算コストが高くなります。

GenLouvain: Multislice Modularity の実用的実装

Multislice Modularity の最適化によく使われるのが GenLouvain (Jutla, Jeub, Mucha, 2011–) です。Louvain アルゴリズムの多重・動的ネットワーク版で、次の手順で動作します:

GenLouvain:
  入力: 多重/動的ネットワーク (隣接行列 A^(s), 結合パラメータ ω)
  1. Multislice Modularity 行列 B を構築:
     B_{isjs} = A_{ijs} - γ_s * k_{is}*k_{js}/(2*m_s)  (同一スライス内)
     B_{isir} = ω_{isr}                                  (スライス間・同一ノード)
  2. この B 行列上で Louvain の局所移動 + 集約を適用
  3. Multislice Modularity Q_multislice を最大化
  → 各ノードの各スライスにおけるコミュニティ割り当てが得られる

第 IV 部: 近年の最前線

GNN ベースのコミュニティー検出

2020 年代に入り、Graph Neural Network (GNN) を用いたコミュニティー検出の研究が増えています。

DMoN (Tsitsulin et al., 2023): Modularity を微分可能な形に緩和し、GNN のエンコーダーで得たノード埋め込みからコミュニティー割り当て行列を直接予測します。損失関数は次のとおりです:

• 第 1 項: Modularity の最大化（符号が負なので最小化すると最大化に相当）
• 第 2 項: collapse 正則化。$C^T \mathbf{1}_n$ はクラスターサイズベクトル $\mathbf{s}$（各クラスターに割り当てられたノード数）。全クラスターが均等サイズ（$s_i = n/k$）のとき最小値 0 となり、全ノードが 1 クラスターに集中すると大きなペナルティーを与える
• $C$: GNN が出力するソフトなコミュニティー割り当て行列 ($n \times k$)
• $B$: Modularity 行列 ($B_{ij} = A_{ij} - k_i k_j / 2m$)

MinCutPool (Bianchi et al., 2020): 正規化カットの緩和を損失として学習するグラフプーリング層です。プーリング層を重ねると、ノードを階層的にまとめられます。

GNN ベース手法では、SNS のプロフィール、論文の本文、タンパク質の配列といったノードの特徴量をグラフ構造と同時に扱えます。一方で、次の課題があります:

• 解釈性: GNN の中間表現の意味が不透明
• 汎化性: 学習データと異なる構造のグラフに適用できるか不明
• スケーラビリティー: 大規模グラフでの訓練コスト

フローに基づく動的コミュニティー検出

情報の流れ（フロー）に着目して、時間変化するコミュニティーを扱う研究もあります。Rosvall と Bergstrom (2010) は、各スナップショットを Infomap でクラスタリングし、ブートストラップ再標本化でコミュニティーの有意性を評価したうえで、時刻間の変化をアルビュアル図 (alluvial diagram) で可視化しました。

スライス間の結合を Map Equation に組み込んだのは、De Domenico, Lancichinetti, Arenas, Rosvall (2015) の多層版 Map Equation です。ランダムウォーカーはスライス内を移動し、一定の確率で別のスライスの同じノードに移ります。Mucha らの Multislice Modularity と同様のスライス間結合を、情報理論の枠組みで表したものです。

ストリーミングアルゴリズム

辺が 1 本ずつ到着するストリーミング設定でのコミュニティー検出も研究されています。大規模 SNS でのリアルタイム検出が主な用途です。

OSLOM (Lancichinetti, Radicchi, Ramasco & Fortunato, 2011) は、統計的に有意なコミュニティーを局所的な order-statistics 検定で求める手法で、主に静的グラフを対象にしています。この検定は増分・動的な設定にも応用できますが、p 値の検定を繰り返すため計算コストが比較的高くなります。

手法の比較と選択指針

実践的なアルゴリズム選択ガイド

前編のガイドに、高次・動的・多重ネットワークを扱う場合を加えます:

まとめ — コミュニティー検出の発展の流れ

前編と本稿で扱った研究は、おおまかに 3 つの世代に分けられます。

第 1 世代 (1970–2000 年代前半): グラフ分割問題から社会ネットワーク分析へ。Girvan-Newman 法と Modularity の定式化。辺密度に基づく「静的・単一レイヤー・ペアワイズ」の枠組み。

第 2 世代 (2000 年代後半–2010 年代前半): Louvain のスケーラビリティー（2019 年には改良版の Leiden も登場）、SBM の統計的推論、Resolution Limit や検出限界の発見。手法の改良が進む一方で、問題そのものの難しさも明らかになりました。

第 3 世代 (2000 年代半ば以降、特に 2010 年代後半–現在): 辺の密度以外の情報を使う手法。

• 高次構造の考慮（モチーフ、ハイパーグラフ、単体複体）
• 時間的ダイナミクスの統合（Evolutionary Clustering、Multislice Modularity）
• 多重関係の統合（多重ネットワーク、テンソルアプローチ）
• 深層学習との融合（GNN ベース手法）

コミュニティー検出には単一の正解がありません。辺の密度、モチーフの密度、情報圧縮効率、統計的な有意性、時間的一貫性、レイヤー間の整合性は、それぞれ異なる「コミュニティー」の定義に対応します。個々の手法は、ネットワークの構造を異なる角度から見るための道具です。

研究が進んでいる方向には、例えば次のものがあります:

1. ハイパーグラフ上の GNN: ハイパーグラフニューラルネットワーク (HGNN) を用いた教師なしコミュニティー検出
2. 因果的コミュニティー: ノード・辺の時間的因果関係に基づくコミュニティーの定義
3. スケーラブルな動的手法: 数十億ノード規模のリアルタイム処理
4. 理論的保証の拡張: 高次構造や動的設定における検出限界の解明

前編で述べた「完璧な Community Detection は原理的に不可能」という制約は、高次・動的・多重の設定ではさらに強くなります。どのモチーフを選ぶか、$\alpha$ や $\omega$ をいくつにするかで、結果が変わるからです。その代わりに、三角形の閉包、時間変化、複数種類の関係といった、辺の密度だけでは扱えない構造を分析できるようになりました。次の記事では、本稿の動的ネットワークの議論をさらに進め、辺が 1 イベントずつ到着・削除される ストリーミング設定 を扱います。

参考文献

• Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., & Alon, U. (2002). Network motifs: simple building blocks of complex networks. Science, 298(5594), 824–827.
• Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818.
• Chakrabarti, D., Kumar, R., & Tomkins, A. (2006). Evolutionary clustering. KDD 2006, 554–560.
• Mucha, P. J., Richardson, T., Macon, K., Porter, M. A., & Onnela, J.-P. (2010). Community structure in time-dependent, multiscale, and multiplex networks. Science, 328(5980), 876–878.
• Rosvall, M., & Bergstrom, C. T. (2010). Mapping change in large networks. PLoS ONE, 5(1), e8694.
• Lancichinetti, A., Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011). Finding statistically significant communities in networks. PLoS ONE, 6(4), e18961.
• De Domenico, M., Solé-Ribalta, A., Cozzo, E., Kivelä, M., Moreno, Y., Porter, M. A., Gómez, S., & Arenas, A. (2013). Mathematical formulation of multilayer networks. Physical Review X, 3(4), 041022.
• Yang, J., & Leskovec, J. (2013). Overlapping community detection at scale: a nonnegative matrix factorization approach. WSDM 2013, 587-596.
• Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., & Porter, M. A. (2014). Multilayer networks. Journal of Complex Networks, 2(3), 203–271.
• Gauvin, L., Panisson, A., & Cattuto, C. (2014). Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach. PLoS ONE, 9(1), e86028.
• De Domenico, M., Lancichinetti, A., Arenas, A., & Rosvall, M. (2015). Identifying modular flows on multilayer networks reveals highly overlapping organization in interconnected systems. Physical Review X, 5(1), 011027.
• Benson, A. R., Gleich, D. F., & Leskovec, J. (2016). Higher-order organization of complex networks. Science, 353(6295), 163–166.
• Bianchi, F. M., Grattarola, D., & Alippi, C. (2020). Spectral clustering with graph neural networks for graph pooling. ICML 2020.
• Kumar, T., Vaidyanathan, S., Ananthapadmanabhan, H., Parthasarathy, S., & Ravindran, B. (2020). Hypergraph clustering by iteratively reweighted modularity maximization. Applied Network Science, 5, 52.
• Schaub, M. T., Benson, A. R., Horn, P., Lippner, G., & Jadbabaie, A. (2020). Random walks on simplicial complexes and the normalized Hodge 1-Laplacian. SIAM Review, 62(2), 353–391.
• Magnani, M., Hanteer, O., Interdonato, R., Rossi, L., & Tagarelli, A. (2021). Community detection in multiplex networks. ACM Computing Surveys, 54(3), Article 48, 1–35.
• Tsitsulin, A., Palowitch, J., Perozzi, B., & Müller, E. (2023). Graph clustering with graph neural networks. JMLR, 24(127), 1–21.
• Zhou, D., Huang, J., & Schölkopf, B. (2006). Learning with Hypergraphs: Clustering, Classification, and Embedding. NeurIPS 2006.
• Jutla, I. S., Jeub, L. G. S., & Mucha, P. J. (2011–). A generalized Louvain method for community detection implemented in MATLAB. http://netwiki.amath.unc.edu/GenLouvain

参考資料（発展的読書）

• Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010). Link communities reveal multiscale complexity in networks. Nature, 466(7307), 761-764.
• Benson, A. R., Gleich, D. F., & Lim, L.-H. (2017). The spacey random walk: a stochastic process for higher-order data. SIAM Review, 59(2), 321–345.
• Rossetti, G., Milli, L., & Cazabet, R. (2019). CDLIB: a python library to extract, compare and evaluate communities from complex networks. Applied Network Science, 4, 52.
• Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3-5), 75-174.
• Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1-44.