← ネットワーク科学 一覧

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

📎 前提：モジュラリティ最大化　|　関連：コアペリフェリ構造・assortativity

要点（BLUF）

• Louvain法：各ノードを「最も $Q$ が上がる隣の集団」へ移し、集団を1ノードに集約 — を繰り返す貪欲・階層的アルゴリズム。
• ほぼ線形時間で数百万ノードに届く。コミュニティ検出の事実上の標準。
• Leiden法：Louvain が稀に「内部で非連結なコミュニティ」を作る欠陥を修正し、品質と速度を改善した後継。

概念：局所改善と集約の繰り返し

モジュラリティ $Q$ の厳密最大化は NP困難（モジュラリティ最大化）。そこで「全体最適は諦め、局所的に $Q$ を上げる移動を貪欲に繰り返す」のが Louvain法です。賢いのは、改善が止まったらコミュニティを1つのノードに畳んで（集約）同じ手続きを上の階層で繰り返す点。これで多階層のコミュニティが高速に得られます。

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

フェーズ1（局所移動）：各ノードを順に見て、隣接するコミュニティのうち「移すと $Q$ の増分 $\Delta Q$ が最大になる先」へ移動する。$\Delta Q > 0$ の移動がなくなるまで繰り返す。

フェーズ2（集約）：各コミュニティを1つのスーパーノードに畳み込む。コミュニティ内エッジは自己ループ、コミュニティ間エッジは重み付きエッジになる。この縮約グラフでフェーズ1を再実行。

2フェーズを $Q$ が改善しなくなるまで繰り返します。各階層が異なる粒度のコミュニティに対応します。

graph TD
    S["元のグラフ"] --> P1["フェーズ1<br/>各ノードを最良の隣集団へ移動"]
    P1 --> P2["フェーズ2<br/>コミュニティを1ノードに集約"]
    P2 --> Q{"Qが改善した?"}
    Q -->|"はい"| P1
    Q -->|"いいえ"| E["階層的コミュニティを出力"]

コードで確認

import networkx as nx
from networkx.algorithms.community import louvain_communities, modularity

G = nx.karate_club_graph()
lc = louvain_communities(G, seed=42)
print("Louvain コミュニティ数:", len(lc), " サイズ:", sorted(len(c) for c in lc))
print("Louvain の Q =", round(modularity(G, lc), 4))

実行結果：

Louvain コミュニティ数: 4  サイズ: [4, 6, 10, 14]
Louvain の Q = 0.4266

Louvain は4コミュニティに分け $Q=0.43$。貪欲法（モジュラリティ最大化 の $Q=0.41$）より高く、より細かい粒度を捉えています。乱数シードで結果が変わりうる（貪欲なので局所解依存）点に注意。

Leiden法：Louvainの欠陥を直す

Louvain には「集約の過程で、内部が非連結なコミュニティが生まれることがある」という見落とされがちな欠陥があります。Leiden法は移動と集約の間に**refinement（細分化）**ステップを挟み、各コミュニティが連結であることを保証します。結果として品質が安定し、速度も向上。大規模解析では Leiden が推奨されます（networkx 標準には未収録で、leidenalg 等を使います）。

数式の直観的意味

Louvain の核心は $\Delta Q$ を局所量だけで高速計算できることです。ノード $i$ をコミュニティ $C$ に移したときの $Q$ 変化は、$i$ と $C$ の間のエッジ数と、$C$ の総次数だけで決まり、グラフ全体を見直す必要がありません。だから1回の移動が $O(\deg i)$ で済み、全体がほぼ線形時間になる。「局所的な改善の積み重ねが大域的に良い分割に至る」という、貪欲法が機能する典型例です。

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

• Louvain は局所解に落ちる：シードや訪問順で結果が変わる。複数回実行して最良 $Q$ を採るのが実務です。
• Louvain のコミュニティが非連結になりうる：見落とされやすい欠陥。連結性が重要なら Leiden を使う。
• 解像度限界は継承される：Louvain/Leiden もモジュラリティを最適化する以上、小コミュニティ併合の問題は残ります（モジュラリティ最大化）。

対応シミュレーション

本文のコードがそのまま検証用です。

関連

• 前提：モジュラリティ最大化
• 別種の構造：コアペリフェリ構造・assortativity
• 上位ハブ：コミュニティ構造 目次