ストリーミング Community Detection — リアルタイムに変化するグラフの中でコミュニティを追い続ける科学

はじめに — なぜ「ストリーミング」なのか

第 1 編ではコミュニティ検出の基礎——Modularity、Louvain/Leiden、Infomap、SBM——を、第 2 編では高次構造・動的ネットワーク・多重ネットワークへの拡張を解説しました。

しかし第 2 編で扱った「動的ネットワーク」のアプローチには、ある暗黙の前提がありました: グラフのスナップショットが離散的な時刻に与えられ、各スナップショットでバッチ処理的にコミュニティ検出を実行する。現実の大規模ネットワーク——Twitter/X のフォロー関係、金融取引ネットワーク、IoT センサーネットワーク——では、この前提は 2 つの点で破綻します。

1. スケールの問題: 数十億ノード・数百億辺を持つグラフで、辺が 1 本変わるたびに Louvain を最初から実行するのはコスト的に不可能
2. リアルタイム性の問題: 不正検知やトレンド予測のように、コミュニティ構造の変化を 即座に 把握したいユースケースでは、次のスナップショットを待つ余裕がない

こうした要求に応えるのが ストリーミング・コミュニティ検出 (Streaming Community Detection) です。辺が 1 本ずつ到着（または削除）される 辺ストリーム (edge stream) に対して、コミュニティ構造を 増分的 (incrementally) に更新し続ける——これがこの記事のテーマです。

この記事で扱うこと

• ストリーミング CD の 研究史 — バッチ処理からの脱却がどう進んだか
• 「バッチ再計算」「増分的更新」「真のストリーミング」の 3 層の区別
• 象徴的なアルゴリズム群の 超詳細な解説: LabelRankT、OSLOM、DEMON、TILES、DynaMo、delta-screening Louvain、ANGEL
• ストリーミング CD の 設計空間 — アルゴリズム設計時に検討すべき独立した次元
• 近年の GNN ベース・LLM 連携 アプローチ
• 実践的な アルゴリズム選択指針

第 I 部: 基礎概念 — バッチからストリーミングへ

辺ストリームの形式的定義

ストリーミング設定におけるグラフは、以下のように定義されます:

ここで:

• $e_i = (u_i, v_i)$: 辺（ノードのペア）
• $t_i$: タイムスタンプ（$t_i \leq t_{i+1}$）
• $\text{op}_i \in \{+, -\}$: 操作（辺の追加 $+$ または削除 $-$）

任意の時刻 $t$ において、グラフ $G_t = (V_t, E_t)$ はそれまでに到着したストリームイベントの累積結果です:

ストリーミング CD の目標は、各時刻 $t$ において $G_t$ のコミュニティ分割 $\mathcal{C}_t$ を 効率的に 維持することです。理想的には、辺 1 本の到着に対する更新コストが $O(1)$ ないし $O(\text{polylog}(n))$ で済むべきです。$O(m + n)$（グラフ全体の走査）を必要とする手法は、ストリーミングとしては不十分です。

3 つの処理パラダイム

ストリーミング設定での CD を理解するには、処理の粒度に基づく 3 つのパラダイムを区別することが重要です:

1. バッチ再計算 (Batch Recompute)

辺が変更されるたびに、グラフ全体に対してコミュニティ検出アルゴリズムを最初から実行します。正確ですが、計算コストが $O(m + n)$ 以上かかるため、大規模グラフでは各更新に秒〜分単位の時間がかかります。Louvain の適用がこれに該当します。

2. 増分的更新 (Incremental Update)

辺の変更が影響する 局所的な範囲のみ を再計算します。変更された辺の端点とその近傍のみを対象とするため、更新コストは $O(\Delta \cdot k)$（$\Delta$ = 変更辺数、$k$ = 平均次数）程度に抑えられます。delta-screening Louvain がこの代表例です。

3. 真のストリーミング (True Streaming)

辺 1 本の到着に対してアルゴリズムの内部状態を 定数時間 ないし 対数時間 で更新します。グラフの走査を一切必要とせず、到着した辺とその直接の近傍情報のみを用いて決定を行います。TILES が理念的にこのカテゴリに属します（ただし実際には三角形検出のためにノードの次数分のコストがかかります）。

安定性と応答性のトレードオフ

ストリーミング CD の根本的なジレンマは、安定性 (stability) と 応答性 (responsiveness) のトレードオフです。

• 安定性: コミュニティ構造がノイズ（ランダムな辺の出現・消失）に対して安定であること。ちょっとした変化で割り当てがコロコロ変わるのは望ましくない
• 応答性: グラフの構造が本質的に変化した（コミュニティが分裂した、新しいコミュニティが出現した等）ときに、素早くそれを反映すること

第 2 編で紹介した Evolutionary Clustering のパラメータ $\alpha$ は、まさにこのトレードオフを制御するものでした:

ストリーミング設定では、このトレードオフが辺 1 本の粒度で問われます。「この辺の追加は本質的な構造変化の兆候か、それとも単なるノイズか？」——この判断を辺 1 本のコンテキストだけで行う必要があるのです。

第 II 部: 研究史 — バッチ処理の時代からの脱却

前史: LPA（Label Propagation Algorithm）の登場 (2007)

ストリーミング CD の歴史を理解するには、まず Label Propagation Algorithm (LPA) を押さえる必要があります。Raghavan, Albert, Kumara (2007) が提案した LPA は、その単純さから自然にストリーミング化しやすいアルゴリズムでした。

Label Propagation Algorithm (LPA):
  1. 各ノードにユニークなラベルを割り当て
  2. 繰り返し:
     各ノード v について:
       v の近傍のラベルの中で最頻出のラベルを v に割り当て
       （同率の場合はランダムに選択）
  3. ラベルが収束したら終了
  → 同じラベルを持つノードの集合がコミュニティ

LPA の計算量は $O(km)$（$k$ は収束までの反復回数、通常 5 回程度）と非常に軽量です。しかも各ノードの更新は 近傍の情報のみ を必要とするため、辺が追加されたときに関係するノードだけを更新すれば良い——つまり、本質的に局所的な操作です。

この「局所性」が、LPA をストリーミング設定への拡張に適した候補にしました。

GraphScope (2007): 変化点検出の先駆

Sun, Faloutsos, Papadimitriou, Yu (KDD 2007) の GraphScope は、ストリーミングに対応した初期の重要な研究です。GraphScope は情報理論（最小記述長原理、MDL）に基づいて、辺ストリームにおけるグラフ構造の 変化点 (change point) を自動的に検出します。

核心のアイデアは以下です:

1. 辺ストリームをセグメント $[t_i, t_{i+1})$ に分割
2. 各セグメント内ではグラフ構造は安定と仮定し、コミュニティ構造を推定
3. セグメント境界は MDL 原理に基づいて自動決定: 新しいセグメントを導入するコスト vs 既存セグメントのモデルで新しいデータを符号化するコストを比較

• $L(\text{model})$: モデル（コミュニティ構造）の記述長
• $L(\text{data} \mid \text{model})$: モデルを条件としたデータの記述長

新しい辺がこのコストのバランスを崩したとき——つまり、既存のコミュニティ構造では新しいデータを効率的に記述できなくなったとき——変化点が検出され、コミュニティ構造が更新されます。

GraphScope の革新は「いつ再計算すべきか」を データ駆動的に 決定した点にあります。定期的にスナップショットを取るのではなく、構造変化が起きたときだけ再計算するため、不要な計算を回避できます。

iLCD (2010): 増分的局所コミュニティ検出

Cazabet, Amblard, Hanachi (IEEE SocialCom 2010) は、動的に成長するネットワークでのコミュニティ検出に特化した初期の手法 iLCD (incremental Local Community Detection) を提案しました。

iLCD の核心は、新しい辺が到着するたびにその端点が既存のコミュニティに参加すべきか新しいコミュニティを形成すべきかを 局所的な品質関数 に基づいて判定する点にあります。辺 $(u, v)$ が到着した場合:

1. $u$ も $v$ もどのコミュニティにも属さない場合、両方を含む新しいコミュニティを作成
2. 一方が既存のコミュニティ $C$ に属する場合、もう一方が $C$ に参加すべきかを局所密度基準で評価
3. 両方が異なるコミュニティに属する場合、マージの可能性を評価
4. 定期的に、コミュニティ境界のノードの再割り当てを検討

iLCD は自然に重複コミュニティを生成します。あるノードが複数のコミュニティの参加条件を同時に満たしうるためです。重要なのは、iLCD が増分的に動作する点です: 到着した辺の局所的な近傍のみを調べるため、ストリーミング設定に対して効率的です。

iLCD の意義は、コミュニティ検出が 真にオンライン で実行可能であることを示した点にあります——バッチスナップショットを待つのではなく、各グラフイベントが発生した時点で処理するというアプローチは、後の TILES や ANGEL に直接的な影響を与えました。

DiDiC (2010): 分散拡散型アプローチ

Gehweiler と Meyerhenke (2010) が提案した DiDiC (Distributed Diffusive Clustering) は、全く異なるパラダイムを導入しました。各ノードが「拡散ベクトル」$\mathbf{d}_v \in \mathbb{R}^k$ を持ち、近傍との間でこのベクトルを局所的に拡散（平均化）させることで、自然にクラスタが形成されるというアイデアです。

DiDiC:
  各ノード v は k 次元の拡散ベクトル d_v を持つ
  初期化: d_v = e_v（one-hot ベクトル）
  各ノード v について（非同期に、局所的に）:
    d_v ← (1-α) · d_v + α · (1/|N(v)|) Σ_{u ∈ N(v)} d_u
  ノード v のコミュニティ = argmax_i d_v[i]

拡散パラメータ $\alpha$ は、各ステップでどれだけ近傍の情報を取り込むかを制御します。$\alpha$ が大きいほど近傍の影響を強く受け、コミュニティの収束が速くなりますが、安定性が低下します。

DiDiC の重要な点は:

1. 完全に局所的: 各ノードの更新は近傍ノードの拡散ベクトルのみを参照
2. 非同期実行可能: 全ノードが同時に更新する必要がなく、辺が到着したノードだけを更新できる
3. 分散環境に適合: 各ノードが自身の状態を独立に管理でき、中央集権的な調整が不要

ストリーミング設定では、辺 $(u, v)$ が到着したとき、$u$ と $v$（および必要に応じてその近傍）の拡散ベクトルだけを更新すれば良く、グラフ全体を走査する必要がありません。

LabelRankT (2013): ラベル伝搬の増分化

Xie, Chen, Szymanski (2013) は LPA を動的ネットワーク向けに拡張した LabelRankT を提案しました。LabelRankT の核心は「辺の変更に影響されるノードだけにラベル伝搬を限定する」という発想です。

LabelRankT:
  通常の LPA でコミュニティを初期化
  辺 (u, v, op) がストリームから到着するたびに:
    1. 影響集合 Δ を構築:
       Δ = {u, v} ∪ N(u) ∪ N(v)  （u, v とその近傍）
    2. Δ 内のノードのみでラベル伝搬を反復:
       各 w ∈ Δ:
         w のラベル ← w の近傍の多数決
    3. Δ 内のノードのラベルが収束するまで（通常 2-3 反復）
    4. 更新されたラベルを出力

LabelRankT の計算量は辺 1 本あたり $O(k \cdot |\Delta|)$ で、$|\Delta|$ は変更された辺の近傍サイズ（= ノードの次数の和）、$k$ は局所的な収束までの反復回数です。次数が $d$ のノードなら、$|\Delta| = O(d)$ なので、全体のコストは $O(k \cdot d)$ となり、グラフサイズ $n, m$ に依存しません。

ただし LabelRankT には重要な限界があります:

• 収束の不安定性: LPA 自体が非決定的（同率ラベルのランダム選択）であるため、局所的な再実行のたびに異なる結果が得られうる
• 重複コミュニティ非対応: 各ノードは 1 つのラベルしか持たないため、重複コミュニティを検出できない
• 品質の保証なし: Modularity や他の品質指標に対する明示的な最適化を行わないため、品質が保証されない

第 III 部: 象徴的アルゴリズムの詳解

OSLOM (2011): 統計的有意性に基づく増分検出

Lancichinetti, Radicchi, Ramasco, Fortunato (2011) の OSLOM (Order Statistics Local Optimization Method) は、コミュニティの「統計的有意性」を検定する手法です。第 2 編でも触れましたが、ここではストリーミング適用の側面を詳しく見ます。

OSLOM の核心的なアイデアは、あるノード集合 $S$ がコミュニティであるかどうかを 帰無仮説検定 と 順序統計量 (order statistics) によって判定することです。名前の由来もここにあります。

具体的な手順は以下です:

1. コミュニティ $S$ に隣接する各ノード $i$ について、Configuration Model（帰無モデル）の下で $i$ が $S$ への内部接続を $k_i^{\text{int}}$ 本以上持つ確率（スコア $r_i$）を計算
2. これらのスコアを昇順にソート: $r_{(1)} \leq r_{(2)} \leq \cdots$
3. $k$ 番目に小さいスコアに対して、順序統計量の p 値 を計算: $n$ 個の一様乱数の $k$ 番目の順序統計量が $r_{(k)}$ 以下になる確率
4. この p 値が最小となる順位 $k$ を選択し、コミュニティ全体の有意性を判定

p 値が十分小さければ（例えば $< 0.05$）、$S$ は統計的に有意なコミュニティと判定されます。重要な点は、OSLOM がコミュニティ全体の内部辺数ではなく ノード単位 で有意性を検定する点であり、これにより個々の外れ値ノードに対しても頑健な判定が可能になります。

OSLOM のストリーミング適用:

OSLOM の増分更新:
  辺 (u, v) が追加されたとき:
    1. u, v が属するコミュニティ C_u, C_v を特定
    2. C_u (と C_v) の p 値を再計算:
       - u の近傍で C_u に属さないノードを C_u に追加した場合の p 値を評価
       - p 値が改善するなら、そのノードを C_u に追加
    3. 同様に C_u からノードを除去した場合の p 値も評価
    4. C_u と C_v のマージの可能性も検討
  辺 (u, v) が削除されたとき:
    1. C_u (= C_v の場合) の p 値を再計算
    2. p 値が閾値を超えたら、C_u を部分グラフに分解して再検定

OSLOM の強みは 理論的な根拠 です。p 値に基づく判定は、Modularity のような ad hoc な指標と異なり、統計学的に「意味のあるコミュニティ」と「偶然の集まり」を区別する明確な基準を提供します。特に Resolution Limit（第 1 編参照）の問題を回避できる点が重要です——小さなコミュニティでも統計的に有意であれば検出されます。

一方で、p 値の計算自体がコストのかかる操作であり、大規模ストリームに対するスケーラビリティには課題が残ります。

DEMON (2012): エゴネットの民主主義

Coscia, Rossetti, Giannotti, Pedreschi (2012) の DEMON (Democratic Estimate of the Modular Organization of a Network) は、エレガントな「ボトムアップ」型の局所コミュニティ検出手法です。

DEMON の哲学は、「コミュニティはノードの 投票 によって決まるべき」というものです。具体的には:

DEMON:
  各ノード v について:
    1. v のエゴネット ego(v) を抽出
       ego(v) = v と v の全近傍 N(v) が誘導する部分グラフ
    2. ego(v) からノード v を除く（v への辺を全て削除）
    3. 残ったグラフに LPA を適用してローカルコミュニティを検出
    4. 各ローカルコミュニティに v を追加
  全ノードの結果を統合:
    - 類似度が閾値以上のローカルコミュニティ同士をマージ
    - マージ基準: Jaccard 係数 J(C_i, C_j) > ε

なぜ v をエゴネットから除くのでしょうか？ v は定義上、ego(v) の全メンバーに接続されているため、v を含めると ego(v) 全体が 1 つのコミュニティとして検出されてしまいます。v を除くことで、v の近傍内の 自然なグルーピング が見えてきます——たとえば「v の大学の友人」と「v の職場の同僚」は v を除くと別々のグループになりますが、v がいると 1 つに結合されてしまいます。

DEMON のストリーミング適用は自然です:

1. 辺 $(u, v)$ が到着 → $u$ と $v$ のエゴネットのみを再構築して LPA を再実行
2. 影響を受けたローカルコミュニティのマージ判定のみを再実行

DEMON は 重複コミュニティ を自然に検出できる点が強みです。異なるノードのエゴネットから得られたローカルコミュニティは重複しうるため、1 つのノードが複数のコミュニティに属する結果が得られます。

DynaMo (2019): Modularity の増分追跡

Zhuang, Chang, Li (2019) の DynaMo は、Modularity $Q$ の値を辺の追加・削除に対して 増分的に 更新する手法です。

DynaMo の核心的な洞察は、辺 $(u, v)$ の変化が生じたとき、ノードのコミュニティ間移動の Modularity 利得 (modularity gain) を局所情報のみで効率的に再計算できる点にあります。Louvain を最初からやり直す必要がありません。

Modularity の定義を再掲します:

辺 $(u, v)$ が追加されたとき、$A_{uv}$ が 0→1 に、$k_u$ が $k_u + 1$ に、$k_v$ が $k_v + 1$ に、$m$ が $m + 1$ に変化します。これらの変化は $u$、$v$、および所属コミュニティの内部統計量（$\Sigma_{\text{in}}$、$\Sigma_{\text{tot}}$）にのみ影響します。DynaMo はこの局所性を利用します:

• $u$ と $v$ が 同じコミュニティ に属する場合: コミュニティの内部辺数が 1 増加し、総次数が 2 増加します。DynaMo はコミュニティの $Q$ への寄与を $O(1)$ で更新
• $u$ と $v$ が 異なるコミュニティ に属する場合: $u$ を $v$ のコミュニティに移動させたときの Modularity 利得（およびその逆）を再計算し、利得が正なら移動を実行

DynaMo:
  辺 (u, v, op) が到着するたびに:
    1. グラフ統計量を更新（次数、コミュニティの Σ_in, Σ_tot）
    2. もし op = + (追加):
       a. u, v が同じコミュニティ → 内部辺が増加、Q を更新
       b. u, v が異なるコミュニティ → u の移動の利得を計算:
          gain(u → C_v) = （u が C_v に参加することで得られる内部辺の増分）
                        - （u が C_u を離脱することで失う内部辺の分）
          gain > 0 なら u を C_v に移動
    3. もし op = - (削除):
       a. u, v が同じコミュニティ → 内部辺が減少
       b. コミュニティの連結性を検査。非連結なら分裂
    4. 移動の波及効果: u が移動した場合、u の近傍にも移動の利得を計算（限定的ラベル伝搬）

DynaMo の利点は、Modularity という広く使われた指標を厳密に追跡できる点です。バッチ Louvain とは異なり、各更新で局所的なコミュニティ統計量のみを用いて Modularity 利得を再計算するため、品質の劣化を監視しやすくなっています。

TILES (2017): 三角形ベースの真のストリーミング

Rossetti, Pappalardo, Pedreschi, Giannotti (2017) の TILES は、「ストリーミング」を名前に冠する最も影響力のある手法の一つです。TILES は 三角形の形成 をコミュニティの基本単位とするユニークなアプローチを取ります。

TILES の核心的アイデア

「2 人の人間が繋がっているだけでは、コミュニティとは呼べない。共通の友人を持って初めて、そこに社会的凝集が生まれる」——これが TILES の出発点です。数学的には、辺 $(u, v)$ が到着したとき、$u$ と $v$ が共通の近傍 $w$ を持つ（つまり三角形 $(u, v, w)$ が形成される）場合に限って、$u$、$v$、$w$ を同一コミュニティに属するとみなします。

TILES のアルゴリズム詳細

TILES アルゴリズム:
  データ構造:
    - 隣接リスト adj[v]: 各ノードの現在の近傍集合
    - コミュニティラベル label[v]: 各ノードのコミュニティ集合（重複可）
    - 辺タイムスタンプ ts[(u,v)]: 各辺の最終到着時刻
    - TTL パラメータ τ: 辺の生存時間
 
  辺 (u, v, t) が到着するたびに:
    1. ts[(u,v)] ← t    // タイムスタンプ更新
    2. adj[u] ← adj[u] ∪ {v}, adj[v] ← adj[v] ∪ {u}
    3. 共通近傍 W ← adj[u] ∩ adj[v]
    4. for each w ∈ W:
         // 三角形 (u, v, w) が形成された
         // u, v, w のラベル集合の和集合を取り、3 ノードに割り当て
         merged ← label[u] ∪ label[v] ∪ label[w]
         if merged = ∅:
           merged ← {new_label()}  // 新規コミュニティ
         label[u] ← label[v] ← label[w] ← merged
    5. TTL チェック:
       for each edge (a, b) where t - ts[(a,b)] > τ:
         adj[a] ← adj[a] \ {b}, adj[b] ← adj[b] \ {a}
         // (a,b) の消失が a, b のコミュニティに影響するか確認
         再評価(a, b)

計算量分析

辺 $(u, v)$ の到着に対する TILES の計算量は:

• ステップ 3 の共通近傍の計算: $O(\min(\deg(u), \deg(v)))$（ソート済みリストの共通部分）
• ステップ 4 のラベル更新: $O(|W| \cdot |\text{labels}|)$

最悪ケースは $O(\deg^2)$（$\deg$ = 最大次数）ですが、べき乗則次数分布を持つ現実のネットワークでは、ほとんどのノードの次数は小さいため、平均的なコストは低く抑えられます。

TTL (Time-To-Live) 機構

TILES の最もユニークな特徴は TTL 機構 です。各辺にはタイムスタンプが付与され、一定期間 $\tau$ 内に再度到着しなかった辺は「期限切れ」として除去されます。

TTL の直感的な意味: SNS において、2 人の人間が最後にインタラクションしたのが 1 年前であれば、その関係はもはや「活性的」ではないとみなすべきです。TTL はこの「関係の鮮度」をモデル化し、古くなった辺を自動的にプルーニングします。

TTL の重要な効果:

1. メモリ管理: 無限に成長するグラフのメモリ使用量を制限
2. ノイズ除去: 一時的な偶然の接触と持続的な関係を区別
3. コミュニティの自然な死: 全辺が期限切れになったコミュニティは自然に消滅

パラメータ $\tau$ の選択はドメイン知識に依存します。SNS のメッセージなら $\tau = 30$ 日、学術共著なら $\tau = 5$ 年、金融取引なら $\tau = 1$ 時間といった具合です。

以下のデモで、辺がストリームとして到着する状況でのコミュニティの形成・分裂・維持を確認できます:

delta-screening Louvain (2021): 影響範囲の限定

Zarayeneh と Kalyanaraman (2021) の delta-screening は、既存の Louvain アルゴリズムを増分化するための汎用的なフレームワークです。「どのノードの Modularity 利得が辺の変更によって変わる可能性があるか」を 事前にスクリーニング し、そのノードだけに Louvain の局所移動を適用します。

スクリーニングの原理

辺 $(u, v)$ が追加されたとき、Modularity が変化しうるのは以下のノードに限られます:

1. $u$ と $v$ 自身
2. $u$ と同じコミュニティに属するノードで、$v$ のコミュニティに移動する利得が増加しうるもの
3. $v$ と同じコミュニティに属するノードで、$u$ のコミュニティに移動する利得が増加しうるもの

形式的には、ノード $w$ が「影響を受ける」のは、以下の条件を満たす場合です:

ここで $\Sigma_{\text{in}}^{C'}$ はコミュニティ $C'$ の内部辺の重みの和、$k_{w,\text{in}}^{C'}$ は $w$ からコミュニティ $C'$ への辺の重みの和、$\Sigma_{\text{tot}}^{C'}$ は $C'$ に属する全ノードの次数の和です。

辺 $(u, v)$ の追加は $k_u$、$k_v$、$m$、および $u, v$ が属するコミュニティの $\Sigma_{\text{in}}$、$\Sigma_{\text{tot}}$ のみを変更します。したがって、これらの値に依存するノード——つまり $u$ のコミュニティまたは $v$ のコミュニティに隣接するノード——だけがスクリーニング対象になります。

delta-screening Louvain:
  前提: 現在のコミュニティ割り当て C が存在
  辺 (u, v) が変更されたとき:
    1. スクリーニング:
       affected ← ∅
       for each node w in C_u ∪ C_v ∪ N(u) ∪ N(v):
         if ΔQ(w → best_community) が辺変更前後で異なる:
           affected ← affected ∪ {w}
    2. 局所 Louvain:
       affected のノードに対してのみ Louvain の局所移動フェーズを実行
    3. 集約フェーズ:
       影響を受けたコミュニティに対してのみ集約

実験的な効果

Zarayeneh らの実験では、LFR ベンチマークグラフ（$n = 100{,}000$、平均次数 20）に対して、辺の追加ごとにフル Louvain を実行する場合と比較して 10〜100 倍 の高速化が達成されました。しかも Modularity の品質劣化はほぼゼロ でした。

これは、辺 1 本の変更がグラフ全体のコミュニティ構造に影響することは稀であるという事実を反映しています——ほとんどの辺の追加・削除は局所的な影響しか持たないのです。

ANGEL (2020): マージベースの重複コミュニティ

Rossetti (2020) の ANGEL は、DEMON のアイデアを発展させた増分的手法です。

ANGEL と DEMON の違いは、ANGEL がコミュニティの進化を マージ操作の連鎖 としてモデル化する点です:

ANGEL:
  辺 (u, v) が到着するたびに:
    1. u と v のエゴネットを再構築
    2. エゴネット内で LPA を実行 → ローカルコミュニティ L_u, L_v を抽出
    3. 既存のグローバルコミュニティ集合 G から、L_u, L_v と高い類似度を持つ
       グローバルコミュニティを検索
    4. Jaccard(L, G_i) > θ ならマージ: G_i ← G_i ∪ L
       どの G_i とも類似度が低ければ、L を新しいグローバルコミュニティとして追加

ANGEL の賢い点は、各ステップで ローカルな視点（エゴネット）で発見したコミュニティを、グローバルな知識（既存のグローバルコミュニティ集合）と統合する 2 段階プロセスにあります。

第 IV 部: ストリーミング CD の設計空間

ここまでの個別アルゴリズムの解説を俯瞰すると、ストリーミング CD のアルゴリズム設計には 4 つの独立した次元 が存在することがわかります。

次元 1: 更新戦略

• 全体再計算: 各辺の到着で全体を再計算。品質は最高だがコストも最高
• 局所更新: 変更の影響範囲のみを再計算（OSLOM, delta-screening）
• 遅延更新: 変更をバッファに蓄積し、一定量たまったらバッチで更新（DynaMo のバッチ変形）

次元 2: 時間モデル

• スナップショット: 離散的な時刻のグラフ（第 2 編の Multislice Modularity）
• スライディングウィンドウ: 最近の $W$ 秒/辺のみを保持。古いデータは破棄
• 減衰 (Decay): 各辺の重みが時間とともに指数的に減衰: $w(e, t) = w_0 \cdot e^{-\lambda(t - t_e)}$。TILES の TTL はこの離散版

次元 3: コミュニティの性質

• 排他的 (Disjoint): 各ノードは高々 1 つのコミュニティに所属（LabelRankT, Louvain）
• 重複 (Overlapping): 各ノードが複数のコミュニティに所属可能（DEMON, TILES, ANGEL, OSLOM）
• ファジー (Fuzzy): 所属度が $[0, 1]$ の連続値。DiDiC の拡散ベクトルがこれに近い

次元 4: 品質基準

• Modularity: Configuration Model との比較（DynaMo, delta-screening）
• 統計検定: p 値に基づく有意性（OSLOM）
• 三角形密度: 三角形の共有をコミュニティの定義とする（TILES）
• 情報理論: Map Equation の増分版（動的 Infomap）

各次元の選択は独立であり、理論上は $3 \times 3 \times 3 \times 4 = 108$ 通りの組み合わせが可能です。既存のアルゴリズムはこの空間の一部しかカバーしておらず、未探索の組み合わせが多く残されています。

第 V 部: 各手法の比較と統合的評価

具体例: TILES と LabelRankT の比較

同じ辺ストリームを TILES と LabelRankT がどう処理するかを、5 ノード（A–E）の小さなグラフで比較します。

辺ストリーム: +(A,B), +(B,C), +(A,C), +(C,D), +(D,E), +(C,E)

TILES の処理:

• +(A,B), +(B,C): 三角形なし → コミュニティ未形成
• +(A,C): 三角形 ABC 形成 → コミュニティ 1 = {A, B, C}
• +(C,D), +(D,E): 三角形なし → D, E は未所属のまま
• +(C,E): 三角形 CDE 形成 → コミュニティ 2 = {C, D, E}。C は両方に所属（重複）

結果: {A, B, C} と {C, D, E} の 2 コミュニティ。C が重複メンバー。三角形が形成されるまで D, E はどのコミュニティにも属さなかった点に注目してください。

LabelRankT の処理:

• 初期 LPA で全連結ノードにラベルを割り当て（例: A,B,C に同一ラベル、D,E に別ラベル）
• +(C,E) の到着時: Δ = {C, E} ∪ N(C) ∪ N(E) = {A, B, C, D, E}（全ノード）
• Δ 内でラベル伝搬を実行。C は 4 つの近傍を持ち、多数決により全ノードが同一ラベルに収束しやすい

結果: 全ノード {A, B, C, D, E} が 1 つのコミュニティ。重複なし。

違いのポイント: TILES は三角形を要求するため保守的で、自然に重複コミュニティを生成します。LabelRankT は多数決ベースでノードを排他的に割り当てるため、密に接続された領域を 1 つの大きなコミュニティに統合しがちです。

ベンチマークと評価の課題

ストリーミング CD の評価には、静的な手法とは異なる特有の課題があります:

1. 動的ベンチマークの必要性

静的な LFR ベンチマークは、グラフが変化しないためストリーミング手法の評価には不十分です。動的ベンチマークとして、以下が用いられます:

• Dynamic LFR (Greene, Doyle, & Cunningham, 2010): LFR ベンチマークを時間方向に拡張。各タイムステップでノードがコミュニティ間を移動し、コミュニティの誕生・死・分裂・統合が発生
• RDYN (Rossetti, 2017): ストリーミング設定に特化したベンチマーク。辺の追加・削除がイベントとして生成され、真のコミュニティ構造の経時変化が追跡可能

2. 評価指標

ストリーミング CD では通常の NMI（Normalized Mutual Information）に加えて、以下の指標が重要になります:

• 更新あたりの計算時間: 辺 1 本の到着に対するレスポンスタイム
• NMI の時系列: 真のコミュニティとの一致度がストリームの進行とともにどう変化するか
• コミュニティ安定性: コミュニティ割り当ての時間的変動の大きさ（小さいほど安定）
• 遅延 (lag): 真のコミュニティ構造が変化してから、アルゴリズムがそれを反映するまでの時間差

3. scalability 実験

ストリーミング手法の実用的な価値はスケーラビリティに直結します。評価には:

• スループット: 1 秒あたり何本の辺を処理できるか（辺/秒）
• メモリ使用量: グラフサイズに対するメモリ消費の増加率
• レイテンシ: 辺の到着から結果の更新までの遅延

実践的な選択ガイド

第 VI 部: 近年の最前線と今後の方向性

GNN ベースのストリーミング CD

2020 年代に入り、Graph Neural Network (GNN) をストリーミング設定に適用する研究が急速に進んでいます。

EvolveGCN (Pareja et al., 2020) は、GCN（Graph Convolutional Network）の重みパラメータを RNN（LSTM/GRU）で時間方向に進化させるアーキテクチャです:

ここで $W_t$ は時刻 $t$ における GCN の重み、$H_{t-1}$ は前時刻のノード表現行列です（EvolveGCN-H 変形）。辺ストリームから構築されたスナップショット列に対して、各スナップショットで GCN を適用しつつ、重みを RNN で滑らかに遷移させます。

ROLAND (You et al., 2022) は、より洗練されたアプローチとして、GNN の各層の出力に対して時系列モデリングを適用し、ノード表現を継続的に更新します。

これらの手法の特徴は:

1. ノード特徴量の活用: グラフ構造だけでなく、ノードに付随する属性情報（プロフィール、コンテンツ等）を活用
2. 表現学習との統合: コミュニティ検出を「ノード埋め込みの進化」として捉え、クラスタリング特化の損失関数で学習
3. 帰納的推論: 新しいノードに対しても、学習済みのパラメータで即座にコミュニティを推定可能

ただし、GNN ベースの手法には以下の課題が残っています:

• 計算コスト: GNN のフォワードパスは GPU が必要で、辺 1 本ごとに実行するのはコスト高
• 学習データの必要性: 教師あり/自己教師あり学習のための十分なデータが必要
• 解釈性: なぜある分割が選ばれたのかが不透明

Approximation + Sketch ベースのアプローチ

大規模ストリームに対するもう一つの方向性は、ストリームアルゴリズム の理論的フレームワークを援用するアプローチです。

MinHash / SimHash によるノード間類似度の近似: 各ノードの近傍集合を固定長のハッシュスケッチで要約し、辺の追加・削除に対して $O(1)$ で更新。ノード間の Jaccard 類似度を近似的に計算し、類似度が高いノード対を同一コミュニティにグループ化。

Count-Min Sketch による次数追跡: 辺ストリームにおけるノードの次数を省メモリで追跡し、Modularity の近似計算に利用。

これらの手法は理論的な近似保証（$\epsilon$-$\delta$ 近似など）を持ちますが、コミュニティ検出特化のストリームアルゴリズムとしてはまだ発展途上です。

オープンな研究課題

ストリーミング Community Detection は活発な研究分野であり、以下の方向性が注目されています:

1. 理論的な検出限界: 静的 SBM における Kesten-Stigum 閾値のストリーミング版。「辺を 1 本ずつしか見られない場合、コミュニティ検出はどこまで可能か？」
2. 辺の順序依存性: ストリームにおける辺の到着順序が結果に与える影響の定量化。同じ辺集合でも異なる順序で到着すると異なるコミュニティが得られるのか？
3. スケーラビリティの壁: 数十億辺規模のストリームを単一マシンで処理可能な手法の開発
4. プライバシー保護: 差分プライバシーを保証しながらストリーミング CD を実行する手法。ノードの所属コミュニティが外部に漏洩しないよう保護
5. マルチモーダルストリーム: 辺の追加・削除だけでなく、ノード属性の変化や辺の重み変化も同時に処理

まとめ — ストリーミング CD の統合的視座

3 部作を通じて Community Detection の全体像を振り返ると、静的 (第 1 編) → 動的 (第 2 編) → ストリーミング (本稿) という発展の流れが見えます。

ストリーミング CD の本質的な困難は、不完全な情報に基づく逐次的な意思決定 にあります。バッチ処理ではグラフの全貌が見えていますが、ストリーミングでは「次にどの辺が来るか分からない」状況で、今の辺 1 本の情報だけでコミュニティ割り当てを更新しなければなりません。

しかし、この制約はアルゴリズムの創造性を呼び覚ます源でもあります——三角形の形成をトリガーにする TILES、影響範囲を事前にスクリーニングする delta-screening、エゴネットの民主的投票で決める DEMON——それぞれが「局所的な情報からいかにグローバルな構造を推定するか」という問いに異なる角度から答えています。

ネットワークがますます大規模化・リアルタイム化する現代において、ストリーミング CD はグラフ研究の最前線であり続けるでしょう。

参考文献

• Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 036106.
• Sun, J., Faloutsos, C., Papadimitriou, S., & Yu, P. S. (2007). GraphScope: parameter-free mining of large time-evolving graphs. KDD 2007, 687–696.
• Gehweiler, J., & Meyerhenke, H. (2010). A distributed diffusive heuristic for clustering a virtual P2P supercomputer. IEEE International Parallel & Distributed Processing Symposium (IPDPS), 1–8.
• Xie, J., Chen, M., & Szymanski, B. K. (2013). LabelRankT: Incremental community detection in dynamic networks via label propagation. Workshop on Dynamic Networks Management and Mining (DyNetMM), 25–32.
• Lancichinetti, A., Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011). Finding statistically significant communities in networks. PLoS ONE, 6(4), e18961.
• Coscia, M., Rossetti, G., Giannotti, F., & Pedreschi, D. (2012). DEMON: a local-first discovery method for overlapping communities. KDD 2012, 615–623.
• Zhuang, D., Chang, J. M., & Li, M. (2019). DynaMo: Dynamic community detection by incrementally maximizing modularity. IEEE Transactions on Knowledge and Data Engineering, 33(5), 1934–1945.
• Rossetti, G., Pappalardo, L., Pedreschi, D., & Giannotti, F. (2017). Tiles: an online algorithm for community discovery in dynamic social networks. Machine Learning, 106(8), 1213–1241.
• Rossetti, G. (2020). ANGEL: efficient, and effective, node-centric community discovery in static and dynamic networks. Applied Network Science, 5, 26.
• Zarayeneh, N., & Kalyanaraman, A. (2021). Delta-screening: A fast and efficient technique to update communities in dynamic graphs. IEEE Transactions on Network Science and Engineering, 8(2), 1614–1629.
• Pareja, A., Domeniconi, G., Chen, J., Ma, T., Suzumura, T., Kanezashi, H., Kaler, T., Schardl, T., & Leiserson, C. (2020). EvolveGCN: Evolving graph convolutional networks for dynamic graphs. AAAI 2020, 5363–5370.
• You, J., Du, T., & Leskovec, J. (2022). ROLAND: graph learning framework for dynamic graphs. KDD 2022, 2358–2366.
• Greene, D., Doyle, D., & Cunningham, P. (2010). Tracking the evolution of communities in dynamic social networks. International Conference on Advances in Social Network Analysis and Mining (ASONAM), 176–183.
• Rossetti, G. (2017). RDyn: graph benchmark handling community dynamics. Journal of Complex Networks, 5(6), 893–912.
• Cazabet, R., Amblard, F., & Hanachi, C. (2010). Detection of overlapping communities in dynamical social networks. 2010 IEEE Second International Conference on Social Computing (SocialCom), 309–314.

参考資料（発展的読書）

• Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1–44.
• Rossetti, G., & Cazabet, R. (2018). Community discovery in dynamic networks: a survey. ACM Computing Surveys, 51(2), 1–37.
• Chakrabarti, D., Kumar, R., & Tomkins, A. (2006). Evolutionary clustering. KDD 2006, 554–560.