モジュラリティ最大化｜ネットワーク科学

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：コミュニティ検出とは　|　関連：Louvain法・Leiden法・configurationモデル・次数保存ヌルモデル

要点（BLUF）

モジュラリティ $Q$ ：実際の内部エッジ割合から「次数を保ったランダムグラフでの期待値」を引いた量。
$Q$ が大きいほど良い分割。 $Q$ の最大化がコミュニティ検出の標準的な目的関数。
ただし NP困難で、解像度限界（小さなコミュニティを見逃す）という弱点もある。

概念：ランダムより密ならコミュニティ

「内部エッジが多い＝良いコミュニティ」と言いたいけれど、密なネットワークなら何で割ってもエッジは多い。だから基準が要ります。モジュラリティは「同じ次数列を持つランダムグラフ（ヌルモデル、configurationモデル・次数保存ヌルモデル）と比べて、内部エッジがどれだけ余計に多いか」で良さを測ります。偶然では説明できない密さこそがコミュニティの証拠だ、という発想です。

数式による定義

エッジ総数を $m$ 、ノード $i,j$ が同じコミュニティなら $\delta(c_i,c_j)=1$ として、

Q = \frac{1}{2m} \sum_{i,j} \left( A_{ij} - \frac{k_i k_j}{2m} \right) \delta(c_i, c_j)

$A_{ij}$ ：実際にエッジがあるか（0/1）。
$\dfrac{k_i k_j}{2m}$ ：次数を保ったランダムグラフで $i,j$ 間にエッジが期待される本数（configurationモデルの期待値）。
$\delta(c_i,c_j)$ ：同じコミュニティのペアだけ和に入れる。

つまり $Q$ は「同じコミュニティ内で、実際のエッジ − ランダム期待値」を全ペアで足したもの。 $Q$ は $[-1/2, 1]$ の範囲をとり、経験的に $0.3$ を超えると有意なコミュニティ構造があると見なされます。

コードで確認

import networkx as nx
import numpy as np
from networkx.algorithms.community import modularity, greedy_modularity_communities

G = nx.karate_club_graph()
clubs = nx.get_node_attributes(G, "club")
mr = set(n for n in G if clubs[n] == "Mr. Hi")

# 実際の2派閥分割
part_true = [mr, set(G.nodes()) - mr]
print("実派閥分割の Q =", round(modularity(G, part_true), 4))

# でたらめな2分割
rng = np.random.default_rng(0)
nodes = list(G.nodes()); rng.shuffle(nodes)
rand_part = [set(nodes[:17]), set(nodes[17:])]
print("ランダム2分割の Q =", round(modularity(G, rand_part), 4))

# 貪欲にQを最大化
greedy = greedy_modularity_communities(G)
print("貪欲最大化 コミュニティ数:", len(greedy), " Q =", round(modularity(G, greedy), 4))

実行結果：

実派閥分割の Q = 0.3914
ランダム2分割の Q = -0.0965
貪欲最大化 コミュニティ数: 3  Q = 0.411

実際の派閥分割は $Q=0.39$ （有意な構造）。でたらめな分割は $Q<0$ （ランダム期待より内部エッジが少ない＝コミュニティになっていない）。貪欲最大化は3コミュニティに分け $Q=0.41$ とさらに高い — 最大化は必ずしも「真の」2派閥を返さない点に注目してください。

数式の直観的意味

$A_{ij} - k_i k_j/(2m)$ は「実際の親密さ − たまたまの親密さ」です。次数の高いノードどうしは偶然でも繋がりやすい（ $k_i k_j$ が大きい）ので、その分を割り引く。割り引いてもなお内部エッジが多ければ、それは偶然でなく「集団としてまとまっている」証拠。 $Q$ の最大化とは、この「偶然を超えた密さ」が最大になる分割を探すことです。

⚠️ よくある誤解・落とし穴

モジュラリティ最大化は NP困難：厳密解は無理。実用はヒューリスティクス（Louvain法・Leiden法）。
解像度限界（resolution limit）： $Q$ は大きなネットワークで小さなコミュニティを大きな塊に併合してしまう。解像度パラメータ $\gamma$ で調整します。
$Q$ が高い分割が複数ありうる： $Q$ 地形は平坦な高原を持ち、ほぼ同じ $Q$ で構造が違う分割が並存する（退化）。

対応シミュレーション

本文のコードがそのまま検証用です。最大化アルゴリズムは Louvain法・Leiden法、ヌルモデルは configurationモデル・次数保存ヌルモデル。