ストリーミング Community Detection — 辺の到着・削除に合わせてコミュニティーを更新する手法

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

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

ただし第 2 編で扱った「動的ネットワーク」の手法の多くは、離散的なスナップショットを選び、スナップショットごとにバッチ処理でコミュニティー検出を実行します。Twitter/X のフォロー関係、金融取引ネットワーク、IoT センサーネットワークのような現実の大規模ネットワークでは、このやり方は次の 2 点で行き詰まります。

1. スケール: 数十億ノード・数百億辺のグラフで、辺が 1 本変わるたびに Louvain を最初から実行するのは、計算コストが大きすぎて現実的ではありません。
2. リアルタイム性: 不正検知やトレンド予測のように、コミュニティー構造の変化をすぐに把握したい用途では、次のスナップショットを待てません。

ストリーミング・コミュニティー検出 (Streaming Community Detection、以下ストリーミング CD) は、辺が 1 本ずつ到着（または削除）される辺ストリーム (edge stream) に対して、コミュニティー構造を増分的 (incrementally) に更新し続けます。多くの手法に共通するのは、変更された辺の周辺だけを更新し、グラフ全体の再計算を避けるという考え方です。

この記事で扱うこと

• 1 回の更新で再計算する範囲による区別: バッチ再計算、増分的更新、真のストリーミング
• 研究史: LPA と GraphScope から、iLCD・DiDiC・LabelRankT を経てバッチ処理を離れていった経緯
• 代表的なアルゴリズムの仕組みと計算量: OSLOM、DEMON、DynaMo、TILES、delta-screening Louvain、ANGEL
• 設計空間: 更新戦略・時間モデル・コミュニティーの性質・品質基準の 4 つの次元
• 手法の比較と評価の課題、状況に応じたアルゴリズムの選び方
• GNN やスケッチを使う近年のアプローチと、未解決の研究課題

第 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 の手法は、1 回の更新でどこまで再計算するかによって 3 つに分けられます。

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

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

辺 1 本の到着に対して、アルゴリズムの内部状態を定数時間か対数時間で更新します。グラフは走査せず、到着した辺とその直接の近傍の情報だけを使って判断します。TILES は考え方としてはこの分類に入りますが、実際には三角形を見つけるために端点の次数に比例するコストがかかります。

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

ストリーミング CD では、安定性 (stability) と応答性 (responsiveness) を両立させにくいという問題があります。

• 安定性: ランダムな辺の出現・消失といったノイズによって、コミュニティー構造が変わらないこと。小さな変化のたびに割り当てが入れ替わる結果は望ましくありません。
• 応答性: コミュニティーの分裂や新しいコミュニティーの出現など、グラフの構造が実際に変わったときに、それを素早く反映すること。

第 2 編で紹介した Evolutionary Clustering では、パラメーター $\alpha$ がこの 2 つの重みを決めます。

$\alpha$ を大きくすると現在のグラフへの当てはまりが、小さくすると前時刻の分割との類似度が重視されます。ストリーミング設定では、どちらを重視するかを辺 1 本ごとに判断する必要があります。新しく届いた辺が本質的な構造変化の兆候なのか、単なるノイズなのかを、その辺の周辺の情報だけで見分けなければなりません。

第 II 部: 研究史 — バッチ処理から増分的更新へ

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

Raghavan, Albert, Kumara (2007) が提案した Label Propagation Algorithm (LPA) は仕組みが単純で、ストリーミング設定へ拡張しやすいアルゴリズムです。後で紹介する LabelRankT、DEMON、ANGEL も LPA の考え方を使っています。

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

LPA の計算量は $O(km)$（$k$ は収束までの反復回数で、実験では小さいことが多い）です。各ノードの更新には近傍のラベルしか使わないため、辺が追加されたときも関係するノードだけを更新できます。この局所性が、LPA をストリーミング設定へ拡張しやすくしています。

GraphScope (2007): グラフストリームの変化点検出

Sun, Faloutsos, Papadimitriou, Yu (KDD 2007) の GraphScope は、時間とともに変化するグラフのストリームを、パラメーターを設定せずに解析する初期の研究です。最小記述長原理 (MDL) に基づいて、辺ストリームの中でグラフ構造が変わる変化点 (change point) を自動的に検出します。汎用のコミュニティー検出手法というより、MDL に基づく変化点検出と、送信元・送信先グループのモデル化 (source/destination group modeling) を組み合わせた手法ですが、ストリーミンググラフクラスタリングの研究に大きな影響を与えました。

手順は次のとおりです。

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

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

既存のコミュニティー構造では新しいデータを効率よく記述できなくなると、GraphScope はそこを変化点として新しいセグメントを始め、コミュニティー構造を更新します。

iLCD (2010): 局所的な基準による増分的な検出

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

iLCD は、新しい辺が到着するたびに、その端点が既存のコミュニティーに加わるか新しいコミュニティーを作るかを、局所的な品質関数で判定します。辺 $(u, v)$ が到着した場合の処理は次のとおりです。

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

1 つのノードが複数のコミュニティーの参加条件を同時に満たしうるため、iLCD は自然に重複コミュニティーを生成します。また、調べるのは到着した辺の近傍だけなので、ストリーミング設定でも効率よく動作します。

iLCD は、スナップショットを待たずにグラフのイベントが起きるたびに処理する、真にオンラインなコミュニティー検出が可能であることを示しました。後で紹介する TILES も、辺が届くたびに処理します。

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

Gehweiler と Meyerhenke (2010) が提案した DiDiC (Distributed Diffusive Clustering) は、ラベル伝搬とは異なり、拡散によってクラスターを作ります。各ノードは「拡散ベクトル」$\mathbf{d}_v \in \mathbb{R}^k$ を持ち、近傍とのあいだでこのベクトルを局所的に拡散（平均化）させることで、クラスターが形成されます。

DiDiC:
  各ノード v は k 次元の拡散ベクトル d_v を持つ
  初期化: 選んだクラスタ数に対応する seed / load ベクトルを割り当てる
  各ノード 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. 非同期に実行できる: 全ノードを同時に更新する必要がありません。ストリーミング設定では、辺 $(u, v)$ が到着したときに $u$ と $v$（必要ならその近傍）の拡散ベクトルだけを更新すればよく、グラフ全体を走査せずに済みます。
3. 分散環境に向く: 各ノードが自身の状態を独立に管理でき、中央での調整が要りません。

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

Xie, Chen, Szymanski (2013) は LabelRank を動的ネットワーク向けに拡張した LabelRankT を提案しました。通常の LPA と異なり、LabelRank 系の手法はラベル分布を伝搬し、inflation・cutoff・conditional update などの演算を用います。動的版では、計算量の大きい伝搬処理を、辺の変更の影響を受けるノードだけに限定します。

LabelRankT:
  LabelRank のラベル分布でコミュニティを初期化
  辺 (u, v, op) がストリームから到着するたびに:
    1. 影響集合 Δ を構築:
       Δ = {u, v} ∪ N(u) ∪ N(v)  （u, v とその近傍）
    2. Δ 内のノードのみで LabelRank 型の伝搬を反復:
       各 w ∈ Δ:
         近傍から w のラベル分布を更新
         inflation、cutoff、conditional-update ルールを適用
    3. Δ が安定するか更新予算に達するまで局所的に反復
    4. 各ノードの支配的ラベルを出力

LabelRankT の辺 1 本あたりの処理は、グラフ全体ではなく影響集合 $\Delta$ とその周辺の辺に限られます。コストは $O(k \cdot m_\Delta)$（$m_\Delta$ は $\Delta$ 内外で実際に触れる辺数、$k$ は局所反復回数）と見積もれ、端点の次数が有界ならグラフ全体のサイズ $n, m$ には依存しません。

一方で、LabelRankT には次の限界があります。

• LabelRank はラベル分布を決定的に更新するため、LPA のようなランダムな同率処理はありませんが、得られる分割は inflation・cutoff・conditional update の閾値によって変わります。
• 各ノードには支配的なラベルを 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 にはこうした検定の枠組みがありません。また、この検定は Modularity の大域的な解像度スケールに縛られないため、小さなコミュニティーでも統計的に有意であれば検出されます。

一方で、p 値の計算にはコストがかかり、元の OSLOM は軽量なストリーミング手法ではありません。大規模なストリームで局所検定を増分的に使うには、実装上の工夫が必要です。

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) > ε

ステップ 2 で v を除くのは、v が定義上 ego(v) の全メンバーとつながっているからです。v を含めたままだと ego(v) 全体が 1 つのコミュニティーとして検出されます。v を除けば、v の近傍の中にある自然なグループ分けが見えます。たとえば「v の大学の友人」と「v の職場の同僚」は、v を除けば別々のグループになりますが、v がいると 1 つにつながります。

ストリーミング設定では、次の 2 つを再実行するだけで済みます。

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

異なるノードのエゴネットから得たローカルコミュニティーは重なりうるので、DEMON では 1 つのノードが複数のコミュニティーに属せます。重複コミュニティーを扱うための追加の仕組みは要りません。

DynaMo (2019): Modularity の増分追跡

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

辺 $(u, v)$ が変化したとき、ノードをコミュニティー間で移動させる Modularity 利得 (modularity gain) は局所的な情報だけで再計算できます。DynaMo はこの性質を使うので、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 人がつながっているだけではコミュニティーとはみなさず、共通の友人がいるときに初めて社会的なまとまりが生じると考えます。数式で言えば、辺 $(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) が形成された
         // 三角形で支えられた既存コミュニティを拡張。なければ新規作成
         candidate ← (label[u] ∩ label[w]) ∪ (label[v] ∩ label[w]) ∪ (label[u] ∩ label[v])
         if candidate = ∅:
           candidate ← {new_label()}  // この三角形の新規コミュニティ
         for each ℓ ∈ candidate:
           label[u] ← label[u] ∪ {ℓ}
           label[v] ← label[v] ∪ {ℓ}
           label[w] ← label[w] ∪ {ℓ}
    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}|)$

TTL 期限切れの走査を除けば、更新は $O(\min(\deg(u), \deg(v)) + |W| \cdot |\text{labels}|)$ です。コストは端点の次数とラベル更新数に比例します。次数分布がべき乗則に従う現実のネットワークではほとんどのノードの次数が小さいので、平均的なコストは低く抑えられます。

TTL (Time-To-Live) 機構

TILES の特徴的な仕組みが TTL 機構です。各辺にはタイムスタンプが付き、一定期間 $\tau$ のうちに再び到着しなかった辺は「期限切れ」として除去されます。

たとえば SNS で 2 人が最後にやり取りしたのが 1 年前なら、その関係はもう活発ではないとみなせます。TTL はこうした関係の新しさをモデル化し、古くなった辺を自動的に取り除きます。

TTL には次の効果があります。

1. メモリー管理: 成長し続けるグラフのメモリー使用量を一定の範囲に抑えます。
2. ノイズ除去: 一時的な偶然の接触と、続いている関係を区別できます。
3. コミュニティーの消滅: すべての辺が期限切れになったコミュニティーは消えます。

$\tau$ はドメイン知識に基づいて決めます。たとえば SNS のメッセージなら 30 日、学術共著なら 5 年、金融取引なら 1 時間といった値が考えられます。

次のデモは、辺がストリームとして到着するにつれてコミュニティーが形成され、ブリッジ辺の追加・削除を経ても維持される様子を示します。

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

Zarayeneh と Kalyanaraman (2021) の delta-screening は、Louvain など Modularity を最適化する既存のアルゴリズムを増分化するための汎用的なフレームワークです。辺の変更によって 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}}$ だけです。全ノードの利得に共通して入る $m$ を除くと、これらの値に依存するのは $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 らは、辺の変更をタイムステップごとにまとめて処理する実験を、合成ネットワークと実ネットワークで行いました。各タイムステップで Louvain を最初から実行し直す場合と比べて最大 38 倍の高速化が報告され、Modularity もほぼ同じ値に保たれました。ほとんどの辺の追加・削除は局所的な影響しか持たず、辺 1 本の変更でグラフ全体のコミュニティー構造が変わることはまれだからです。

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

Rossetti (2020) の ANGEL は、DEMON のアイデアを発展させたノード中心の手法です。時間とともに変わるネットワーク向けには、拡張版の ArchAngel があります。

ANGEL は DEMON と同じく各ノードのエゴネットから出発し、そこで見つけたローカルなコミュニティーをマージ操作でグローバルなコミュニティー集合にまとめます。

ANGEL（1 つのグラフ）:
  各ノード u について:
    1. u 自身を除いた u のエゴネットを作る
    2. エゴネット内で LPA を実行 → ローカルコミュニティ L を抽出
    3. L と最も重なるグローバルコミュニティ G_i を探す
    4. 重なりが閾値 θ を超えればマージ: G_i ← G_i ∪ L
       超えなければ、L を新しいグローバルコミュニティとして追加
 
ArchAngel（スナップショットで与えられる変化するグラフ）:
  各スナップショット t について:
    1. スナップショット t に ANGEL を実行
    2. t のコミュニティーを t−1 のコミュニティーと重なりで対応づけ、
       各コミュニティーの変化を追跡

ANGEL は、ローカルな視点（エゴネット）で見つけたコミュニティーを、グローバルな知識（グローバルコミュニティー集合）に統合する 2 段階で処理します。ArchAngel は変化を辺ごとではなくスナップショットごとに扱うので、TILES のように辺が届くたびにコミュニティーを更新するわけではありません（ANGEL の README）。

第 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 変種

4 つの次元の選択肢をそのまま掛け合わせると $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 の処理:

• 最初に LabelRank のラベル分布で全連結ノードを初期化（例: A,B,C に同一ラベル、D,E に別ラベル）
• +(C,E) の到着時: Δ = {C, E} ∪ N(C) ∪ N(E) = {A, B, C, D, E}（全ノード）
• Δ 内でラベル分布の局所伝搬を実行。C が両方の密な部分を橋渡しするため、1 つのラベルが影響集合全体で優勢になり得る

結果: 1 つのラベルが優勢になった場合、全ノード {A, B, C, D, E} が 1 つのコミュニティーになります。重複はありません。

違い: TILES は三角形ができるまでコミュニティーを作らないので慎重で、重複コミュニティーをそのまま生成します。LabelRankT は各ノードに支配的ラベルを 1 つ出力するため、局所伝搬によって密につながった領域を 1 つの大きなコミュニティーにまとめがちです。

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

ストリーミング CD の評価には、静的な手法にはない課題が 3 つあります。

静的な LFR ベンチマークではグラフが変化しないため、ストリーミング手法の評価には足りません。動的ベンチマークとしては次のものが使われます。

• Dynamic LFR (Greene, Doyle, & Cunningham, 2010): LFR ベンチマークを時間方向に拡張。各タイムステップでノードがコミュニティー間を移動し、コミュニティーの誕生・消滅・分裂・統合が起こる
• RDyn (Rossetti, 2017): ストリーミング設定向けのベンチマーク。辺の追加・削除がイベントとして生成され、正解のコミュニティー構造の変化を時間に沿って追える

ストリーミング CD では、通常の NMI (Normalized Mutual Information) に加えて次の指標を見ます。

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

ストリーミング手法を実際に使えるかどうかは、スケーラビリティーでほぼ決まります。評価では次の値を測ります。

• スループット: 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$ は時刻 $t$ のノード表現行列です（EvolveGCN-H 変形）。辺ストリームから作ったスナップショット列の各スナップショットに GCN を適用し、重みを RNN でなめらかに遷移させます。

ROLAND (You et al., 2022) は、GNN の各層の出力に時系列モデリングを適用し、ノード表現を継続的に更新します。

GNN をストリーミング CD に使う手法には、次の特徴があります。

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

一方で、GNN ベースの手法には次の課題があります。

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

近似とスケッチに基づくアプローチ

大規模なストリームに対しては、ストリームアルゴリズムの理論的な枠組みを使うアプローチもあります。

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

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

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

未解決の研究課題

未解決の課題として、次のようなものがあります。

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

まとめ — 静的からストリーミングへ

3 部作で扱った手法は、静的 (第 1 編) → 動的 (第 2 編) → ストリーミング (本稿) の順に発展してきました。

ストリーミング CD が難しいのは、情報が不完全なまま逐次的に判断しなければならないからです。バッチ処理ではグラフ全体が見えていますが、ストリーミングでは次にどの辺が来るか分からないまま、いま届いた辺の情報だけでコミュニティー割り当てを更新します。

この制約に対して、各手法は局所的な情報から全体の構造を推定する方法をそれぞれ用意しています。TILES は三角形ができたときだけコミュニティーを作り、delta-screening は影響を受けるノードを事前に絞り込み、DEMON はエゴネットごとの投票でコミュニティーを決めます。

参考文献

• 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.