社区发现：哪些节点抱团？

上一篇我们学会了给节点排名——谁度数最高、谁最居中、谁的 PageRank 最大。但”重要节点”只是个体属性，还有一个更宏观的问题：网络中有没有自然形成的群组结构？ 社交网络里，人们会按兴趣、地域、职业”抱团”；蛋白质相互作用网络里，功能相关的蛋白质聚成模块；互联网上，主题相近的网页互相链接成簇。这些组内连接紧密、组间连接稀疏的子图就是”社区”（community）。

没有社区发现，你只能看到一团密密麻麻的节点和边——看不出哪些节点属于同一个功能群组，无法做用户分群、无法识别蛋白质功能模块、无法理解大型网络的中观结构。社区发现回答的核心问题是：如何从网络拓扑自动识别出这些自然群组？

算法范式：贪心（Louvain — 每步选 $\Delta Q$ 最大的合并）、消息传递（标签传播 — 每个节点采纳邻居多数标签）

核心思想：“组内密、组间疏”的量化

在进入具体算法之前，先抓住社区发现的核心直觉：

一个好的社区划分，应该让社区内部的边远多于”随机期望”。 如果我们把所有节点随机打乱重新连边（保持每个节点的度不变），社区内部边的比例会是多少？实际社区内部边比这个”随机基线”多出的部分，就是社区结构的”信号强度”。

这个直觉的数学形式化就是模块度（Modularity）——整篇文章最重要的概念。

模块度（Modularity）：社区好坏的标尺

数学定义

模块度 $Q$ 由 Newman & Girvan (2004) 提出，是目前最广泛使用的社区质量度量：

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

逐项拆解：

$A_{ij}$ ：邻接矩阵元素。如果节点 $i$ 和 $j$ 之间有边， $A_{ij} = 1$ ；否则 $A_{ij} = 0$ 。
$k_i = \deg(i)$ ：节点 $i$ 的度（连接的边数）。
$\frac{k_i k_j}{2m}$ ：零模型（null model）——在保持度序列不变的随机图（configuration model）中， $i$ 和 $j$ 之间的期望边数。直觉：度高的节点更可能随机连边。
$\delta(c_i, c_j)$ ：Kronecker delta，当且仅当 $i$ 和 $j$ 被分到同一社区（ $c_i = c_j$ ）时为 1。这个因子让求和只计算同社区内的节点对。
$\frac{1}{2m}$ ：归一化因子， $m = |E|$ 是总边数。使得 $Q \in [-0.5, 1)$ 。
整体含义： $Q$ 衡量的是”同社区内的实际边数 − 随机期望边数”的总和，归一化后的值。

模块度的取值范围与直觉

$Q = 0$ ：社区内部的边数恰好等于随机期望——没有社区结构，和随机图一样。
$Q > 0$ ：社区内部边多于随机期望——存在社区结构。
$Q < 0$ ：社区内部边少于随机期望——节点倾向于连接其他社区（反社区结构）。
实际网络中， $Q \approx 0.3$ – $0.7$ 表示有明显的社区结构（Newman, 2006）。

等价的社区级形式

模块度也可以按社区逐个计算。设社区 $c$ 内部的边数为 $l_c$ ，社区内节点的度之和为 $d_c$ ，则：

$Q = \sum_c \left[\frac{l_c}{m} - \left(\frac{d_c}{2m}\right)^2\right]$

逐项理解：

$\frac{l_c}{m}$ ：社区 $c$ 内部边占总边数的比例（实际值）。
$\left(\frac{d_c}{2m}\right)^2$ ：如果随机布线，社区 $c$ 内部边的期望占比（零模型值）。
差值 > 0 意味着这个社区”比随机更紧密”。

这个形式在 Louvain 算法中尤其有用——它让我们能快速计算”将节点 $i$ 移入社区 $c$ 后 $Q$ 的变化量 $\Delta Q$ “。

模块度增益 $\Delta Q$

当我们将一个孤立节点 $i$ （度为 $k_i$ ）移入社区 $c$ 时，模块度变化为：

$\Delta Q = \frac{1}{2m}\left[k_{i,\text{in}} - \frac{k_i \cdot d_c}{2m}\right]$

其中 $k_{i,\text{in}}$ 是 $i$ 连向社区 $c$ 内部节点的边数， $d_c$ 是社区 $c$ 中所有节点的度之和。

直觉：

$k_{i,\text{in}}$ 大（ $i$ 与 $c$ 连接紧密）→ $\Delta Q$ 大，应该合并。
$d_c$ 大（ $c$ 已经很大）→ $\Delta Q$ 被惩罚，防止社区无限膨胀。

这个公式是 Louvain 算法的核心驱动力——每一步都选择使 $\Delta Q$ 最大的移动。

Louvain 算法：贪心合并 + 层级折叠

Louvain 算法（Blondel et al., 2008）是目前最广泛使用的社区发现算法。它的核心思路极其简洁：贪心地移动节点来最大化模块度，然后把找到的社区折叠成超节点，在超图上重复这个过程。

算法步骤

Phase 1 — 贪心局部移动：

初始化：每个节点自成一个社区（ $n$ 个单节点社区）
对每个节点 $i$ $i$ ，考虑所有邻居所在的社区 $c$ $c$ ：
- 计算将 $i$ 移入社区 $c$ 的 $\Delta Q$
- 选择使 $\Delta Q$ 最大且 > 0 的社区，将 $i$ 移入
反复扫描所有节点，直到没有节点想移动 → Phase 1 稳定

Phase 2 — 层级折叠：

将每个社区缩成一个超节点
社区内部的边变成超节点的自环（权重 = 内部边数 $\times 2$ ）
两个社区之间的边合并为超节点间的加权边（权重 = 跨社区边数）
在这个新的加权超图上，回到步骤 1，重复 Phase 1 + Phase 2

终止条件：当某一轮的 Phase 1 没有产生任何节点移动（ $Q$ 不再增加），算法停止。

复杂度分析

单次 Phase 1 扫描：每个节点检查邻居 → $O(m)$ 总时间
Phase 1 收敛：实验表明通常只需几轮扫描
Phase 2： $O(n + m)$
层级数：通常 $O(\log n)$ 层
实际复杂度： $O(n \log n)$ 左右（经验值，在大多数真实网络上）
理论最坏： $O(n^2)$ （但极少遇到）

Louvain 走查

下面的交互组件展示 Louvain 算法在一个 10 节点无向图上的完整执行过程。注意观察节点如何逐步被”吸入”密集连接的邻居社区。

Louvain 算法走查无向图 · 10 节点 · 3 个自然社区

步骤 1/11: 初始状态：每个节点是自己的社区（10 个社区）。Louvain 将贪心地合并社区来最大化模块度 Q。

1 / 11

走查中的关键观察：

贪心选择：节点总是加入与自己连边最多的社区。例如 D 有 3 条边连向社区 $\{A,B,C\}$ 但只有 1 条连向 E，所以选择前者。
自然涌现：算法没有预设社区数量——3 个社区是从网络拓扑中自然涌现的。
层级折叠：Phase 2 把每个社区缩成超节点后，超图上的边非常稀疏（每个桥变成一条边），继续优化已无收益。

Louvain 的局限与 Leiden 改进

Louvain 算法简单高效，但有一个理论缺陷：它不保证发现的社区是内部连通的。在某些情况下，Louvain 可能把不连通的子图合并为同一社区（因为贪心移动的顺序可能导致中间状态出现断裂，但后续没有修复）。

Leiden 算法（Traag, Waltman & van Eck, 2019）针对这一问题提出改进：

在 Phase 1 中增加”精炼”步骤：每次贪心移动后，检查社区是否保持连通
用”move”和”refine”交替进行，保证每个社区始终是连通子图
收敛更快（因为避免了无效的断裂-修复循环）
输出质量通常 ≥ Louvain

实践建议：如果工具支持 Leiden（如 leidenalg Python 包），优先使用 Leiden。

标签传播（Label Propagation）：最快的社区发现

标签传播算法（Raghavan, Albert & Kumara, 2007）是另一种极其简洁的社区发现方法。它不依赖模块度，核心思想是消息传递：每个节点不断采纳邻居中最常见的标签，密集连接的区域会快速统一标签。

算法步骤

初始化：每个节点 $v$ 的标签 $l(v) = v$ （自己的唯一 ID）
迭代：以随机顺序扫描每个节点。对节点 $v$ $v$ ：
- 统计邻居的标签频率
- 将 $l(v)$ 更新为邻居中出现次数最多的标签（ties 随机打破）
终止：当没有节点的标签需要更新时（所有节点的标签 = 邻居中最频繁的标签），算法收敛
拥有相同标签的节点构成一个社区

复杂度分析

单次迭代： $O(n + m)$ ——每个节点查看邻居的标签
迭代次数：实验表明通常 $O(1)$ 到 $O(\log n)$ 轮
总复杂度：接近 $O(n + m)$ （近线性），是已知最快的社区发现算法之一

优点与缺点

优点：

极快：近线性时间，适合百万甚至十亿级节点的网络
无需参数：不需要预设社区数量
直觉清晰：密集连接区域的标签自然统一

缺点：

不确定性：随机扫描顺序和 tie-breaking 导致每次运行结果可能不同
振荡风险：在二部图等特殊结构上可能无法收敛（标签来回切换）
质量不稳定：没有模块度那样的全局目标函数，可能产生较大或较小的社区

实践中常用多次运行取共识（consensus clustering）来缓解不确定性。

k-core 分解：找致密子图的利器

k-core 分解不是直接的社区发现算法，但它是社区预处理和致密子图定位的重要工具。

定义

图 $G$ 的 $k$ -core 是 $G$ 的一个极大子图 $H$ ，使得 $H$ 中每个节点的度 $\geq k$ 。

1-core = 整个连通分量（只要有 1 条边就行）
2-core = 删掉所有度为 1 的节点（叶子）后剩下的
3-core = 进一步删掉度 < 3 的节点…
$k$ -core 是嵌套的： $(k+1)\text{-core} \subseteq k\text{-core}$

节点 $v$ 的 core number（核数）= 最大的 $k$ 使得 $v$ 属于 $k$ -core。图的 degeneracy（退化度）= 最大核数 = 最大 $k$ 使得 $k$ -core 非空。

算法：反复剥离

K-Core-Decomposition(G):
    for each v ∈ V: core[v] = deg(v)
    // 按度数从小到大处理
    while 还有未处理节点:
        v = 未处理节点中 core[v] 最小的
        for each neighbor u of v (未处理):
            if core[u] > core[v]:
                core[u] -= 1

时间复杂度： $O(n + m)$ 。空间： $O(n)$ 。

社区发现中的角色

k-core 在社区发现流程中有两个用途：

预处理：大型网络中，先做 k-core 分解去掉外围”毛刺”节点（核数低的节点通常不属于任何紧密社区），然后在内核上运行 Louvain/标签传播，速度更快、噪声更少。
致密子图定位：高 core number 的节点聚集的区域往往对应网络中最紧密的社区核心。

k-core 的算法细节和更深入的理论性质（如退化度与着色数的关系、k-core 与图密度的精确联系）将在 Art. 10: 团与密子图中展开。

谱聚类：矩阵视角的社区发现

社区发现还有一条完全不同的路径——谱聚类（Spectral Clustering），它从图 Laplacian 矩阵的特征值和特征向量出发。

核心思想：构建图的 Laplacian 矩阵 $L = D - A$ （ $D$ 是度对角矩阵， $A$ 是邻接矩阵），取最小的几个非零特征值对应的特征向量（即 Fiedler 向量及其推广），将节点映射到低维空间后做 k-means 聚类。

谱聚类有优美的理论保证（与 normalized cut 最优化等价），但计算代价较高（特征分解 $O(n^3)$ 或迭代方法 $O(nk^2)$ ），且需要预指定社区数 $k$ 。

谱聚类的完整数学推导——包括图 Laplacian 的性质、Fiedler 向量的几何意义、normalized cut 与 Rayleigh 商的关系——在图 Laplacian 与谱聚类中详细展开。 本文聚焦组合/算法视角的社区发现方法。

模块度的局限：Resolution Limit

模块度优化是社区发现的主流方法，但它有一个被 Fortunato & Barthélemy (2007) 发现的根本性局限——resolution limit。

问题本质

模块度公式中的零模型 $\frac{k_i k_j}{2m}$ 包含全局总边数 $m$ 。这意味着：模块度有一个内在的分辨率尺度，取决于网络的总大小。

具体而言：两个通过单条桥边相连的小团（clique），如果它们的内部边数小于 $\sqrt{2m}$ ，模块度优化会把它们合并为一个社区——即使直觉上它们明显是两个独立的社区。

当网络越大（ $m$ 越大），这个阈值 $\sqrt{2m}$ 越高，越多小社区会被”看不见”。

缓解方法

分辨率参数 $\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 > 1$ 发现更多小社区， $\gamma < 1$ 发现更少大社区。Louvain 和 Leiden 都支持此参数。
多尺度分析：在不同 $\gamma$ 值下运行，观察哪些社区在多个尺度下都稳定存在。
Leiden 算法：通过更好的精炼步骤，在一定程度上缓解（但不完全消除）resolution limit。
非模块度方法：如 Infomap（基于信息论的随机游走压缩）、Stochastic Block Model（概率生成模型），它们不受 resolution limit 约束。

应用场景

社交网络用户分群

Facebook 和 Twitter 使用社区发现来识别兴趣群组、推荐好友、优化信息流。Blondel 等人在 2008 年原始论文中用 Louvain 分析了一个 200 万节点的比利时电话通信网络，发现的社区与法语/荷兰语的语言边界高度吻合——社区结构揭示了真实世界的文化分界线。

蛋白质功能模块

蛋白质相互作用网络（PPI network）中，社区对应功能模块——执行同一生物功能的蛋白质倾向于密集互连。通过社区发现，生物学家可以预测未知蛋白质的功能（如果它与某个已知功能模块的蛋白质密集连接，很可能参与同一功能）。

欺诈检测

金融交易网络中，异常紧密的小社区可能是欺诈环（fraud ring）——多个关联账户协同进行欺诈交易。PayPal 和 Visa 使用社区发现算法检测此类模式。

复杂度对比表

算法	时间复杂度	空间复杂度	需要参数	结果确定性	适用场景
Louvain	$O(n \log n)$ 实际	$O(n + m)$	无（可选 $\gamma$ ）	近似确定	大规模网络，通用首选
Leiden	$O(n \log n)$ 实际	$O(n + m)$	无（可选 $\gamma$ ）	近似确定	Louvain 的改进版
标签传播	$\approx O(n + m)$	$O(n)$	无	不确定	超大规模网络
谱聚类	$O(n^3)$ 或 $O(nk^2)$	$O(n^2)$ 或 $O(nk)$	社区数 $k$	确定	中小规模，需要理论保证
k-core 分解	$O(n + m)$	$O(n)$	无	确定	预处理，致密子图定位

注：Louvain 和 Leiden 的理论最坏时间复杂度为 $O(n^2)$ ，但在绝大多数真实网络上表现为 $O(n \log n)$ 。

🔁 迭代机器视角 — Label PropagationEQ: 方程 / 不动点

Graph	无向图
State[v]	社区标签 label(v)
SELECT	随机序或同步全集
COMBINE	邻居标签的 majority vote
重入	到不动点（但不保证收敛）
TERMINATE	标签不再变化
求解方法	FI

COMBINE 是 majority vote（非半环操作）——同步版本在二部图上可能振荡，无收敛保证

→ 框架详解：Art. 0A — 图上的通用迭代机器

🔁 迭代机器视角 — Louvain (Modularity Optimization)OPT: 优化目标

Graph	原图 → 粗化超图
State[v]	社区归属
SELECT	随机序遍历节点
COMBINE	计算 modularity 增益 ΔQ → 移动到最优社区
重入	到不动点（每轮内）+ 多层粗化
TERMINATE	ΔQ 无正增益
求解方法	FI

→ 框架详解：Art. 0A — 图上的通用迭代机器

总结

本文围绕”网络中哪些节点抱团”这个核心问题，建立了社区发现的完整框架：

模块度 $Q$ ：衡量”组内边比随机期望多多少”的全局质量指标。理解 $Q$ 的公式和直觉是理解 Louvain 的前提。
Louvain 算法：贪心移动节点最大化 $\Delta Q$ → 折叠成超节点 → 重复。 $O(n \log n)$ 实际复杂度，是大规模网络社区发现的事实标准。
标签传播：每个节点采纳邻居多数标签 → 密集区域快速统一。 $O(n + m)$ ，最快但不稳定。
k-core 分解：层层剥离找致密核心， $O(n + m)$ ，是社区发现的有力预处理工具。
谱聚类：从矩阵特征向量做社区发现，有理论保证但计算代价高——详见图 Laplacian 与谱聚类。
Resolution limit：模块度的内在盲区——小社区可能被合并。可用分辨率参数 $\gamma$ 或 Leiden 缓解。

社区发现解决了”哪些节点抱团”，但还有一个关键问题尚未回答：两个节点/两张图之间有多像？ 下一篇 Art. 9: 相似性与同构将从节点邻域重叠到图同构检测，量化图的相似性。而 k-core 的算法细节和更深入的密子图理论将在 Art. 10: 团与密子图中展开。

实现指引

算法	库	函数/方法
Louvain	python-louvain	`community_louvain.best_partition(G)`
Louvain	NetworkX	`nx.community.louvain_communities(G)`
Leiden	leidenalg	`leidenalg.find_partition(G, leidenalg.ModularityVertexPartition)`
标签传播	NetworkX	`nx.community.label_propagation_communities(G)`
模块度计算	NetworkX	`nx.community.modularity(G, communities)`
k-core 分解	NetworkX	`nx.core_number(G)`, `nx.k_core(G, k)`
谱聚类	scikit-learn	`sklearn.cluster.SpectralClustering(n_clusters=k)`
社区检测	igraph	`g.community_multilevel()` (Louvain), `g.community_label_propagation()`
社区检测	Neo4j GDS	`gds.louvain.stream(G)`, `gds.labelPropagation.stream(G)`
社区检测	scikit-network	`sknetwork.clustering.Louvain()`

核心思想：“组内密、组间疏”的量化

模块度（Modularity）：社区好坏的标尺

数学定义

模块度的取值范围与直觉

等价的社区级形式

模块度增益 ΔQ\Delta QΔQ

Louvain 算法：贪心合并 + 层级折叠

算法步骤

复杂度分析

Louvain 走查

Louvain 的局限与 Leiden 改进

标签传播（Label Propagation）：最快的社区发现

算法步骤

复杂度分析

优点与缺点

k-core 分解：找致密子图的利器

定义

算法：反复剥离

社区发现中的角色

谱聚类：矩阵视角的社区发现

模块度的局限：Resolution Limit

问题本质

缓解方法

应用场景

社交网络用户分群

蛋白质功能模块

推荐系统

欺诈检测

复杂度对比表

总结

实现指引

模块度增益 $\Delta Q$