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

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

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

Community Detection とは、グラフ $G = (V, E)$ が与えられたとき、頂点集合 $V$ を「内部の辺が密で、外部との辺が疎」なグループに分割する問題です。一見単純に聞こえますが、ここには深い数学的・計算論的困難が潜んでいます。この記事では、この問題の歴史的経緯を丁寧に辿りながら、主要なアルゴリズムの本質的なアイデアと、この問題がなぜ「本質的に難しい」のかを解説します。

研究の歴史 — ソシオグラムから 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. グラフが完全に分断されるまで繰り返す
  → デンドログラム（階層的な分割の木）が得られる

計算量は $O(m^2 n)$ で、大規模グラフには適用困難です。内訳として、全辺の betweenness 計算は $O(mn)$（全頂点からの BFS が必要）で、それを辺の除去ごとに最大 $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$: グラフ全体の辺の総数。$2m$ は全頂点の次数を合計したもの（各辺が両端で 1 ずつ数えられるため）
• $c_i$: 頂点 $i$ が所属するコミュニティの番号
• $\delta(c_i, c_j)$: クロネッカーのデルタ。$c_i = c_j$（同じコミュニティ）なら 1、違えば 0。この項があることで、同じコミュニティ内のペアだけ が合計に寄与する

式の読み方 — 3 ステップで理解する:

ステップ 1: $A_{ij}$ は「頂点 $i$ と $j$ の間に 実際に辺があるか」を表します。

ステップ 2: $\frac{k_i k_j}{2m}$ は「もし辺をランダムに張り直したら、$i$ と $j$ が繋がる 確率（期待値）」です。直感的には、次数が高い（友人が多い）ノード同士ほど、ランダムでも繋がりやすいという意味です。

ステップ 3: $A_{ij} - \frac{k_i k_j}{2m}$ は「実際の接続 − ランダムに期待される接続」。この差が正なら「ランダムより強く繋がっている」、負なら「ランダムほどには繋がっていない」ことを意味します。

これを同一コミュニティ内の全ペアについて足し合わせ（$\delta(c_i, c_j)$ で制限）、$\frac{1}{2m}$ で正規化したものが Modularity Q です。

$\frac{k_i k_j}{2m}$ の項は Configuration Model（配置モデル） と呼ばれる帰無モデル（null model）から導かれます。これは「各ノードの次数（友人数）は保ったまま、接続先だけをランダムに組み替えたらどうなるか？」という仮想的な比較基準です。次数列を保存するため、単なるランダムグラフ（Erdős-Rényi モデル）よりも現実的な比較対象になります。

まとめると、Modularity Q は:

「ランダムに比べてどれだけコミュニティ内の結合が密か」を測っています。値の意味は:

• $Q = 0$: コミュニティ構造がランダムと変わらない（構造なし）
• $Q > 0$: ランダムより密な内部結合がある（構造あり）
• $Q \approx 0.3 \sim 0.7$: 実ネットワークで見られる典型的な値
• $Q$ の理論的な範囲は $[-0.5, 1]$ だが、実際には負の値はほとんど見られない

Modularity の功績と限界

Modularity は Community Detection に定量的な評価基準を与え、この分野を爆発的に発展させました。しかし、2 つの根本的な問題も明らかになります:

1. NP 困難性 (Brandes et al., 2008): Modularity の最大化は NP 困難。厳密解は現実的に不可能
2. Resolution Limit (Fortunato & Barthélemy, 2007): 小さなコミュニティを見落とす構造的欠陥

これらについては後のセクションで詳しく解説します。

なお、Modularity の提唱後、最初に実用的な最適化アルゴリズムを示したのは Clauset-Newman-Moore (CNM) の凝集型貪欲法 (2004) です。CNM は計算量 $O(md \log n)$（$d$ はデンドログラムの深さ、$m$ は辺数、$n$ はノード数）で、Girvan-Newman (2002) と Louvain (2008) の間を埋める重要な手法でした。凝集型（agglomerative）とは、最初は各ノードが単独のコミュニティで、$\Delta Q$ が最大のペアを順次統合していくボトムアップのアプローチです。

主要アルゴリズムの詳解

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

Blondel, Guillaume, Lambiotte, Lefebvre が 2008 年に提案した Louvain アルゴリズムは、Community Detection の事実上の標準（de facto standard）となりました。その成功の秘訣は、貪欲法と階層的集約の組み合わせ による卓越したスケーラビリティです。

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

Phase 1 — 局所移動 (Local Moving):

各ノード $i$ について、「このノードを隣接するコミュニティ $C$ に移動したら、Modularity Q はどれだけ変化するか？」を計算します。この変化量が $\Delta Q$ です:

この式も分解して理解しましょう。

各記号の意味:

• $\Sigma_{in}$: コミュニティ $C$ の 内部辺 の重みの合計。$C$ 内のノード同士を繋ぐ辺だけを数えたもの
• $\Sigma_{tot}$: コミュニティ $C$ に 接続する全ての辺 の重みの合計。$C$ 内のノードから出ている辺を全部足したもの（内部辺 + 外部辺）
• $k_{i,in}$: ノード $i$ からコミュニティ $C$ 内のノードへの辺 の重みの合計。「$i$ は $C$ のメンバーとどれだけ繋がっているか？」
• $k_i$: ノード $i$ の次数（$i$ から出ている辺の総数）

式の構造 — 「移動後の Q」−「移動前の Q」:

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

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

直感的には: $k_{i,in}$（$i$ と $C$ の実際の接続）が大きいほど $\Delta Q$ は大きくなります。つまり「$C$ のメンバーと沢山繋がっているノードほど、$C$ に移動するメリットが大きい」——これは直感にも合致します。

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

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

Phase 2 — 集約 (Aggregation):

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

以下のデモでこの 2 フェーズの動作を実際に確認してみましょう:

なぜ速いのか

Louvain の計算量は実質 $O(n \log n)$ です。各ノードの $\Delta Q$ 計算は隣接ノード数に比例し、集約によりグラフサイズが急速に縮小するため、実測で数百万ノードのグラフを数分で処理できます。

Louvain の欠陥

しかし Louvain には根本的な問題があります。Phase 1 の局所移動では、ノードを個別に移動するため、コミュニティが非連結（disconnected）になる 場合があります。つまり、同じコミュニティに属する頂点間にパスが存在しないという、直感に反する結果が生じ得ます。

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

Traag, Waltman, van Eck が 2019 年に Louvain の欠陥を修正して提案した Leiden アルゴリズム は、3 フェーズの構成を持ちます:

1. 局所移動 — Louvain と同様だが、高速キューを使用
2. 精錬 (Refinement) — コミュニティ内部で部分集合の再分割を試行。非連結コミュニティの分割を保証
3. 集約 — 精錬後のコミュニティで縮約

Leiden は Louvain の「速さ」を維持しつつ、全てのコミュニティが連結であることを保証 します。現在では Louvain に代わるゴールドスタンダードとなりつつあります。

3. Label Propagation (2007)

Raghavan, Albert, Kumara が提案した Label Propagation Algorithm (LPA) は、極めてシンプルで高速なアルゴリズムです:

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

計算量は $O(m)$ で最速クラスですが、結果が非決定的 です。ノードの処理順序やタイブレーク（同票の場合の選択）によって結果が変わります。また、同期的更新（全ノードを一斉に更新する方式）の場合、収束が保証されず振動状態に陥ることがあります（非同期更新——ノードを 1 つずつ順に更新する方式——では収束が保証されます）。

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

線形代数を活用するアプローチです。まず グラフラプラシアン $L = D - A$ を構成します:

• $A$: 隣接行列（辺があれば 1、なければ 0）
• $D$: 次数行列（対角行列で、$D_{ii} = k_i$）
• $L = D - A$: ラプラシアン行列。$L$ はグラフの「接続の滑らかさ」を測る行列で、$L$ の固有値が 0 に近いほど「繋がりやすい」構造を持つ

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

この式は「行列 $L$ をベクトル $\mathbf{v}$ に掛けると、$\mathbf{v}$ のスカラー $\lambda$ 倍になる」という特殊なベクトル（固有ベクトル）と値（固有値）の組を見つける問題です。

$L$ の固有値 $\lambda$ を小さい順に並べると、$\lambda_1 = 0$（常に存在）、$\lambda_2$、$\lambda_3$、... となります。ここで重要なのが 2 番目に小さい固有値 $\lambda_2$ に対応する固有ベクトル、通称 Fiedler ベクトル です。

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

利点: 理論的基盤が強固（グラフカットの最小化と等価であることが証明されており、Cheeger 不等式により近似精度の保証がある）

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

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

また、Newman (2006) は モジュラリティ行列 $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$ 内に滞在する確率（+コミュニティから出る確率）
• $H(\mathcal{P}^i)$: コミュニティ $i$ 内での移動パターンのエントロピー

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

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

トレードオフ: コミュニティを細かく分けすぎると第 1 項（コミュニティ間移動）が増え、大きすぎると第 2 項（コミュニティ内移動）が増える。このバランスが最適なコミュニティサイズを決定します。

直感的には、コミュニティ構造がうまく捉えられていれば、ランダムウォーカーはコミュニティ内に長く留まるため、コミュニティ内のノードに短いコードワードを割り当てることで全体の記述長を圧縮できます。これは電話の市外局番のアナロジーで理解できます: 同じ市内（コミュニティ）の電話番号は短い番号で呼べるが、市外（別コミュニティ）にかけるときは市外局番が必要になる。

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

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

Modularity ベースの手法と本質的に異なるパラダイムが 統計的推論 (Statistical Inference) に基づくアプローチです。

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$ が生成される確率」を計算しています。この尤度が最大になるような $\{c_i\}$ と $\omega$ を見つけるのが、SBM の推論の目標です。機械学習で言う最尤推定（MLE）と同じ発想です。

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

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

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

さらに、Peixoto (2014) の 階層的 SBM (Nested SBM) は、SBM 自体を再帰的にブロック構造化することで、ノンパラメトリックなモデル選択を実現し、Modularity の Resolution Limit も回避できます。

Community Detection の本質的な難しさ

ここまでアルゴリズムを見てきましたが、Community Detection がなぜ「本質的に難しい」のかを掘り下げましょう。

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

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

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

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

これらは同じグラフに対して異なる「正解」を返すことがあり、どれが「正しい」かは文脈依存です。つまり、Community Detection は客観的に定義される問題ではなく、暗黙の前提（何をコミュニティと呼ぶか）に依存する のです。

2. NP 困難性

Modularity の最大化が NP 困難であること（Brandes et al., 2008）は、最適解を効率的に見つけることが（P ≠ NP を仮定すれば）不可能であることを意味します。より具体的には、「全ての可能なコミュニティ分割を探索するには指数的な時間が必要」ということです。$n$ 個のノードの全ての可能な分割の総数はベル数 $B_n$（ノード数に対して超指数的に増大）であり、全探索は小さなグラフでも現実的ではありません。実用的なアルゴリズムは全て近似法であり、局所最適に陥るリスクを常に抱えています。

しかし、NP 困難性はある意味で「見せかけの問題」でもあります。何を最適化するかの選択自体が恣意的 であるため、真に難しいのは「何を最適化すべきか」という問題設定そのものなのです。

3. Resolution Limit

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

グラフの総辺数を $m$ とします。Modularity の式を思い出すと、帰無モデルの期待値が $\frac{k_i k_j}{2m}$ ですが、小さなコミュニティではこの期待値の項が非常に小さくなります。そのため、小さなコミュニティを統合しても Q の減少が微小で、統合による他の利得で相殺されてしまうのです。

具体的には、コミュニティの次数合計（コミュニティ内ノードの次数の総和）が $\sqrt{2m}$ 未満の場合、たとえ内部が完全グラフ（クリーク）であっても、Modularity の最適解では隣接するコミュニティと統合されてしまいます。内部辺数に換算すると、おおよそ $\sqrt{m/2}$ 未満のコミュニティが影響を受けます。

例えば、100万辺のグラフでは $\sqrt{2 \times 10^6} \approx 1414$ なので、次数合計が 1414 未満のコミュニティは Modularity 最適化では検出できない可能性があります。

これは マルチスケール構造 を持つ実ネットワークにとって深刻な問題です。社会ネットワークには数人の親密なグループから数千人のコミュニティまで幅広いスケールのグループが共存しています。

Resolution limit に対する対策として:

• Resolution parameter $\gamma$ の導入: $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$ で繰り返し検出し、複数のスケールのコミュニティを同時に把握
• SBM ベースの手法への移行: 帰無モデルの制約を回避

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

2011 年に Decelle らが統計物理の cavity 法（非厳密的手法）により導出し、後に Mossel, Neeman & Sly (2018) および Massoulié (2014) によって厳密に証明された 検出限界 (Detectability Threshold) は、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})$: グラフ全体の平均次数に比例。これが ノイズ（ランダムな変動）に相当。グラフがスパース（辺が少ない）なほどノイズが相対的に大きくなる

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

この不等式が成り立つとき、いかなるアルゴリズムでもコミュニティをランダムよりうまく検出できません（Decelle et al., 2011; 厳密証明は Mossel, Neeman & Sly, 2018）。

この結果は統計物理学のスピングラスの理論と深い関係があり、コミュニティ構造の検出に 相転移 (phase transition) が存在することを示しています。閾値を超えると突然検出が可能になり、それ以下では原理的に不可能——これは「計算困難性」とは異なる、情報理論的な限界 です。

5. Ground Truth の不在

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

• ベンチマーク（LFR 等）を使えば人工的な正解はあるが、実ネットワークの複雑さを反映しない。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$ をとるのは、小さいコミュニティが不当に有利にならないよう正規化するため

Conductance が小さいほど「境界が明確で外に漏れにくい」、つまり良いコミュニティです。

どの目的関数が適切かは、ネットワークの性質と分析の目的によって決まります。これは弱点ではなく、ネットワーク解析では単一の「正解」が存在しないことの反映 です。

現代の展開と未解決問題

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

Label Propagation や Louvain の非決定性に対処するため、コンセンサスクラスタリング (Lancichinetti & Fortunato, 2012) が提案されました。アルゴリズムを複数回実行し、「ノード $i$ と $j$ が同じコミュニティに属する頻度」からコンセンサス行列を構築、これに再度コミュニティ検出を適用して安定した結果を得ます。

高次構造 (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) は時間依存・マルチスケール・多重ネットワークにおけるコミュニティ検出を統一的に定式化しました。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 は原理的に不可能である」ことを理解し、代わりに「目的に応じた適切なツールを選択する」という pragmatic な姿勢に至りました。Louvain/Leiden の実用性、SBM の理論的堅牢性、Infomap のフロー感度——それぞれの強みを理解し、ネットワークの性質と分析目的に合わせて使い分けることが、現代のネットワーク科学者に求められています。

参考文献

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