莱顿社区检测算法简介

发表于 2026/07/29

作者 handsomestwei

26 分钟阅读

莱顿社区检测算法简介

Leiden 算法（莱顿算法）是 Louvain 社区发现方法的改进版，由 Traag 等人提出（论文 From Louvain to Leiden: guaranteeing well-connected communities）。它在优化模块度的同时，保证每个社区内部连通，并通常比 Louvain 更快、划分质量更好。本文介绍其背景、相对 Louvain 的改进、三阶段流程、leidenalg 用法与选型建议。

参考与延伸阅读：

论文：https://arxiv.org/abs/1810.08473
leidenalg GitHub：https://github.com/vtraag/leidenalg
Python 封装：https://github.com/vtraag/leidenalg-python
官方文档：https://leidenalg.readthedocs.io/en/stable/intro.html

1. 社区发现与 Leiden 定位

社区发现（Community Detection） 在图/网络中识别「内部连接紧密、彼此连接相对稀疏」的节点群组。许多现实问题都可建模为网络：

场景	网络建模	社区含义
风控 / 反欺诈	用户—设备—IP—商户关联图	疑似团伙、黑灰产集群
社交媒体	关注 / 互动关系	兴趣圈、朋友圈
生物信息	蛋白质相互作用网络	功能模块
信息检索	文档共引 / 共现网络	主题簇

常见社区发现方法包括 Louvain、LPA（标签传播）、Infomap、极大连通子图等。Leiden（2019 年发表，目前仍是社区检测领域的常用 SOTA 之一）可视为 Louvain 的直接升级版：同样基于模块度优化与层次聚合，但修复了 Louvain 可能产出不连通社区的缺陷，并在实验中往往更快、划分更优。

主流 Python 实现为 Vincent Traag 的 leidenalg 包（底层 C 核心 + Cython，基于 igraph），支持大规模图与多核并行。

2. 相对 Louvain 的改进

2.1 Louvain 的主要缺陷

Louvain 通过贪心最大化模块度（Modularity）做社区划分，流行但有一个长期被忽视的问题：可能产生连通性很差的社区，甚至不连通（disconnected）社区。

论文实验观察到：迭代运行 Louvain 时，最多约 25% 的社区「连接严重不良」，最多约 16% 的社区完全断开。典型失效情形：

某社区含节点 0–6：节点 1–6 仅在本社区内有强连接，
节点 0 同时与「网络其余部分」有大量外部连接。
当 Louvain 将节点 0 单独移到外部社区后，
节点 1–6 虽仍各自「局部最优」，但作为一个社区已不连通。
直观上应拆成 {1–3} 与 {4–6} 两个社区，但 Louvain 只做单点移动，
且聚合为超节点后无法再拆分，断开社区可能被固化。

2.2 Leiden 的两点核心改进

维度	Louvain	Leiden
社区连通性	不保证；可能出现断开社区	保证每个社区连通
节点移动效率	本社区内每个顶点都尝试对所有其他社区算 ΔQ	仅对不稳定点及其直接相邻社区计算（队列式局部移动）
划分细化	主要「合并」社区	增加 Refine（精炼）步骤，可拆分社区内部不良连接
收敛性质	无连通保证	迭代收敛到「所有社区子集局部最优分配」的分区
速度	较快	论文与实践中往往更快

Leiden 的关键差异：不仅能合并社区，还能在 Refine 阶段拆分集群，从而避免「表面模块度高、内部却断开」的划分。

3. 算法原理：三阶段流程

Leiden 沿用 Louvain 的 Expand-and-Reduce 思想，每轮迭代包含三个阶段：

初始：每个节点单独成社区
    ↓
(1) 局部移动（Local moving）
    将节点移到 ΔQ 最大的邻接社区；用队列只回访「邻居社区发生变化」的节点
    ↓
(2) 社区精炼（Refine）  ← Leiden 相对 Louvain 的新增关键步骤
    在每个社区内部重新细分，保证子社区连通；允许带随机性的合并（参数 θ）
    ↓
(3) 社区压缩（Aggregation）
    将同一社区压缩为超节点，在聚合图上继续迭代，直至模块度不再提升

3.1 局部移动（Local moving）

与 Louvain「反复遍历全图直到无点可动」不同，Leiden 使用 FIFO 队列：

初始化：随机顺序将所有节点入队
出队一个节点，尝试迁入 ΔQ > 0 的最优邻接社区；否则留在原社区
若发生移动，将所有不属于新社区且不在队中的邻居入队
队列为空时结束本阶段

这样只跟踪「受影响」的节点，减少无效的模块度计算。

3.2 社区精炼（Refine）

Refine 在阶段 (1) 的划分 P 上得到 P_refined：

先把 P 中每个节点视为独立社区，再在每个原社区内部做优化
目标：消除社区内部的不良连接，必要时将一个社区拆成多个连通子社区
合并目标社区时引入随机性：增益越大被选中概率越高，随机程度由 θ > 0 控制，便于探索分区空间
Refine 后，原社区在聚合图中可能对应多个子节点，但初始聚合划分仍沿用阶段 (1) 的标签

直观理解：Louvain 只有「并」；Leiden 多了「拆」，从而保证连通性与更高的划分质量。

3.3 社区压缩（Aggregation）

将 Refine 后的子社区压缩为超节点，在聚合网络上重复三阶段，直到质量函数无法继续提升。

leidenalg.find_partition() 内部已包含上述多层迭代，一般无需手动循环调用；通过 n_iterations 控制轮数（默认 2；设为 -1 表示直到无法改进为止）。

4. 质量函数与分辨率参数

Leiden 算法框架（局部移动 → Refine → 压缩）与质量函数是解耦的：同一套三阶段流程，可换成不同的「什么叫好社区」的评分标准。leidenalg 用 partition_type 指定质量函数。

4.1 模块度（Modularity）

模块度（Newman–Girvan）衡量：社区内部边数，相对「按节点度数随机连边」的零模型（configuration null model）多出多少。

\[Q = \frac{1}{2m}\sum_{ij}\left(A_{ij} - \frac{k_i k_j}{2m}\right)\delta(\sigma_i, \sigma_j)\]

$A_{ij}$：邻接矩阵；$k_i$：节点度数；$m$：总边数
$\delta(\sigma_i,\sigma_j)=1$ 当且仅当 $i,j$ 同社区

直觉：若同社区边比「按度数随机连」还多，则 $Q$ 高。ModularityVertexPartition 优化的就是这一目标。缺点是存在分辨率极限（resolution limit）：在大图中，两个很小但内部极密的团，可能被错误合并成一个社区。

4.1.1 CPM：Constant Potts Model

CPM 全称 Constant Potts Model（常译常数 Potts 模型 / 恒定 Potts 模型）：

英文词	含义
Constant	惩罚项用常数分辨率 $\gamma$，不依赖图规模 $m$ 或度数积 $k_i k_j$（对比模块度的 $\frac{k_i k_j}{2m}$）
Potts Model	统计物理中的 Potts 模型：每个节点一个离散「自旋态」（社区标签），同态节点之间有相互作用能量；社区发现把「最小化能量 / 最大化质量」映射为找社区划分

CPM 的质量函数（官方 CPMVertexPartition）：

\[Q = \sum_{ij}\bigl(A_{ij} - \gamma\bigr)\delta(\sigma_i, \sigma_j) = \sum_c \Bigl[m_c - \gamma\binom{n_c}{2}\Bigr]\]

$\gamma$ 的物理含义（密度阈值）：

条件	含义
社区内密度 $p_c = m_c / \binom{n_c}{2} \geq \gamma$	社区内部够「密」
社区间密度 $p_{cd} \leq \gamma$	社区之间够「疏」

因此选某个 $\gamma$，等价于声明：「我只认密度不低于 $\gamma$ 的团为社区」。这一定义不依赖全图规模，故 CPM 不受分辨率极限困扰（见 Traag et al., Narrow scope for resolution-limit-free community detection, PRE 2011）。

对比项	模块度	CPM
零模型 / 惩罚	$\frac{k_i k_j}{2m}$（随度数、图规模变）	常数 $\gamma$
分辨率极限	有（大图易吞掉小团）	无
$\gamma$ 含义	RB 系列里调粗细；纯 Modularity 类无独立 γ	社区密度阈值（无向无权图上通常在 $(0,1]$）
边权	仅正权	正权与负权均可
典型场景	默认起步、与经典文献对齐	需控社区密度、多层图、带负边（如「不喜欢」关系）

小例子（直觉）：3 个完全图 $K_5$（每团 5 点、内部密度 = 1），团之间仅各连 1 条弱边。

用 模块度：若全图很大，三个小团可能被当成「太小」而并成一大社区（分辨率极限）。
用 CPM，γ = 0.5：内部密度 1 ≥ 0.5，团间密度很低 ≤ 0.5 → 稳定拆成 3 个社区。
用 CPM，γ = 0.05：阈值很低，弱边也可能被接受，可能并成更少、更大的社区。

4.2 分辨率参数 γ（resolution）

resolution_parameter（γ）在不同划分类型下含义不完全相同：

划分类型	γ 含义	调大 γ 的效果
CPM	社区密度阈值	要求更密 → 社区更小、更多
RBConfiguration / RBER	线性分辨率（与 Potts 惩罚强度相关）	同样倾向更细的划分
Modularity / Surprise / Significance	无独立 γ（或隐含在公式中）	—

经验口诀（CPM / RB 系列）：γ 越大 → 社区越碎；γ 越小 → 社区越大。业务上按「希望团伙最小内部密度 / 期望社区规模」做网格搜索。

4.3 常用划分类型（`partition_type`）

下列类型均来自 leidenalg 官方 API。先总览，再逐类说明与数据例子。

类型	英文全称 / 含义	核心判据	有 γ？	适用边权
`ModularityVertexPartition`	Modularity	相对「度数配置模型」的超额内部边	否	仅正权
`RBConfigurationVertexPartition`	Reichardt–Bornholdt + Configuration null	带 γ 的模块度变体（惩罚仍按度数）	是	仅正权
`RBERVertexPartition`	Reichardt–Bornholdt + Erdős–Rényi null	带 γ；惩罚按全图均匀密度 $p$	是	仅正权
`CPMVertexPartition`	Constant Potts Model	内部边 − γ × 可能对数	是	正/负权
`SurpriseVertexPartition`	(Asymptotic) Surprise	内部边比例相对随机期望的「惊讶度」（KL）	否	正权
`SignificanceVertexPartition`	Significance	各社区密度相对全图密度的显著性（KL）	否	仅无权

（1）`ModularityVertexPartition` — 模块度（默认首选）

作用：最大化经典模块度 $Q$；与绝大多数「Louvain/Leiden 文献结果」对齐。
效果倾向：社区规模受全图边数约束；大图上小而密的团容易被吞并。
例子：Zachary 空手道俱乐部（34 节点）。通常得到约 2–4 个社区，对应俱乐部真实分裂的两大阵营及边界节点微调——适合「先看全图自然分组」。

  
partition = la.find_partition(g, la.ModularityVertexPartition)
# Zachary 上常见：4 个社区，quality() ≈ 0.42

（2）`RBConfigurationVertexPartition` — 带分辨率的「度数零模型」

全称：Reichardt and Bornholdt’s Potts model with a configuration null model。
作用：在模块度公式中引入 γ：$A_{ij} - \gamma\frac{k_i k_j}{2m}$。γ = 1 时与标准模块度等价（差一个常数倍）。
与 Modularity 区别：可调粗细，但仍按节点度数做零模型——高度数节点更「贵」、更难被随便塞进小社区。
例子：同一社交图，γ = 0.5 → 社区偏大（粗分兴趣圈）；γ = 2.0 → 社区偏小（细分小圈子）。高度数「大 V」在两种设定下都更难单独成碎社区。

（3）`RBERVertexPartition` — 带分辨率的「均匀随机图零模型」

全称：Reichardt–Bornholdt + Erdős–Rényi null（$p = m / \binom{n}{2}$）。
作用：惩罚项是常数密度 $p$，不区分节点度数：$A_{ij} - \gamma p$。
与 RBConfiguration 区别：ER 零模型假设「谁和谁连边概率一样」；度异质很强的网络（少数枢纽节点）上，可能与真实生成过程不符。度分布较均匀时，与 CPM / RBConfig 差异较小。
例子：近正则网格/随机几何图上，RBER 与 CPM 结果接近；幂律社交图上，RBConfiguration / Modularity 通常更稳妥。

（4）`CPMVertexPartition` — 按密度阈值切社区

作用：按「内部密度 ≥ γ、外部密度 ≤ γ」定义社区；无分辨率极限；支持负边。
例子（风控）：设备—账号二部图转同构图后，希望「至少 30% 的可能边都存在才算团伙」→ 试 resolution_parameter=0.3。
- γ = 0.1：松散关联也会成团 → 社区大、召回高、误伤多。
- γ = 0.5：只有较密子图才成团 → 社区小、精准高。
例子（Zachary）：γ = 0.05 时社区偏少、偏大；γ = 0.5 时切得更碎（官方文档与常见演示一致）。

  
p_loose = la.find_partition(g, la.CPMVertexPartition, resolution_parameter=0.05)
p_tight = la.find_partition(g, la.CPMVertexPartition, resolution_parameter=0.5)

（5）`SurpriseVertexPartition` — 「内部边占比有多令人惊讶」

作用：比较「实际内部边比例 $q$」与「按社区规模随机时期望比例 $\langle q\rangle$」的 KL 散度（Surprise）。没有分辨率参数。
效果倾向：强调划分在统计上「不像随机」，常得到与模块度不同、有时更细的结构。
例子：边很少、社区边界模糊的稀疏引用网络——Surprise 可能比模块度更敢拆出小主题簇；稠密且社区清晰时，与模块度往往接近。

（6）`SignificanceVertexPartition` — 各社区密度是否显著高于全图

作用：对每个社区算密度相对全图密度的 KL 散度并求和。仅适用于无权图。
与 Surprise 区别：Surprise 看「全局内部边比例」；Significance 逐社区看「局部密度是否显著」。
例子：无权合作网络、无权设备共现图；若边已带金额/次数权重，应改用 CPM / Modularity，而不是 Significance。

选型速查（同一张图怎么选）

你的目标	更合适的 `partition_type`
默认、对齐经典论文/报告	`ModularityVertexPartition`
要调社区粗细，且度异质明显	`RBConfigurationVertexPartition`
要按「密度阈值」控团伙松紧 / 有负边	`CPMVertexPartition`
度较均匀、想用 ER 零模型	`RBERVertexPartition`
关心统计显著性、无权图	`SignificanceVertexPartition` 或 `SurpriseVertexPartition`

同一 Zachary 图上的定性对比（示意）：

设定	常见现象
Modularity	~4 社区，贴近已知两大阵营
CPM γ=0.05	社区更少、更大
CPM γ=0.5	社区更多、更碎
Surprise	可能与 Modularity 边界节点归属不同
RBConfiguration γ=2	比 γ=1（≈模块度）更碎

实际社区数随 seed、n_iterations 略有波动；对比实验时应固定 seed。

5. Python 实践（leidenalg）

5.1 安装

pip install python-igraph leidenalg
# 可选：pip install cairocffi  # 部分可视化场景

依赖 igraph（C 库 + python-igraph 绑定）。leidenalg 基于 igraph 图对象，大规模图上性能较好。

5.2 最小示例

  
import igraph as ig
import leidenalg as la

g = ig.Graph.Famous("Zachary")  # 空手道俱乐部网络

partition = la.find_partition(g, la.ModularityVertexPartition)

print(partition)           # 聚类对象
print(partition.membership)  # 每个节点的社区编号
print(partition.quality())   # 模块度等质量分数

5.3 `find_partition` 主要参数

  
la.find_partition(
    graph,                    # ig.Graph
    partition_type,           # 如 la.ModularityVertexPartition
    initial_membership=None,  # 初始社区标签；None 则每节点单独成社区
    weights=None,             # 边权（边属性名或列表）
    n_iterations=2,           # 迭代轮数；-1 表示直到无法改进
    max_comm_size=0,          # 单社区最大节点数；0 表示不限制
    seed=None,                # 随机种子
    **kwargs,                 # 如 resolution_parameter=0.05
)

参数	作用
`n_iterations`	控制 Leiden 外层迭代次数；生产环境可增大或设为 `-1`
`max_comm_size`	限制社区规模，避免超大团伙（如 `max_comm_size=10`）
`resolution_parameter`	CPM 等类型的分辨率 γ
`seed`	固定随机性，保证可复现
`weights`	支持加权图；有向图需结合具体划分类型与图构建方式

5.4 分辨率与社区规模示例

  
# CPM：γ 为密度阈值（越大社区越碎）
p_fine = la.find_partition(g, la.CPMVertexPartition, resolution_parameter=0.5)
p_coarse = la.find_partition(g, la.CPMVertexPartition, resolution_parameter=0.05)

# 限制最大社区 10 个节点
p_cap = la.find_partition(g, la.ModularityVertexPartition, max_comm_size=10)

注意：旧文/部分示例里「γ 越大社区越大」的说法不适用于 CPM；对 CPM / RB 系列，一般是 γ 越大 → 社区越碎（见 §4.2）。

5.5 提取子图与结果整理

  
import pandas as pd

# 节点 → 社区映射
df = pd.DataFrame({
    "node": g.vs["name"] if "name" in g.vs.attributes() else range(g.vcount()),
    "community": partition.membership,
})

# 取第 k 个社区子图
sub_g = partition.subgraph(0)
# 或：sub_g = g.subgraph([i for i, c in enumerate(partition.membership) if c == 0])

5.6 扩展能力

API	用途
`find_partition_multiplex`	多层 / 多路复用图上的联合社区发现
`find_partition_temporal`	时序网络切片上的社区检测
`is_membership_fixed` + `optimise_partition`	增量更新：固定旧节点社区，仅为新节点分配标签

加权、有向网络：通过边权 weights 与合适的 partition_type 支持；有向边需在构图时显式保留方向。

6. 与其他社区发现方法对比

方法	核心思想	优点	局限
Leiden	模块度/CPM + 三阶段（含 Refine）	连通性有保证、速度快、实现成熟	分辨率等参数需调；可能陷入局部最优
Louvain	模块度贪心 + 聚合	简单、快、工业界广泛使用	可能不连通社区；质量与稳定性弱于 Leiden
LPA	标签传播	极快、实现简单	结果不稳定，难控社区数
Infomap	最短编码 / 随机游走	适合流向、层级结构明显的网络	对参数与图构建敏感
极大连通子图	图拓扑连通分量	计算极简	无语义「紧密」约束，易过大

选型建议：

风控团伙、通用关系网络挖掘：优先 Leiden（或至少知晓 Louvain 的连通性风险）
需要极快粗分、可接受不稳定：LPA
强调信息流 / 路径：Infomap
时序多层网络：find_partition_temporal / find_partition_multiplex

7. 小结

要点	结论
Leiden 是什么	Louvain 的改进版社区发现算法，保证社区连通
核心机制	局部移动 + Refine 精炼 + 社区压缩，迭代至质量函数收敛
相对 Louvain	更快、划分更好、避免断开社区
Python 工具	`leidenalg` + `python-igraph`
关键参数	`partition_type`（Modularity / CPM / RBER / Surprise 等）、`resolution_parameter`、`n_iterations`、`max_comm_size`
CPM 是什么	Constant Potts Model：用常数 γ 作密度阈值，无分辨率极限，支持负边
典型应用	风控团伙识别、社交圈、生物网络模块、文档主题聚类

8. 参考与来源

资源	链接
Leiden 论文	https://arxiv.org/abs/1810.08473
leidenalg（C/Python）	https://github.com/vtraag/leidenalg
leidenalg-python	https://github.com/vtraag/leidenalg-python
官方文档	https://leidenalg.readthedocs.io/en/stable/intro.html
划分类型 API（Modularity / CPM / RBER / Surprise 等）	https://leidenalg.readthedocs.io/en/stable/reference.html
CPM 论文（分辨率极限自由）	Traag et al., PRE 2011 — https://doi.org/10.1103/PhysRevE.84.016114
高级用法（固定节点等）	https://leidenalg.readthedocs.io/en/stable/advanced.html
igraph Python	https://python.igraph.org/

AI, ML

AI ML 社区发现 Leiden Louvain 图算法复杂网络

本文由作者按照 CC BY 4.0 进行授权

莱顿社区检测算法简介

莱顿社区检测算法简介

目录

1. 社区发现与 Leiden 定位

2. 相对 Louvain 的改进

2.1 Louvain 的主要缺陷

2.2 Leiden 的两点核心改进

3. 算法原理：三阶段流程

3.1 局部移动（Local moving）

3.2 社区精炼（Refine）

3.3 社区压缩（Aggregation）

4. 质量函数与分辨率参数

4.1 模块度（Modularity）

4.1.1 CPM：Constant Potts Model

4.2 分辨率参数 γ（resolution）

4.3 常用划分类型（`partition_type`）

（1）`ModularityVertexPartition` — 模块度（默认首选）

（2）`RBConfigurationVertexPartition` — 带分辨率的「度数零模型」

（3）`RBERVertexPartition` — 带分辨率的「均匀随机图零模型」

（4）`CPMVertexPartition` — 按密度阈值切社区

（5）`SurpriseVertexPartition` — 「内部边占比有多令人惊讶」

（6）`SignificanceVertexPartition` — 各社区密度是否显著高于全图

选型速查（同一张图怎么选）

5. Python 实践（leidenalg）

5.1 安装

5.2 最小示例

5.3 `find_partition` 主要参数

5.4 分辨率与社区规模示例

5.5 提取子图与结果整理

5.6 扩展能力

6. 与其他社区发现方法对比

7. 小结

8. 参考与来源

热门标签

莱顿社区检测算法简介

目录

1. 社区发现与 Leiden 定位

2. 相对 Louvain 的改进

2.1 Louvain 的主要缺陷

2.2 Leiden 的两点核心改进

3. 算法原理：三阶段流程

3.1 局部移动（Local moving）

3.2 社区精炼（Refine）

3.3 社区压缩（Aggregation）

4. 质量函数与分辨率参数

4.1 模块度（Modularity）

4.1.1 CPM：Constant Potts Model

4.2 分辨率参数 γ（resolution）

4.3 常用划分类型（partition_type）

（1）ModularityVertexPartition — 模块度（默认首选）

（2）RBConfigurationVertexPartition — 带分辨率的「度数零模型」

（3）RBERVertexPartition — 带分辨率的「均匀随机图零模型」

（4）CPMVertexPartition — 按密度阈值切社区

（5）SurpriseVertexPartition — 「内部边占比有多令人惊讶」

（6）SignificanceVertexPartition — 各社区密度是否显著高于全图

选型速查（同一张图怎么选）

5. Python 实践（leidenalg）

5.1 安装

5.2 最小示例

5.3 find_partition 主要参数

5.4 分辨率与社区规模示例

5.5 提取子图与结果整理

5.6 扩展能力

6. 与其他社区发现方法对比

7. 小结

8. 参考与来源

热门标签

4.3 常用划分类型（`partition_type`）

（1）`ModularityVertexPartition` — 模块度（默认首选）

（2）`RBConfigurationVertexPartition` — 带分辨率的「度数零模型」

（3）`RBERVertexPartition` — 带分辨率的「均匀随机图零模型」

（4）`CPMVertexPartition` — 按密度阈值切社区

（5）`SurpriseVertexPartition` — 「内部边占比有多令人惊讶」

（6）`SignificanceVertexPartition` — 各社区密度是否显著高于全图

5.3 `find_partition` 主要参数