数学推导与算法

本节把模块度、Louvain 与 Leiden 算法、谱方法、随机块模型、映射方程、可检测性和团渗流中只陈述的结果完整推一遍。记号：$A$ 为无向无权网络的邻接矩阵（加权网络把 $A_{ij}$ 换成边权、$k_i$ 换成强度即可），$k_i=\sum_j A_{ij}$ 为节点 $i$ 的度，$m=\frac12\sum_i k_i$ 为边数，$n$ 为节点数。

A. 从模块度到谱二分（Newman 2006）

第 1 步：把 $\delta$ 函数写成 $\pm1$ 变量。 二分时令 $s_i\in\{+1,-1\}$ 表示节点 $i$ 在哪一侧。两点同侧时 $s_is_j=1$，异侧时 $s_is_j=-1$，所以 $$\delta(c_i,c_j)=\tfrac12(1+s_is_j).$$

第 2 步：代入模块度。 记模块度矩阵 $B_{ij}=A_{ij}-\dfrac{k_ik_j}{2m}$，则 $$Q=\frac{1}{2m}\sum_{ij}B_{ij}\cdot\frac{1+s_is_j}{2} =\frac{1}{4m}\sum_{ij}B_{ij}+\frac{1}{4m}\sum_{ij}B_{ij}s_is_j .$$ $B$ 的每一行之和为零：$\sum_j B_{ij}=k_i-\dfrac{k_i\cdot 2m}{2m}=0$。所以第一项消失，得到 $Q=\dfrac{1}{4m}\mathbf s^\top B\mathbf s$。这一步是精确的。

第 3 步：特征分解。 $B$ 是实对称矩阵，有正交归一的特征向量 $\mathbf u_1,\dots,\mathbf u_n$，对应特征值 $\beta_1\ge\beta_2\ge\cdots\ge\beta_n$。把 $\mathbf s$ 展开为 $\mathbf s=\sum_l a_l\mathbf u_l$，$a_l=\mathbf u_l^\top\mathbf s$，则 $$Q=\frac{1}{4m}\sum_{l=1}^{n}a_l^2\,\beta_l,\qquad \sum_l a_l^2=\mathbf s^\top\mathbf s=n .$$

第 4 步：放松与取整（近似在这里进入）。 若 $\mathbf s$ 可以是任意实向量（只保留 $\mathbf s^\top\mathbf s=n$），把全部“权重”$n$ 放到最大特征值上即可使 $Q$ 最大，即 $\mathbf s\propto\mathbf u_1$。但 $s_i$ 只能取 $\pm1$，退而求其次：让 $a_1=\mathbf u_1^\top\mathbf s=\sum_i u_{1i}s_i$ 尽量大，显然取 $s_i=\operatorname{sign}(u_{1i})$。这是启发式，不保证全局最优；Newman 建议之后再做一轮“逐个翻转节点、保留使 $Q$ 增加的翻转”的局部微调。

第 5 步：何时停止。 因为 $B\mathbf 1=\mathbf 0$，全 1 向量总是特征值为 0 的特征向量。若 $\beta_1\le 0$（没有正特征值），任何二分都不能让 $Q$ 超过“不分”的 0，网络被判为不可再分。

第 6 步：递归细分。 对已有社团 $g$ 再二分时，$Q$ 的增量为 $\Delta Q=\frac{1}{4m}\mathbf s^\top B^{(g)}\mathbf s$，其中 $$B^{(g)}_{ij}=B_{ij}-\delta_{ij}\sum_{l\in g}B_{il},\qquad i,j\in g ,$$ 对角修正项保证 $B^{(g)}$ 的行和也为零。用 $B^{(g)}$ 的主特征向量重复第 4、5 步，直到所有社团都不可再分。

算法 1  模块度谱二分（递归版）
输入：网络 G；输出：社团划分 P
1. P ← {V}；待处理队列 S ← {V}
2. while S 非空:
3.     取出 g；构造 B^(g)（不显式存储，见下）
4.     用 Lanczos/幂迭代求 B^(g) 的最大特征值 β1 与特征向量 u1
5.     if β1 ≤ 0（数值容差内）: g 不可再分，continue
6.     s_i ← sign(u1_i)；可选：逐点翻转微调 s
7.     ΔQ ← sᵀ B^(g) s / (4m)
8.     if ΔQ ≤ 0: continue
9.     按 s 把 g 分成 g+、g−，在 P 中替换 g；把 g+、g− 加入 S
10. return P

复杂度：$B$ 是稠密矩阵，但不必存储。$B\mathbf x=A\mathbf x-\mathbf k\,(\mathbf k^\top\mathbf x)/2m$，一次乘法只需 $O(m+n)$。每次二分需要若干次乘法（次数取决于特征值间隙）；Newman（2006）估计稀疏网络上整个递归过程约为 $O(n^2\log n)$。

B. Louvain 局部移动的 $\Delta Q$

用按社团求和的形式 $Q=\sum_c\left[\frac{l_c}{m}-\left(\frac{d_c}{2m}\right)^2\right]$（$l_c$：社团内部边数；$d_c$：社团度之和）。设节点 $i$ 当前独自成一个社团（贡献 $-(k_i/2m)^2$），记 $k_{i,C}$ 为 $i$ 连向社团 $C$ 的边数。把 $i$ 并入 $C$ 后，$l_C\to l_C+k_{i,C}$，$d_C\to d_C+k_i$，$i$ 自身的那一项消失： $$\Delta Q_{i\to C}=\frac{k_{i,C}}{m}-\frac{(d_C+k_i)^2-d_C^2-k_i^2}{4m^2} =\frac{k_{i,C}}{m}-\frac{k_i\,d_C}{2m^2}.$$ 一般情形：节点 $i$ 从社团 $D$ 移到 $C$，可看作“先移出成为孤点、再并入”，记 $D'=D\setminus\{i\}$， $$\Delta Q_{D\to C}=\frac{k_{i,C}-k_{i,D'}}{m}-\frac{k_i\,(d_C-d_{D'})}{2m^2}.$$ 含义：第一项是“连向 $C$ 比连向原社团多出的边”，第二项是零模型下的期望惩罚。带分辨率参数 $\gamma$ 时第二项乘以 $\gamma$。这个公式只需要 $i$ 的邻居信息和每个社团的 $d_c$，所以一次扫描全部节点的代价为 $O(m)$。（聚合后的超节点带自环，自环随节点一起移动，公式形式不变。）

算法 2  Louvain（一轮"局部移动 + 聚合"）
1. 每个节点自成社团；记录每个社团的 d_c
2. repeat
3.     improved ← false
4.     for 节点 i（随机顺序）:
5.         统计 i 连向各邻居社团的边数 k_{i,C}
6.         对每个邻居社团 C 计算 ΔQ_{D→C}；取最大者 C*
7.         if ΔQ_{D→C*} > 0: 移动 i，更新 d_D、d_{C*}；improved ← true
8. until not improved
9. 每个社团压缩为超节点，社团间边权相加，社团内边变为自环
10. 若第 9 步后社团数未减少则停止，否则在新网络上回到第 1 步

复杂度：每次扫描 $O(m)$；扫描次数和层数没有严格的理论上界，经验上整体接近线性。第 7 步只接受严格增益，保证 $Q$ 单调上升、算法终止；但只能到达局部最优，结果依赖访问顺序。

推广到任意质量矩阵：若质量函数可写成 $\sum_{ij}M_{ij}\delta(g_i,g_j)$（$M$ 对称，如多层模块度的超模块度矩阵），则把节点 $i$ 从 $D$ 移到 $C$ 的增量为 $2\left(\sum_{j\in C}M_{ij}-\sum_{j\in D'}M_{ij}\right)$，聚合时 $M\to Z^\top MZ$（$Z$ 为节点–社团指示矩阵）。这就是 GenLouvain 一类实现的核心，代码示例的多层模块度即用此法。

C. Leiden 算法的流程

算法 3  Leiden（一层）
输入：网络 G，初始划分 P；输出：新划分
1. 快速局部移动：队列 Q ← 全部节点（随机顺序）
2.     while Q 非空: 取出 v，移到增益最大的社团（含空社团）；
3.         若 v 移动了，把 v 的不在 Q 中、且不属于 v 新社团的邻居加入 Q
4. 细化：对 P 中每个社团 C，令 P_ref 在 C 内从单点开始；
5.     对 C 中仍为单点、且与 C 其余部分连接足够好的节点 v（随机顺序）：
6.         在 C 内与 v 相连、且自身与 C 连接足够好的子社团中，
7.         以概率 ∝ exp(ΔH/θ)（只考虑 ΔH ≥ 0）选择一个并入
8. 聚合：以 P_ref 的子社团为超节点建聚合网络；初始划分取 P（每个超节点归入其母社团）
9. 若 P 中每个社团都只含一个 P_ref 子社团（不再变化），停止；否则在聚合网络上回到第 1 步

“连接足够好”的判据与质量函数有关：以 CPM 为例，要求子集 $S$ 与 $C\setminus S$ 之间的边数不少于 $\gamma\,\|S\|\cdot(\|C\|-\|S\|)$。第 7 步的随机性让细化可以探索更多可能的子社团；$\theta\to0$ 时退化为贪心选择。

D. 分辨率极限的推导要点

把局部移动的方法用于“合并两个社团 1、2”：设它们之间有 $l_{12}$ 条边，度之和为 $d_1,d_2$，则 $$\Delta Q_{\text{merge}}=\frac{l_{12}}{m}-\frac{d_1d_2}{2m^2}.$$ 只要 $l_{12}\ge1$ 且 $d_1d_2<2m\,l_{12}$，合并就会提高 $Q$。取 $l_{12}=1$、$d_1=d_2=d$：当 $d<\sqrt{2m}$ 时，模块度最大化倾向于把两个哪怕内部完全连通的小团合并。

经典例子（Fortunato 与 Barthélemy 2007）：$n_c$ 个 $K_k$ 完全子图连成环，相邻两团之间只有 1 条边。每团 $d=k(k-1)+2$，$m=n_c\left[\frac{k(k-1)}{2}+1\right]$。代入 $d^2<2m$ 得：当 $n_c>k(k-1)+2$ 时，把相邻两团合并的 $Q$ 更高。例如 $k=5$ 时，只要环上超过 22 个团，最大模块度划分就不再把每个团单独作为社团。代码示例中，10 个 $K_5$ 时“每团一社团”的 $Q=0.809$ 高于两两合并的 0.755；30 个 $K_5$ 时则反过来（0.876 对 0.888）。

CPM 为何没有分辨率极限：对 CPM，合并社团 1、2 的增量为 $\Delta H=l_{12}-\gamma n_1n_2$，只依赖两个社团自身，与网络其余部分无关。两个 $K_5$ 之间 $l_{12}=1$、$n_1n_2=25$，只要 $\gamma>1/25$ 就不会合并，与团数无关。

E. 划分数目的估计

等大二分数用 Stirling 公式 $N!\approx\sqrt{2\pi N}(N/e)^N$： $$\binom{N}{N/2}=\frac{N!}{[(N/2)!]^2}\approx\frac{\sqrt{2\pi N}\,(N/e)^N}{\pi N\,(N/2e)^N}=\frac{2^N\sqrt{2}}{\sqrt{\pi N}}=\frac{2^{N+1}}{\sqrt{2\pi N}}.$$ Bell 数的递推来自“考察包含节点 $N+1$ 的那个组”：若该组另含 $N-j$ 个其他节点（$\binom{N}{N-j}=\binom Nj$ 种选法），其余 $j$ 个节点任意划分（$B_j$ 种），故 $B_{N+1}=\sum_j\binom NjB_j$。$B_N$ 的增长快于任何 $c^N$：粗略地，$\ln B_N\sim N\ln N$。

F. SBM 与 DC-SBM 的轮廓似然（Karrer 与 Newman 2011）

DC-SBM：$A_{ij}\sim\text{Poisson}(\theta_i\theta_j\omega_{b_ib_j})$（$i<j$；自环另计，此处略），对数似然（略去与参数无关的项） $$\ln P(A\mid\theta,\omega,\mathbf b)=\sum_i k_i\ln\theta_i+\frac12\sum_{rs}\left(m_{rs}\ln\omega_{rs}-\omega_{rs}\sum_{i\in r}\theta_i\sum_{j\in s}\theta_j\right),$$ $m_{rs}=\sum_{ij}A_{ij}\delta_{b_i,r}\delta_{b_j,s}$（$r=s$ 时为组内边数的 2 倍）。$\theta$ 有尺度不确定性，加约束 $\sum_{i\in r}\theta_i=1$（对每个组）。在此约束下对 $\theta_i$ 求极大得 $\hat\theta_i=k_i/\kappa_r$（$\kappa_r=\sum_{i\in r}k_i$），对 $\omega_{rs}$ 求极大得 $\hat\omega_{rs}=m_{rs}$。代回并去掉常数，得到只依赖划分的轮廓对数似然 $$\mathcal L_{\text{DC}}(\mathbf b)=\sum_{rs}m_{rs}\ln\frac{m_{rs}}{\kappa_r\kappa_s}.$$ 标准 SBM 相当于所有 $\theta_i$ 相同，同理得到 $\mathcal L_{\text{SBM}}=\sum_{rs}m_{rs}\ln\frac{m_{rs}}{n_rn_s}$。

二者的差别一目了然：DC-SBM 用组的度之和 $\kappa_r$ 做归一化，标准 SBM 用组的节点数 $n_r$。前者把“度高”归因于节点参数 $\theta_i$，后者只能把度的差异归因于分组，因此在度异质的网络中会按度分组。

与模块度的对应（Newman 2016 的要点）：若限定 $\omega_{rr}=\omega_{\text{in}}$、$\omega_{rs}=\omega_{\text{out}}$（$r\ne s$），并取 $\theta_i=k_i$（期望度等于观测度），对数似然中依赖划分的部分为 $$\frac12\sum_{ij}\left[A_{ij}\ln\frac{\omega_{\text{in}}}{\omega_{\text{out}}}-\frac{k_ik_j}{2m}\cdot 2m(\omega_{\text{in}}-\omega_{\text{out}})\right]\delta(b_i,b_j) \;\propto\;\sum_{ij}\left[A_{ij}-\gamma\frac{k_ik_j}{2m}\right]\delta(b_i,b_j),$$ 其中 $\gamma=\dfrac{\omega_{\text{in}}-\omega_{\text{out}}}{\ln\omega_{\text{in}}-\ln\omega_{\text{out}}}$（$\omega$ 已按 $2m$ 归一化）。也就是说，最大化 $Q_\gamma$ 就是在这个受限模型下做最大似然；交替地“固定划分估计 $\omega_{\text{in}},\omega_{\text{out}}$、再更新 $\gamma$ 与划分”，就得到一个由数据决定 $\gamma$ 的迭代方案。

算法 4  DC-SBM 的贪心最大似然（固定组数 B，多次随机重启）
1. for restart = 1..R:
2.     随机初始化 b
3.     repeat
4.         for 节点 i（随机顺序）: 把 i 移到使 L_DC 最大的组（只增益时移动）
5.     until 无移动
6.     记录 L_DC(b)
7. 返回 L_DC 最大的 b

Karrer 与 Newman 使用类似 Kernighan–Lin 的启发式（允许暂时降低似然的强制移动）以跳出局部最优；贝叶斯版本则用 MCMC 在划分空间中抽样。

G. 映射方程的展开

对两层编码，索引码本中各模块码字的使用频率正比于进入概率 $q_i$，模块 $i$ 的码本中各码字（模块内节点与退出码）的使用频率正比于 $p_\alpha$（$\alpha\in i$）与 $q_i$。由 Shannon 信源编码定理， $$H(\mathcal Q)=-\sum_i\frac{q_i}{q}\log_2\frac{q_i}{q},\qquad H(\mathcal P_i)=-\frac{q_i}{p_i}\log_2\frac{q_i}{p_i}-\sum_{\alpha\in i}\frac{p_\alpha}{p_i}\log_2\frac{p_\alpha}{p_i},$$ 其中 $q=\sum_iq_i$，$p_i=q_i+\sum_{\alpha\in i}p_\alpha$。代入 $L=qH(\mathcal Q)+\sum_ip_iH(\mathcal P_i)$ 并记 $\eta(x)=x\log_2x$，整理得 $$L(M)=\eta(q)-2\sum_i\eta(q_i)-\sum_\alpha\eta(p_\alpha)+\sum_i\eta(p_i).$$ 第三项与划分无关（节点访问分布的熵），只有含 $q_i$ 与 $p_i$ 的三项随划分变化，而它们都只依赖于每个模块的退出流和总访问量，因此移动一个节点后的 $\Delta L$ 可以像 $\Delta Q$ 一样局部计算。单一模块时 $q_i=0$，$L=-\sum_\alpha\eta(p_\alpha)$，即节点访问分布的熵。

对无向网络，$p_\alpha=k_\alpha/2m$；模块 $i$ 的退出概率 $q_i$ 等于随机游走者某一步从 $i$ 内部走到外部的概率，即 $\sum_{\alpha\in i}p_\alpha\cdot\frac{k_\alpha^{\text{ext}}}{k_\alpha}=\frac{1}{2m}\sum_{\alpha\in i}k_\alpha^{\text{ext}}$。有向网络需先用带传送的随机游走（传送概率常取 0.15）求稳态分布。

H. 可检测性阈值的直观推导

以 $q=2$ 为例给出一个启发式论证（严格结果见 Decelle 等 2011）。设每个节点有 $c$ 个邻居（稀疏极限下邻域是树状的）。把节点的组标签 $\sigma_i=\pm1$ 看作沿树传播的“信号”：沿一条边走一步，标签保持不变的概率为 $c_{\text{in}}/(c_{\text{in}}+c_{\text{out}})$，因此相关性每步乘以 $$\lambda=\frac{c_{\text{in}}-c_{\text{out}}}{c_{\text{in}}+c_{\text{out}}}=\frac{c_{\text{in}}-c_{\text{out}}}{2c}.$$ 距离根节点 $d$ 步处约有 $c^d$ 个节点，每个携带的关于根标签的相关性为 $\lambda^d$。把它们“投票”汇总，信号量级为 $c^d\lambda^d$，而随机涨落的量级为 $\sqrt{c^d}$。信号压过噪声的条件是 $c^d\lambda^d\gg c^{d/2}$，即 $$c\lambda^2>1\iff |c_{\text{in}}-c_{\text{out}}|>2\sqrt c ,$$ 与 $q=2$ 时的阈值一致（一般 $q$ 时 $\lambda=\frac{c_{\text{in}}-c_{\text{out}}}{qc}$，得 $|c_{\text{in}}-c_{\text{out}}|>q\sqrt c$）。这一条件也正是非回溯矩阵中携带社团信息的特征值 $\frac{c_{\text{in}}-c_{\text{out}}}{q}$ 从噪声谱的半径 $\sqrt c$ 中分离出来的条件，所以非回溯谱方法恰好在阈值处开始有效。

I. 团渗流阈值

在 ER 网络 $G(N,p)$ 中滚动一个 $k$-团模板：每次保留 $k-1$ 个节点、把第 $k$ 个节点换到别处。可选择留下的 $k-1$ 个节点中哪一个作为下次移动的“支点”，约有 $k-1$ 种；新节点约有 $N-k-1\approx N$ 个候选位置；新节点必须与留下的 $k-1$ 个节点全部相连，概率为 $p^{k-1}$。渗流阈值处，每次滚动产生的“下一个相邻 $k$-团”的期望数应恰好为 1（类似分支过程的临界条件）： $$(k-1)\,N\,p_c^{\,k-1}=1\quad\Longrightarrow\quad p_c(k)=\frac{1}{[(k-1)N]^{1/(k-1)}} .$$ 期望小于 1 时，滚动很快停止，$k$-团社团的规模呈指数衰减；大于 1 时，出现横跨网络的巨大 $k$-团社团。

J. 划分比较指标的性质

• NMI 的上界与偏差：$I(X;Y)\le\min\{H(X),H(Y)\}$，故 NMI $\le1$。当 $Y$ 的组数很多时，即使 $Y$ 随机，有限样本下的互信息估计也偏正（每组节点很少，列联表稀疏），这是随机多组划分 NMI 虚高的来源；调整互信息（AMI）减去了随机划分下互信息的期望。
• ARI 的机会校正：在两个划分的组大小（边际）固定、节点标签随机排列的超几何模型下，$\sum\binom{n_{xy}}2$ 的期望为 $\left[\sum\binom{n_x}2\sum\binom{n_y}2\right]/\binom n2$，ARI 正是减去这一期望后的归一化值，因此随机划分的 ARI 期望为 0。
• VI 是度量：$\text{VI}(X,Y)=H(X\mid Y)+H(Y\mid X)$，满足非负性、对称性与三角不等式，上界为 $\log_2 n$。