Community Detection — グラフの中に潜む「仲間」を見つけ出す科学

はじめに — なぜ「コミュニティー」を見つけたいのか

現実世界のネットワークには、ほぼ必ず「仲間のかたまり」が存在します。SNS の友人グループ、Web のテーマの近いページ群、タンパク質相互作用ネットワークの機能モジュール、論文引用ネットワークの研究分野などです。このように密に結合したノードの集団をコミュニティー (community) と呼びます。

Community Detection とは、グラフ $G = (V, E)$ が与えられたとき、ノード（頂点）の集合 $V$ を「内部の辺が密で、外部との辺が疎」なグループに分割する問題です。単純に聞こえますが、「コミュニティー」には普遍的な定義がなく、代表的な指標である Modularity の最大化は NP 困難で、さらにどのアルゴリズムでも検出できない領域まであります。そのため実務では、完璧な手法を探すより、ネットワークの性質と分析の目的に合う手法を選ぶことになります。

研究の歴史 — ソシオグラムから Leiden まで

Community Detection の研究には 100 年近い歴史があります。主な節目は次のタイムラインのとおりです。

前史: グラフ分割問題 (Graph Partitioning)

Community Detection の直接の祖先は、VLSI 回路設計におけるグラフ分割問題です。1970 年に Kernighan と Lin が提案した KL アルゴリズムは、ノード集合を同じ大きさの 2 つの部分に分けるヒューリスティックで、部分をまたぐ辺（カット辺）の数ができるだけ少ない分け方を探します。

Kernighan-Lin アルゴリズム (1970):
  入力: グラフ G = (V, E)、初期 2分割 (A, B) で |A| = |B|
  繰り返し:
    1. 全ノードを「未ロック」にする
    2. n/2 回の交換を順に行う:
       a. 未ロックのペア (a ∈ A, b ∈ B) で交換利得 g(a,b) が最大のものを選択
       b. a と b を交換し、両方を「ロック」（以後このパスでは動かさない）
       c. 累積利得を記録
    3. 累積利得が最大となる接頭辞 k を見つけ、最初の k 個の交換のみ確定
       → このバックトラック機構により局所最適を脱出できる
    4. 改善がなくなるまで繰り返す

KL アルゴリズムは、その時点ではカットを悪化させる交換も実行して先を探索し、累積利得が最大の接頭辞まで巻き戻します。この先読み (look-ahead) によって、単純な貪欲法では抜け出せない局所最適から脱出できます。

ただし、グラフ分割問題と Community Detection は次の点で異なります。

この違いによって、Community Detection は独自の研究分野になりました。コミュニティーの数もサイズも分からない状況で、意味のあるグループを自動的に見つけることが中心的な課題です。

転換点: Girvan-Newman (2002)

2002 年、Michelle Girvan と Mark Newman は、コミュニティー内の辺を探す代わりに、コミュニティー間をつなぐ橋（ブリッジ）を取り除いてグラフを分けるという方法を提案しました。

橋を見分けるのに使うのが辺媒介中心性 (Edge Betweenness Centrality) です。全ノードペア間の最短経路のうち、ある辺を通るものの数をその辺の betweenness と呼びます。コミュニティー間のブリッジ辺には多くの最短経路が集中するため、betweenness が高くなります。

Girvan-Newman アルゴリズム:
  1. 全辺の betweenness を計算
  2. betweenness 最大の辺を除去
  3. betweenness を再計算
  4. グラフが完全に分断されるまで繰り返す
  → デンドログラム（階層的な分割の木）が得られる

ノード数を $n$、辺数を $m$ とすると、全辺の betweenness の計算には全ノードからの幅優先探索（BFS）が必要で $O(mn)$ かかり、これを辺の除去ごとに最大 $O(m)$ 回繰り返すため、計算量は $O(m^2 n)$ です。大規模グラフには適用できませんが、コミュニティー構造を定量的に評価する方向への出発点になりました。

Modularity Q — 「良い分割」とは何か

Girvan-Newman 法はデンドログラムを作りますが、どの階層で切ればよいかは決めてくれません。この問いに答えるため、Newman と Girvan は 2004 年に Modularity (モジュラリティー) Q という指標を定義しました。

定義

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

• $A_{ij}$: 隣接行列の要素。ノード $i$ と $j$ の間に辺があれば 1、なければ 0
• $k_i$: ノード $i$ の次数（$i$ から出ている辺の本数）。人間関係で言えば友人の数
• $m$: グラフ全体の辺の総数。各辺は両端で 1 ずつ数えられるので、全ノードの次数の合計は $2m$
• $c_i$: ノード $i$ が所属するコミュニティーの番号
• $\delta(c_i, c_j)$: クロネッカーのデルタ。$c_i = c_j$（同じコミュニティー）なら 1、違えば 0。この項によって、同じコミュニティー内のペアだけが合計に寄与する

角括弧の中は、次の 2 つの量の差です。

• $A_{ij}$ は、ノード $i$ と $j$ の間に実際に辺があるかを表します。
• $\frac{k_i k_j}{2m}$ は、各ノードの次数を保ったまま辺をランダムに張り直したときに、$i$ と $j$ の間に期待される辺の数です。次数が高い（友人が多い）ノード同士ほど、ランダムでもつながりやすくなります。

差 $A_{ij} - \frac{k_i k_j}{2m}$ が正なら $i$ と $j$ はランダムより強くつながっており、負ならランダムほどにはつながっていません。これを同一コミュニティー内の全ペアについて足し合わせ（$\delta(c_i, c_j)$ で制限）、$\frac{1}{2m}$ で正規化したものが Modularity Q です。

比較基準にしている「次数を保ったまま辺をランダムに張り直したグラフ」は、Configuration Model（配置モデル）と呼ばれる帰無モデル（null model）です。次数列を保存するため、単なるランダムグラフ（Erdős-Rényi モデル）よりも現実的な比較対象になります。

つまり Modularity Q は次のように書けます。

Q は、コミュニティー内の結合がランダムに比べてどれだけ密かを測ります。値は次のように読みます。

• $Q = 0$: コミュニティー内の辺の数が、ランダムに張った場合の期待値と変わらない（構造なし）
• $Q > 0$: ランダムより密な内部結合がある（構造あり）
• $Q \approx 0.3 \sim 0.7$: コミュニティー構造がはっきりしたネットワークで典型的な値 (Newman & Girvan, 2004)
• $Q$ の理論的な範囲は $[-0.5, 1]$ (Brandes et al., 2008) だが、実際には負の値はほとんど見られない

Modularity の功績と限界

Modularity は Community Detection に定量的な評価基準を与え、この分野の研究が急速に広がるきっかけになりました。提唱後に登場した最初の実用的な最適化アルゴリズムは、Clauset-Newman-Moore (CNM) の凝集型貪欲法 (2004) です。凝集型（agglomerative）とは、各ノードを単独のコミュニティーとして始め、統合したときの Q の増加量 $\Delta Q$ が最大のペアを順に統合していくボトムアップの方法です。計算量は $O(md \log n)$（$d$ はデンドログラムの深さ）で、Girvan-Newman (2002) と Louvain (2008) の間を埋める手法でした。

一方で、次の 2 つの根本的な問題も明らかになりました。

1. NP 困難性 (Brandes et al., 2008): Modularity の最大化は NP 困難で、厳密解を現実的な時間で求めることはできない
2. Resolution Limit (Fortunato & Barthélemy, 2007): 小さなコミュニティーを見落とす構造的な欠陥

どちらも「Community Detection の本質的な難しさ」の節で詳しく扱います。

主要アルゴリズムの詳解

1. Louvain アルゴリズム (2008)

Blondel, Guillaume, Lambiotte, Lefebvre が 2008 年に提案した Louvain アルゴリズムは、Community Detection の事実上の標準（de facto standard）になりました。貪欲な局所移動と階層的な集約を組み合わせることで、大規模なグラフにも適用できます。

アルゴリズムの 2 フェーズ

各ノード $i$ について、隣接するコミュニティー $C$ へ移動したときの Modularity Q の変化量 $\Delta Q$ を計算します。

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

• $\Sigma_{in}$: コミュニティー $C$ の内部辺（$C$ 内のノード同士をつなぐ辺）の重みの合計。各辺を両端から 1 回ずつ、計 2 回数える
• $\Sigma_{tot}$: コミュニティー $C$ に接続する全ての辺の重みの合計。$C$ 内のノードから出ている辺を内部辺・外部辺の区別なく足したもの
• $k_{i,in}$: ノード $i$ から $C$ 内のノードへの辺の重みの合計。$i$ が $C$ のメンバーとどれだけつながっているかを表す
• $k_i$: ノード $i$ の次数（$i$ から出ている辺の総数）

式は「移動後の寄与」から「移動前の寄与」を引いた形をしています。

$\Delta Q = [\text{移動後の Modularity への寄与}] - [\text{移動前の Modularity への寄与}]$

• 前半の角括弧は、ノード $i$ が $C$ に加わった後の、$C$ の Modularity への寄与です
  • $\frac{\Sigma_{in} + 2k_{i,in}}{2m}$: $i$ と $C$ 内ノードを結ぶ $k_{i,in}$ 本分の辺が内部辺になる。両端で数えるので $2k_{i,in}$ 増える
  • $\left(\frac{\Sigma_{tot} + k_i}{2m}\right)^2$: 期待値の項も $i$ の次数分だけ増える
• 後半の角括弧は移動前の寄与で、$C$ と $i$ がそれぞれ独立に持っていた寄与の合計です

$C$ のメンバーと多くつながっているノードほど（$k_{i,in}$ が大きいほど）、$C$ に移動したときの $\Delta Q$ は大きくなります。

各ノードは、$\Delta Q$ が最大かつ正となるコミュニティーに移動します。全ノードを順に処理し、移動がなくなるまで繰り返します。

実際の実装では、ノードを現在のコミュニティーから取り出すコストと、新しいコミュニティーに挿入する利得の 2 段階で $\Delta Q$ を計算します。上の式は、孤立ノード（自分だけのコミュニティー）を $C$ に挿入する場合の利得です。

Phase 1 で得られた各コミュニティーを 1 つの「超ノード」に縮約します。コミュニティー内辺は自己ループ、コミュニティー間辺は超辺になります。この縮約グラフに対して再び Phase 1 を適用します。

次のデモで、2 つのフェーズの動きを追えます。

なぜ速いのか

局所移動で全ノードを 1 巡するコストは、調べる隣接辺の数にほぼ比例します。また、集約するたびにコミュニティー数が急減するので、計算時間の大半は最初の局所移動と集約に集中します。原論文 (Blondel et al., 2008) によると、人工的なモジュール構造を持つ大規模ネットワークでのシミュレーションから、典型的な疎なデータでは計算量がネットワークの規模に対して線形になることが示唆されています。これは実験から得られた傾向で、最悪計算量の保証ではありません。同じ論文では、1 億 1800 万ノード・約 10 億辺の Web グラフを 152 分で処理しています。

Louvain の欠陥

Louvain には根本的な問題もあります。Phase 1 ではノードを個別に動かし、その後の集約で内部構造が見えなくなるため、コミュニティーの結合が極端に弱くなったり、非連結（disconnected）になったりすることがあります。非連結とは、同じコミュニティーに属するのに、コミュニティー内を通るパスでは互いに行き来できないノードがある状態です。Traag ら (2019) は、実ネットワークでもこの現象が起こることを報告しています。

2. Leiden アルゴリズム (2019)

Traag, Waltman, van Eck が 2019 年に Louvain の欠陥を修正するために提案した Leiden アルゴリズムは、次の 3 フェーズで構成されます。

1. 局所移動 — Louvain と同様だが、近傍が変化したノードだけをキューに入れて再訪問する
2. 精錬 (Refinement) — 集約前にコミュニティー内部を部分分割し、非連結または結合の弱い部分をそのまま持ち越さない
3. 集約 — 精錬後のコミュニティーで縮約

Leiden は Louvain の速さを保ったまま、各反復後のコミュニティーが内部で連結であることを保証します。反復を続けると、コミュニティー内のどの部分集合も局所最適に割り当てられた分割に近づきます。Modularity が高いだけでなく、よく結合したコミュニティーが得られるため、Louvain に代わる標準になりつつあります。

3. Label Propagation (2007)

Raghavan, Albert, Kumara が提案した Label Propagation Algorithm (LPA) は、次のように単純な規則で動く高速なアルゴリズムです。

Label Propagation:
  1. 各ノードにユニークなラベルを割り当て
  2. ランダムな順序で各ノードを処理:
     - 隣接ノードの中で最も多いラベルに更新
  3. ラベルが変化しなくなるまで繰り返す
  → 同じラベルのノード群がコミュニティ

1 反復あたりの計算量はほぼ $O(m)$ で最速の部類ですが、結果は非決定的で、ノードの処理順序やタイブレーク（同票の場合の選択）によって変わります。全ノードを一斉に更新する同期的更新では振動状態に陥ることがあるため、実用上はノードを 1 つずつ順に更新する非同期更新がよく使われます。

4. Spectral Clustering（スペクトラルクラスタリング）

線形代数を使う方法です。まずグラフラプラシアン $L = D - A$ を作ります。

• $A$: 隣接行列（辺があれば 1、なければ 0）
• $D$: 次数行列（対角行列で、$D_{ii} = k_i$）

この $L$ を固有値分解します。

固有値分解は、行列 $L$ を掛けても向きが変わらず、スカラー $\lambda$ 倍になるだけのベクトル $\mathbf{v}$（固有ベクトル）と、その倍率 $\lambda$（固有値）の組を求める問題です。

$L$ の固有値を小さい順に並べると、$\lambda_1 = 0$（常に存在）、$\lambda_2$、$\lambda_3$、... となります。固有値 0 の個数は連結成分の数に等しく、0 に近い固有値が多いほど、グラフは互いに弱くしかつながっていない部分に分かれやすくなります。分割に使うのは、2 番目に小さい固有値 $\lambda_2$ に対応する固有ベクトル、通称 Fiedler ベクトルです。

Fiedler ベクトルの各成分は各ノードに対応する実数値で、同じコミュニティーのノードには近い値、異なるコミュニティーのノードには離れた値が割り当てられる傾向があります。そこで、成分の正負でノードを 2 分割できます。$k$ 個のコミュニティーを見つけたい場合は、最小の $k$ 個の固有ベクトルでノードを $k$ 次元空間に埋め込み、k-means などでクラスタリングします。

利点: 理論的な基盤がある。グラフカット最小化の連続緩和として導かれ、Cheeger 不等式によって Fiedler ベクトルによる 2 分割の品質に保証がある

欠点: コミュニティー数 $k$ を事前に指定する必要がある。完全な固有値分解の計算量は $O(n^3)$ だが、疎グラフでは Lanczos 法などの反復法で必要な $k$ 個の固有ベクトルだけを $O(k \cdot m)$ で計算できる

実用上は、組合せ的ラプラシアン $L = D - A$ よりも正規化ラプラシアン $L_{sym} = D^{-1/2}LD^{-1/2}$ や $L_{rw} = D^{-1}L$ がよく使われます（Shi & Malik, 2000）。正規化版は、次数分布が不均一なグラフでも安定した結果を返します。

Newman (2006) は、Modularity 行列 $B_{ij} = A_{ij} - k_i k_j / 2m$ の主要固有ベクトルを使って Modularity を最適化できることを示しました。$B_{ij}$ は Modularity Q の式の $\sum$ の中にある $A_{ij} - \frac{k_i k_j}{2m}$ そのものです。目的関数は異なりますが、Modularity 最適化の一部の手法とスペクトラル法は、固有ベクトルで分割するという同じ線形代数の道具を共有しています。

5. Infomap — 情報理論的アプローチ (2008)

Rosvall と Bergstrom が提案した Infomap は、ランダムウォークの経路を最も効率よく記述（圧縮）するコミュニティー構造を見つけます。

中心にあるのは次の Map Equation（マップ方程式）です。

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

• $M$: コミュニティーの分割方法（最適化の対象）
• $c$: コミュニティー数
• $L(M)$: 分割 $M$ のもとでランダムウォークを記述するのに必要な平均コード長（小さいほど良い）
• $q_{\curvearrowleft}$: ランダムウォーカーがコミュニティー間を移動する確率の合計
• $H(\mathcal{Q})$: コミュニティー間の移動パターンのエントロピー（不確実さ）
• $p_{\circlearrowleft}^i$: ランダムウォーカーがコミュニティー $i$ 内のノードにいる確率と、$i$ から出る確率の和
• $H(\mathcal{P}^i)$: コミュニティー $i$ 内での移動パターンのエントロピー

第 1 項 $q_{\curvearrowleft} H(\mathcal{Q})$ は、コミュニティー間の移動を記述するコストです。コミュニティー間の移動が頻繁だと、次にどのコミュニティーへ行くかを記述するのに多くのビットが必要になります。

第 2 項 $\sum p_{\circlearrowleft}^i H(\mathcal{P}^i)$ は、各コミュニティー内部での移動を記述するコストです。コミュニティーが小さければ内部ノードが少なく、短いコードで記述できます。

コミュニティーを細かく分けすぎると第 1 項が増え、大きくしすぎると第 2 項が増えます。この 2 項のバランスでコミュニティーの大きさが決まります。

コミュニティー構造をうまく捉えた分割では、ランダムウォーカーがコミュニティー内に長く留まります。コミュニティー内のノードには短いコードワードを割り当てれば済むので、全体の記述長が短くなります。電話の市外局番と同じ仕組みで、同じ市内（コミュニティー）には短い番号でかけられ、市外（別コミュニティー）にかけるときだけ市外局番が必要になります。

Modularity がランダムモデルとの比較という統計的な視点を取るのに対し、Infomap は情報圧縮という情報理論的な視点から問題を定式化しています。ランダムウォークの流れを直接扱うので、有向グラフやフロー構造を持つネットワークに特に適しています。

6. Stochastic Block Model (SBM) — 統計的推論アプローチ

統計的推論 (Statistical Inference) に基づくアプローチは、Modularity ベースの手法とは根本的に異なる考え方を取ります。代表的な SBM は、次のような生成モデルです。

1. 各ノードはコミュニティー $c_i \in \{1, ..., k\}$ に属する
2. コミュニティー $r$ と $s$ の間の辺の確率は $\omega_{rs}$ で決まる
3. 観測されたグラフから、最もありそうなコミュニティー割り当てとパラメーターを推論する

尤度は次の式で表されます。

• $\omega_{c_i c_j}$: コミュニティー $c_i$ と $c_j$ の間に辺ができる確率。同じコミュニティー内では高く、異なるコミュニティー間では低いのが典型的なコミュニティー構造
• $A_{ij}$: 実際のグラフで辺があるか（0 か 1）
• $\omega_{c_i c_j}^{A_{ij}}$: 辺がある場合（$A_{ij}=1$）に寄与する、辺が存在する確率 $\omega$
• $(1 - \omega_{c_i c_j})^{1-A_{ij}}$: 辺がない場合（$A_{ij}=0$）に寄与する、辺が存在しない確率 $1-\omega$
• $\prod_{i < j}$: 全てのノードペアについての積（同時確率）

この式は、コミュニティー割り当て $\{c_i\}$ と辺確率行列 $\omega$ のもとで、観測されたグラフ $G$ が生成される確率です。SBM の推論では、この尤度を最大にする $\{c_i\}$ と $\omega$ を探します。機械学習の最尤推定（MLE）と同じ考え方です。

Degree-Corrected SBM (Karrer & Newman, 2011) は、ノードの次数のばらつきを考慮した拡張です。実ネットワークの次数分布はべき乗則に従うことが多く、元の SBM ではこれを適切にモデル化できません。

SBM の推論:
  パラメータ: コミュニティ割り当て {c_i}, 辺確率行列 ω
  目的: 事後確率 P({c_i}, ω | G) の最大化
  手法: 期待値最大化法 (EM)、変分推論、MCMC、Belief Propagation

SBM の最も重要な特徴はモデル選択です。コミュニティー数 $k$ も推論の対象とし、過剰適合を避けるために記述長最小化（Minimum Description Length）などの基準を使います。これにより、コミュニティー構造が本当に存在するのかという問いに答えられます。

Peixoto (2014) は、Resolution Limit が Modularity 最適化だけでなく、通常の SBM のモデル選択にも現れることを指摘しました。同じ論文の階層的 SBM (Nested SBM) は、SBM 自体を再帰的にブロック構造化してネットワークの階層全体を記述することで、ノンパラメトリックなモデル選択を実現し、この限界も回避します。

Community Detection の本質的な難しさ

ここまでのアルゴリズムはそれぞれ異なる目的関数を最適化しますが、どれを使っても避けられない難しさがあります。

1. 問題の不良設定性 (Ill-Definedness)

最も根本的な困難は、「コミュニティー」の普遍的な定義が存在しないことです。

「コミュニティー内が密で、コミュニティー間が疎」という直感は共有されていますが、それを数学的に定式化する方法は無数にあります。

• カット辺の最小化: グラフ分割の伝統
• 内部密度の最大化: Modularity 的な発想
• ランダムウォークの居住時間: Infomap の発想
• 確率モデルの適合度: SBM の発想
• クリーク的構造: 部分グラフの密度に注目

これらは同じグラフに対して異なる「正解」を返すことがあり、どれが正しいかは、分析の文脈で何をコミュニティーと呼ぶかによって決まります。

2. NP 困難性

Modularity の最大化は NP 困難です（Brandes et al., 2008）。P ≠ NP を仮定すれば、最適解を効率的に見つけるアルゴリズムは存在しません。$n$ 個のノードの分割の総数はベル数 $B_n$ で、ノード数に対して超指数的に増えるため（$B_{30}$ は約 $8.5 \times 10^{23}$）、全探索は数十ノードのグラフでも現実的ではありません。実用的なアルゴリズムはどれも近似法で、局所最適に陥るリスクを常に抱えています。

とはいえ、NP 困難性はある意味で見かけ上の問題でもあります。何を最適化するかの選択自体が恣意的なので、本当に難しいのは何を最適化すべきかという問題設定のほうです。

3. Resolution Limit

Fortunato と Barthélemy (2007) が発見した Resolution Limit は、Modularity ベースの手法に対する本質的な批判です。

グラフの総辺数を $m$ とします。帰無モデルで期待される辺の数 $\frac{k_i k_j}{2m}$ は $m$ に反比例するので、大きなグラフの中の小さな 2 つのコミュニティーの間では、期待される辺の数が 1 本未満になり得ます。そのとき、2 つの間に辺が 1 本あるだけで、統合したほうが Q が大きくなります。

統合が起こるかどうかは、コミュニティーの大きさだけでなく周囲のグラフ構造にも左右されます。Fortunato と Barthélemy は、クリーク（どの 2 ノードも辺で結ばれた部分グラフ）を 1 本ずつの辺で環状につないだ構成 (ring of cliques) を例に挙げています。この構成では、内部辺数が $\sqrt{m}$ スケールを下回るクリークは、明確なコミュニティーであるにもかかわらず、Modularity 最適解で隣のクリークと統合され得ます。この境界はよく「内部辺が約 $\sqrt{m/2}$ 本未満」、あるいは「内部次数合計が約 $\sqrt{2m}$ 未満」と要約されます。

例えば 100 万辺規模のグラフでは $\sqrt{2 \times 10^6} \approx 1414$ なので、内部次数合計がこれより小さいコミュニティーは、周囲の結合パターンによっては Modularity 最適化で区別できない可能性があります。

実ネットワークの多くはマルチスケール構造を持つため、この限界は深刻です。例えば社会ネットワークには、数人の親密なグループから数千人のコミュニティーまで、幅広い大きさのグループが共存しています。

Resolution Limit には次のような対策があります。

• Resolution parameter $\gamma$ の導入 (Reichardt & Bornholdt, 2006): $Q_\gamma = \frac{1}{2m} \sum_{ij} \left[ A_{ij} - \gamma \frac{k_i k_j}{2m} \right] \delta(c_i, c_j)$ $\gamma$ は拡大鏡の倍率のように働きます。$\gamma > 1$ ではランダムモデルのペナルティーが強まり、より小さなコミュニティーが検出されやすくなります。$\gamma < 1$ では大きなコミュニティーが検出されます
• マルチスケール解析: 異なる $\gamma$ で繰り返し検出し、複数のスケールのコミュニティーを同時に把握する
• Nested SBM への移行: 帰無モデルとの比較を使わず、階層的なモデル選択で小さなコミュニティーまで検出する (Peixoto, 2014)

4. 検出限界 — 原理的に検出できない領域

検出限界 (Detectability Threshold) は、Decelle ら (2011) が統計物理の cavity 法（数学的に厳密ではない手法）で導いた閾値で、後に数学的に証明されました。特定のアルゴリズムの性能ではなく、どのアルゴリズムにも越えられない限界を示した点で、Community Detection の理論の中でも特に重要です。

同じ大きさの 2 コミュニティーからなる SBM で、コミュニティー内の辺確率パラメーターを $c_{in}/n$、コミュニティー間の辺確率パラメーターを $c_{out}/n$ とします（各ノードのコミュニティー内期待次数は $\approx c_{in}/2$、コミュニティー間期待次数は $\approx c_{out}/2$ で、平均次数は $(c_{in} + c_{out})/2$）。次の不等式が成り立つとき、ノード数が十分大きければ、どのアルゴリズムでもコミュニティーをランダムな割り当てよりうまく検出できません。

• 左辺 $(c_{in} - c_{out})^2$: コミュニティー内とコミュニティー間の辺確率パラメーターの差の 2 乗。コミュニティー構造の強さ、つまりシグナルに相当し、$c_{in}$ と $c_{out}$ の差が大きいほど内と外の違いがはっきりする
• 右辺 $2(c_{in} + c_{out})$: 平均次数に比例する量。ランダムな変動、つまりノイズに相当する。$c_{in}$ と $c_{out}$ を同じ比率で小さくすると左辺は 2 乗で、右辺は 1 乗で小さくなるので、グラフが疎（辺が少ない）なほど、ノイズはシグナルに比べて相対的に大きくなる

この不等式は、シグナルがノイズに埋もれる条件です。コミュニティー内の接続がコミュニティー間の接続とあまり変わらないときや、グラフが疎すぎるときには、コミュニティーの痕跡がランダムな揺らぎに消されてしまいます。

この結果は統計物理学のスピングラスの理論と深い関係があり、コミュニティー構造の検出に相転移 (phase transition) が存在することを示しています。閾値を下回ると検出は原理的に不可能で、このことは Mossel, Neeman & Sly (2015) が証明しました。閾値を上回ると検出は突然可能になり、効率的な（多項式時間の）アルゴリズムで検出できることを Massoulié (2014) と Mossel, Neeman & Sly (2018) が独立に証明しています。計算に時間がかかるという計算困難性とは違い、閾値を下回る領域での不可能性は情報理論的な限界です。

5. Ground Truth の不在

機械学習の分類問題とは異なり、Community Detection には一般に正解ラベル（ground truth）が存在しません。

• LFR (Lancichinetti-Fortunato-Radicchi, 2008) ベンチマークは、次数分布とコミュニティーサイズ分布の両方がべき乗則に従う合成グラフを生成し、実ネットワークの統計的性質をある程度模倣できるため、標準的なベンチマークとして広く使われている。ただし、こうしたベンチマークの正解は人工的に与えたもので、実ネットワークの複雑さまでは反映しない
• メタデータ（論文の分野、ユーザーの属性など）を正解として使うことがあるが、メタデータに基づくグループとネットワーク構造から導かれるコミュニティーは必ずしも一致しない（Peel, Larremore & Clauset, 2017）
• NMI（正規化相互情報量）や ARI（調整ランド指数）などの評価指標は、正解がある前提で設計されている

SBM ベースのアプローチでは、モデルの適合度によって正解なしでも結果を評価できますが、モデルの仮定自体が正しい保証はありません。

6. 重複コミュニティー (Overlapping Communities)

現実のネットワークでは、ノードが複数のコミュニティーに同時に属するのが自然です。例えば大学の研究者は、「機械学習」と「計算理論」の両方のコミュニティーに属することがあります。

COPRA、BigCLAM、Mixed-Membership SBM など重複を許すアルゴリズムもありますが、定式化と評価はさらに難しくなります。重複の度合いをどう測るか、何をもって正しい重複構造とするかは未解決の問題です。

Modularity 以外の目的関数 — なぜ多様なアプローチが存在するのか

Modularity は Community Detection で最も広く使われる指標ですが、手法ごとに使う目的関数は異なります。「コミュニティー」の捉え方が異なるためです。

Conductance の式の各項は次のとおりです。

• $\text{cut}(S, \bar{S})$: コミュニティー $S$ とその外部 $\bar{S}$ を横断する辺の数（境界線をまたぐ辺の数）
• $\text{vol}(S)$: $S$ 内のノードの次数の合計（コミュニティーの「ボリューム」）
• $\min$ をとるのは、$S$ と $\bar{S}$ を対称に扱い、グラフの大半を含む集合がボリュームの大きさだけで低い値を得ないようにするため

Conductance が小さいほど境界が明確で外に漏れにくく、良いコミュニティーだとみなされます。

どの目的関数が適切かは、ネットワークの性質と分析の目的によって決まります。

現代の展開と未解決問題

コンセンサスクラスタリング

Label Propagation や Louvain の結果は、ノードの処理順序によって変わります。この非決定性に対処するため、コンセンサスクラスタリング (Lancichinetti & Fortunato, 2012) が提案されました。アルゴリズムを複数回実行し、ノード $i$ と $j$ が同じコミュニティーに属した頻度からコンセンサス行列を作ります。この行列にもう一度 Community Detection を適用して、安定した結果を得ます。

高次構造 (Higher-Order) に基づく検出

従来のアプローチはペアワイズ（2 ノード間）の辺のみを考慮しますが、モチーフ（特定の部分グラフパターン）に基づく Community Detection も発展しています (Benson, Gleich & Leskovec, 2016)。例えば三角形の密度に基づくコミュニティーは、単なる辺密度では捉えられない構造を明らかにします。

GNN ベースのアプローチ

Graph Neural Network (GNN) を用いた Community Detection も研究されています (Tsitsulin et al., 2023)。ノードの特徴量を学習し、コミュニティー割り当てをエンドツーエンドで最適化するアプローチです。Modularity などの教師なし目的関数を微分可能にして勾配降下で最適化する手法や、対照学習を使う手法がありますが、モデルの解釈性や汎化性には課題が残っています。

動的・多重ネットワーク

時間とともに変化するネットワークでは、コミュニティーの誕生・成長・分裂・消滅を追跡する必要があり、検出はさらに難しくなります。Mucha et al. (2010) は、時間依存・マルチスケール・多重ネットワークでの Community Detection を統一的に定式化しました。temporal modularity やスナップショット間の対応付けなどが研究されています。

大規模分散処理

SNS の友人関係や Web グラフのような数十億ノード規模のネットワークは、単一マシンでは処理できません。MapReduce や Pregel に基づく分散 Louvain/Leiden の研究が進んでいます。

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

ここまでの比較を踏まえた、状況ごとの推奨手法です。

まとめ

Community Detection は「グラフの中に隠れた構造を見つける」という単純そうな問題ですが、次のような本質的な難しさを抱えています。

1. 定義の曖昧さ: 「コミュニティー」の普遍的な定義が存在しない
2. 計算困難性: Modularity 最大化は NP 困難
3. Resolution Limit: スケールに依存した検出の限界
4. 検出限界: 情報理論的に検出不可能な領域の存在
5. Ground Truth の不在: 正解が分からない問題を「解く」難しさ
6. 重複構造: 現実はハード分割では捉えきれない

100 年近い研究を経て、完璧な Community Detection は原理的に不可能だということが分かり、目的に応じて適切なツールを選ぶという実用的な姿勢が定着しました。大規模なグラフを速く分割するなら Louvain/Leiden、コミュニティー数や構造の有無まで推論するなら SBM、フローを持つネットワークなら Infomap が向いています。

シリーズの続き: 第 2 編では高次構造・動的ネットワーク・多重ネットワークを扱います。さらに 第 3 編ではストリーミング Community Detection を扱います。

参考文献

• Kernighan, B. W., & Lin, S. (1970). An efficient heuristic procedure for partitioning graphs. Bell System Technical Journal, 49(2), 291–307.
• Shi, J., & Malik, J. (2000). Normalized cuts and image segmentation. IEEE TPAMI, 22(8), 888–905.
• Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. PNAS, 99(12), 7821-7826.
• Newman, M. E. J., & Girvan, M. (2004). Finding and evaluating community structure in networks. Physical Review E, 69(2), 026113.
• Clauset, A., Newman, M. E. J., & Moore, C. (2004). Finding community structure in very large networks. Physical Review E, 70(6), 066111.
• Newman, M. E. J. (2006). Modularity and community structure in networks. PNAS, 103(23), 8577-8582.
• Reichardt, J., & Bornholdt, S. (2006). Statistical mechanics of community detection. Physical Review E, 74(1), 016110.
• Brandes, U., et al. (2008). On modularity clustering. IEEE TKDE, 20(2), 172-188.
• Fortunato, S., & Barthélemy, M. (2007). Resolution limit in community detection. PNAS, 104(1), 36-41.
• 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.
• Blondel, V. D., et al. (2008). Fast unfolding of communities in large networks. JSTAT, P10008.
• Rosvall, M., & Bergstrom, C. T. (2008). Maps of random walks on complex networks reveal community structure. PNAS, 105(4), 1118-1123.
• Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008). Benchmark graphs for testing community detection algorithms. Physical Review E, 78(4), 046110.
• Fortunato, S. (2010). Community detection in graphs. Physics Reports, 486(3-5), 75-174.
• Mucha, P. J., et al. (2010). Community structure in time-dependent, multiscale, multiplex networks. Science, 328(5980), 876–878.
• Karrer, B., & Newman, M. E. J. (2011). Stochastic blockmodels and community structure in networks. Physical Review E, 83(1), 016107.
• Decelle, A., et al. (2011). Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Physical Review E, 84(6), 066106.
• Lancichinetti, A., & Fortunato, S. (2012). Consensus clustering in complex networks. Scientific Reports, 2, 336.
• Massoulié, L. (2014). Community detection thresholds and the weak Ramanujan property. STOC 2014, 694–703.
• Peixoto, T. P. (2014). Hierarchical block structures and high-resolution model selection in large networks. Physical Review X, 4(1), 011047.
• Mossel, E., Neeman, J., & Sly, A. (2015). Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162(3–4), 431–461.
• Benson, A. R., Gleich, D. F., & Leskovec, J. (2016). Higher-order organization of complex networks. Science, 353(6295), 163–166.
• Fortunato, S., & Hric, D. (2016). Community detection in networks: A user guide. Physics Reports, 659, 1-44.
• Peel, L., Larremore, D. B., & Clauset, A. (2017). The ground truth about metadata and community detection in networks. Science Advances, 3(5), e1602548.
• Mossel, E., Neeman, J., & Sly, A. (2018). A proof of the block model threshold conjecture. Combinatorica, 38(3), 665–708.
• Traag, V. A., Waltman, L., & van Eck, N. J. (2019). From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports, 9, 5233.
• Tsitsulin, A., et al. (2023). Graph clustering with graph neural networks. JMLR, 24(127), 1–21.