第 04 章学习笔记：社区检测

配套译文：内部译文（已落盘并通过逐段对齐审计；9 个 proof-check-4- 锚点已在本文件以别名 span 对齐）。本章是全书的理论核心长章（42 印刷页）：29 个编号语义对象（Definition 3 / Proposition 4 / Lemma 8 / Theorem 3 / Remark 6 / Example 5）、29 个编号公式、13 图 4 表 4 个算法框。前三节（4.1 割方法、4.2 模块度方法、4.3 贝叶斯方法）各给一条方法路线并配实验与局限分析，4.4 节把三条路线在理论层统一并给出渐近保证。核心矛盾只有一条——"社区"没有严格定义，每条方法路线都各自 NP-hard 且各有失效模式，于是本章用"松弛与近似算法"解决计算问题、用"生成模型（SBM）下的理论分析"解决方法选择问题*。

1. 一句话定位

本章回答第 1 章 karate club 留下的预测问题——仅凭相互作用图，能否恢复潜在的社区结构——答案是三条互补的路线：把社区检测写成割/模块度的组合优化问题再做谱松弛或贪心近似（4.1/4.2），把网络当作 SBM 的样本做贝叶斯后验推断（4.3），然后用理论分析证明前两者的合理性（MAP ≈ 模块度最大化、归一化谱聚类 = 模块度的连续松弛）并给出渐近可行性边界（Rényi 散度阈值与谱方法一致性，4.4）；本章方法直接回答 Ch1 前瞻句 F1（karate club 分裂预测）与 F2（模块度过拟合），其理论框架是第 5–6 章推断问题的起点。

2. 本章导读

本章按"三条方法路线 → 一路理论收口"推进，每条方法路线都遵循同一叙事节奏：准则 → NP-hard → 近似算法 → 实验 → 失效模式。

章首（印刷页 66–68）：社区定义的三种途径（节点相似度 / 局部密度 / 全局模块度）——社区"严格说没有良好定义"，这不是客套话，而是全章方法论分歧的根源。Table 4.1 列出带真值社区的基准数据集（karate club、dolphins、political blogs、MNIST 等），是后面所有实验的战场。
4.1 割方法（印刷页 68–79）：把"组内密、组间疏"写成割最小化。图二分（4.1.1）：平衡约束下 min Cut 化为 $\min z^{T}Lz$（Prop 4.1），连续松弛后由 Courant–Fischer 给出第二小特征向量（Lemma 4.1）→ Algorithm 4。一般 $K$ 簇（4.1.2）：RatioCut/NCut 两种平衡化准则写成迹形式（Lemma 4.2），松弛后取前 $K$ 个特征向量 + $k$-means（Prop 4.2）→ Algorithm 5。SDP（4.1.3）是另一条松弛路线。讨论（4.1.4）给出两类失效：悬垂树导致特征向量局部化（图 4.3，正则化 $\mathcal L_\tau$ 可解，Table 4.3），几何结构劫持低阶特征向量（图 4.4–4.6，需看高阶特征向量）。
4.2 模块度方法（印刷页 80–87）：模块度 $\mathcal M(z)$（Definition 4.2，式 (4.17)）把同社区边密度与配置模型零模型比较，是"全局定义"的化身；图 4.7 的玩具图四种划分是理解它最好的入口。最大化 NP-complete，于是有贪心合并（Algorithm 6，复杂度 $O(n(|E|+n))$，Prop 4.3）与 Louvain（Algorithm 7，实践中完胜）；支撑它们的全部计算只是三个增量公式（Lemma 4.3–4.5）。讨论（4.2.4）：Louvain 倾向把真值社区劈成更多小社区，且模块度比真值更高（Table 4.4、图 4.8/4.9）。
4.3 贝叶斯方法（印刷页 87–92）：先直面过拟合——Louvain 在没有任何社区结构的 ER/CM/PA 随机图上也能找到高模块度划分（图 4.10），归一化谱聚类在 ER 图上也能切出占 15%–30% 边数的割（图 4.11）。解药是把网络视为 Poisson 版 DC-SBM 的实现，对标签 $z$ 最大化后验（4.3.2，对 $\omega$、$\theta$ 积分得到边际似然），用 Metropolis–Hastings MCMC 在标签空间采样（4.3.3）。数值结果（4.3.4）：karate club 上后验给出 $K=1$ 或 $2$（图 4.12），无结构随机图上只预测 1 个社区（图 4.13）——过拟合消失。
4.4 理论分析（印刷页 92–106）：全书理论高地，分四步。4.4.1：2 块对称 DC-SBM 下 MAP 估计 = 带分辨率参数 $\gamma$ 的模块度最大化（Prop 4.4），为模块度补上生成模型根据。4.4.2：$K=2$ 时广义模块度最大化的超椭球松弛精确等于归一化谱聚类（取 $\mathcal L$ 第二小特征向量），把 4.1 与 4.2 两条线焊在一起。4.4.3：信息论边界——同/异社区相互作用分布的 Rényi 散度 $I$ 决定一致恢复（$I\gg n^{-1}$）与强一致恢复（$I\ge(1+\Omega(1))K\log n/n$）的可能性（Thm 4.6，原书不证）；二元稀疏 SBM 的强一致阈值 $(\sqrt a-\sqrt b)^2>K$（Example 4.2）。4.4.4：谱方法在 SBM 上的一致性（Thm 4.8，原书完整证明），证明链为"均值场特征结构（Lemma 4.7）→ 浓度（Thm 4.9，不证）→ 主子空间扰动（Lemma 4.10，引用）→ 近似 $k$-means 误差界（Lemma 4.11）"。
Further Notes（印刷页 106–107）：4 段文献指引，无习题。解读见本页 §16。

3. 本页使用方式

按你在正文中最可能卡住的位置直接跳转：

"为什么最小化割最后变成算特征向量？" → 这条链分三步：离散改写（proof-proposition-4-1，Cut $=\frac14 z^{T}Lz$）→ 二簇松弛解（proof-lemma-4-1，Courant–Fischer）→ $K$ 簇松弛解（prop-4-2-positioning，迹最小化 = 前 $K$ 个特征向量）。先读 §9 卡片 T1/T2 再看证明。
Prop 4.1 证明里 $(z_i-z_j)^2$ 的分段值和系数对不上 → 你不是一个人：原书此处的分段值（印为 1）与系数（印为 $\frac12$）同错一个因子 4，正确链条是 $\mathrm{Cut}=\frac18\sum a_{ij}(z_i-z_j)^2=\frac14z^{T}Lz$，见 proof-proposition-4-1 的校勘提示。
Lemma 4.3/4.4/4.5 三个公式长得像、分不清谁服务谁 → §9 卡片 T3：Lemma 4.3 是"按社区重写 $\mathcal M$"，Lemma 4.4 服务贪心合并（Algorithm 6），Lemma 4.5 服务 Louvain 单点移动（Algorithm 7）；展开证明见 proof-lemma-4-3 起三张卡。
Proposition 4.3 在 OCR 里只剩一个孤立公式和 Proof → 这是已实证的高严重度 OCR 异常：命题头与陈述句被吞并，已按文本层补回（"The time complexity of Algorithm 6 is $O(n(|E|+n))$"），见 proof-proposition-4-3 的校勘提示。
Prop 4.4 的对数似然展开看得头晕 → 它只是两步代数：$\omega_{ij}$ 与 $\log\omega_{ij}$ 都写成"示性函数 × 差 + 基线"，再按 $z$ 相关/无关拆项，见 proof-proposition-4-4 的"证明思路"段。
§4.4.2 的超椭球约束在哪？OCR 里 argmax 下面没有约束行 → OCR 丢失约束行 $x^{T}Dx=2|E|$ 且把 $=$ 误作 $\equiv$；完整推导（含被排除的两个平凡解）见 deriv-modularity-spectral-relaxation。
Theorem 4.6 的两个阈值 $n^{-1}$ 与 $K\log n/n$ 哪来的 → 原书不证，本笔记给阈值直觉（每个节点的标签信息量 $\sim nI$，union bound 要求逐点错误率 $\ll 1/n$），见 thm-4-6-positioning。
Theorem 4.8 的证明里哪些部件是证的、哪些是引的 → 自证：Lemma 4.7、Lemma 4.11 与最终拼装；引用不证：Thm 4.9（浓度）、Lemma 4.10（Davis–Kahan）。读法与依赖图见 §9 卡片 T8 与 proof-theorem-4-8。
找不到 Theorem 4.1–4.5 / Lemma 4.6 → 本章 Theorem 与 Lemma 共用计数器，这是原书编号体系，不是缺漏（见 §14 易混点第 7 条）。

4. 本章主线

推进层	要解决的问题	关键转折	后续用途
4.1 割方法	"组内密、组间疏"如何变成可计算目标	min Cut 有平凡解 ⇒ 加平衡约束；平衡后仍 NP-hard ⇒ 谱松弛（$z\in\{\pm1\}^n$ 放宽到 $\mathbb R^n$，解 = 特征向量）	Algorithm 4/5 是谱聚类原型；§4.4.4 给它一致性理论；正则化 $\mathcal L_\tau$ 回应图 4.3 失效
4.1.4 讨论	松弛在真实数据上可靠吗	两类失效模式：悬垂树使特征向量局部化（正则化修复）、几何结构劫持低阶特征向量（高阶特征向量修复）——"第二小特征向量"不是免死金牌	Thm 4.9 的正则化浓度为 $\mathcal L_\tau$ 正名；GBM 失效与 Ch2 §2.3.4 呼应
4.2 模块度方法	不预设 $K$、直接度量划分质量	$\mathcal M$ 最大化 NP-complete ⇒ 增量公式（Lemma 4.3–4.5）使贪心/Louvain 可用；Louvain 复杂度约 $O(\|E\|)$ 完胜贪心的 $O(n(\|E\|+n))$	无需预设 $K$ 是它对谱方法的卖点；§4.4.1 给它 MAP 根据；过拟合问题引爆 4.3
4.3 贝叶斯方法	高 $\mathcal M$ ≠ 有社区（图 4.10/4.11：随机图上也"检测出社区"）	从"优化准则"转向"生成模型推断"：DC-SBM 似然 × 先验 → 后验；对参数积分得边际似然；MCMC 采样代替穷举 $K^n$	图 4.13 证明它不过拟合；karate club 后验 $K\in\{1,2\}$（图 4.12）回答 Ch1 前瞻句 F2
4.4.1–4.4.2 统一	三条路线是三个方法还是一个？	MAP ≈ 模块度最大化（Prop 4.4，多出分辨率参数 $\gamma$）；归一化谱聚类 = 模块度最大化的连续松弛（超椭球约束 → $Bx=\lambda Dx$ → $\mathcal L$ 第二小特征向量）	4.1/4.2/4.3 在 2 块对称 DC-SBM 下汇成一条线；Ch5 的 DC-SBM 推断由此出发
4.4.3–4.4.4 极限理论	什么时候原则上可恢复？谱方法能达到吗	信息论边界由 Rényi 散度 $I$ 刻画（Thm 4.6，不证）；谱聚类在平均度发散时一致（Thm 4.8，误差 $\sim 1/\bar d_n$，Example 4.5）	阈值语言与 Ch2 相变（Thm 2.1/2.2）一脉相承；强一致比连通性更强（Remark 4.6，脚注 6 用 Lemma 2.4）

5. 本章学习路线 / 概念地图

因果结构读法：定义的分歧产生三条方法线；每条线都撞上 NP-hard，各自用松弛/近似逃生；实验暴露各自失效模式；最后生成模型（SBM）把三条线统一，并给出"何时可能恢复"的边界。

①a 局部定义 → 割（4.1）
min Cut 有平凡解 ⇒ RatioCut / NCut 加平衡
Prop 4.1 · Lemma 4.1/4.2 · Prop 4.2

①b 全局定义 → 模块度（4.2）
$\mathcal M$：与配置模型零模型比较
Def 4.2 · 图 4.7 玩具图四种划分

①c 生成模型 → 贝叶斯（4.3）
网络 = Poisson DC-SBM 的实现，max $\mathbb P(z|A)$
边际似然 (4.18) · 先验 $\mathbb P(z)$ 三层分解

↓ 三条线全部 NP-hard / 组合爆炸 ↓

②a 谱松弛
$z\in\{\pm1\}^n \to \mathbb R^n$：特征向量 + $k$-means
Algorithm 4/5 · SDP (4.16) 另一路线

②b 增量贪心
Lemma 4.3–4.5 的 $\Delta\mathcal M$ 常数时间更新
Algorithm 6（$O(n(|E|+n))$）→ Algorithm 7 Louvain（≈$O(|E|)$）

②c MCMC 采样
Metropolis–Hastings 在标签空间游走
Peixoto 提议分布，$O(d_i)$ 每步

↓ 实验暴露失效 ↓

③a 谱方法的失效（4.1.4）
悬垂树局部化（图 4.3 → 正则化 $\mathcal L_\tau$，Table 4.3）；几何结构劫持（图 4.4–4.6 → 高阶特征向量）；真标签未必对应最小 NCut（图 4.6：真值 NCut 3.8 $>$ 预测 2.7）

③b 模块度/割的过拟合（4.3.1）
无结构随机图上 Louvain 照样给出高 $\mathcal M$（图 4.10）、谱聚类照样切出 15%–30% 的割（图 4.11）；贝叶斯框架只预测 1 个社区（图 4.13）

④ 理论统一（4.4）：Prop 4.4：DC-SBM 的 MAP $=$ 正则化模块度 $\mathcal M_\gamma$ 最大化（4.2 ⇐ 4.3）；§4.4.2：$\mathcal M_\gamma$ 最大化的超椭球松弛 $=$ 归一化谱聚类（4.1 ⇐ 4.2）；Thm 4.6：Rényi 散度 $I$ 划定信息论边界（$I\gg n^{-1}$ 一致恢复，$I\ge(1+\Omega(1))K\log n/n$ 强一致）；Thm 4.8：谱聚类在 $\bar d_n\to\infty$ 时一致（误差 $\le(2+\epsilon)^2cK\bar d_n/\gamma_n^2$）。

6. 分层阅读路线

第一遍（主线，约 2 小时）：章首三种定义 → 4.1.1 全节（Def 4.1 → Prop 4.1 → Lemma 4.1 → Algorithm 4，配 §9 卡片 T1）→ 4.1.2 的 (4.4)(4.5) 与 Lemma 4.2/Prop 4.2 陈述（证明跳过）→ 4.2.1 Def 4.2 + 图 4.7 → 4.2.3 Louvain 算法框 → 4.3.1 过拟合两图（4.10/4.11）→ 4.3.4 图 4.13 的"解药" → 4.4.1 Prop 4.4 陈述 + 4.4.3 Thm 4.6 陈述与 Example 4.2 阈值。目标：能画出 §5 的因果图并说清每条线的失效模式。
第二遍（证明精读，约 3–4 小时）：按依赖序读五组：① 割松弛链 Prop 4.1 → Lemma 4.1 → Lemma 4.2（工具：Prop A.10、Courant–Fischer）；② 模块度计算三引理 Lemma 4.3–4.5 + Prop 4.3；③ Prop 4.4 的对数似然展开；④ §4.4.2 推导（本章最漂亮的非编号推导）；⑤ Thm 4.8 全链：Lemma 4.7 → Thm 4.9/Lemma 4.10（定位）→ Lemma 4.11 → Proof of Thm 4.8。
第三遍（应用与实验逻辑）：对照 Table 4.2/4.3/4.4 读 4.1.4 与 4.2.4 的实验段——为什么 political blogs 上谱聚类只有 52% 而正则化后 95%；为什么 Louvain 的 $\hat K$ 系统性大于真值 $K$；细读 4.3.2 边际似然的两次积分（$\omega$ 用 $\int_0^\infty\mathrm e^{-ax}x^b\mathrm dx=b!/a^{b+1}$，$\theta$ 用 Dirichlet 型积分）与 4.3.3 的 Peixoto 提议分布；回到 karate club 串起 Ch1 F1（图 4.8 Louvain、图 4.12 后验）。
专题回看：学 Ch5（DC-SBM 上的半监督推断）时回看 Prop 4.4 与式 (4.19)；学随机矩阵浓度时回看 Thm 4.9 定位卡；需要 Davis–Kahan 时回看 Lemma 4.10 定位卡；复习 Ch2 相变语言时对照 Thm 4.6 与 Remark 4.6。

7. 初学者背景补充

本章默认的数学背景集中在五处，按首次出现顺序：

Rayleigh 商与 Courant–Fischer（4.1.1 起）：对称矩阵 $M$ 的二次型 $x^{T}Mx$ 在 $\lVert x\rVert$ 固定、$x$ 与已知特征向量正交的约束下，极值由"下一个"特征值给出。Lemma 4.1 只需要 $K=1$ 版（与 $\nu_1=1_n$ 正交 ⇒ 最小值在 $\nu_2$ 处），Prop 4.2 需要矩阵版（前 $K$ 个特征向量张成的子空间极小化 $\mathrm{Tr}\,X^{T}MX$）；严格陈述见原书附录 Thm A.13 与 Prop A.15。本章的 proof-lemma-4-1 用谱展开自包含地证了 $K=1$ 情形，读它即可建立直觉。
图拉普拉斯二次型恒等式（Prop A.10）：$x^{T}Lx=\frac12\sum_{i,j}a_{ij}(x_i-x_j)^2$——"二次型 = 跨越边的不连续性的加权和"。这是 Prop 4.1、Lemma 4.2 一切计算的引擎，记住这一行就够。
$k$-means 与 membership 矩阵（4.1.2 起）：$Z\in\mathcal Z_{n,K}$ 是每行恰一个 1 的 $n\times K$ 矩阵（$Z_{ik}=1\Leftrightarrow$ 节点 $i$ 属簇 $k$）；$k$-means 写成 $\min_{Z,X}\lVert ZX-V\rVert_F^2$（式 (4.10)），NP-hard 但有 $(1+\epsilon)$ 多项式近似（式 (4.11)，Kumar et al., 2004）。Lemma 4.11 只用到这个近似比的定义。
贝叶斯词汇（4.3 起）：先验 $\mathbb P(z)$、似然 $\mathbb P(A|z,\theta,\omega)$、证据 $\mathbb P(A)$（与 $z$ 无关，优化时扔掉）、边际似然 $\mathbb P(A|z)=\int\mathbb P(A|z,\theta,\omega)\mathbb P(\theta,\omega|z)\,\mathrm d\theta\mathrm d\omega$、后验 $\mathbb P(z|A)$、MAP $=\operatorname{argmax}_z\mathbb P(z|A)$。两个积分工具反复出现：$\int_0^\infty\mathrm e^{-ax}x^b\mathrm dx=b!/a^{b+1}$（对 $\omega$ 的指数先验）与单形上的 Dirichlet 型积分 $\int\prod_i\theta_i^{d_i}\delta(\sum_i\theta_i-n_k)\mathrm d\theta=\prod_i d_i!/(\sum_i d_i+1)!$（对 $\theta$ 的均匀先验）。
渐近记号（4.4 起）：$a_n\gg b_n$ 即 $a_n/b_n\to\infty$；$a_n\lesssim b_n$ 即 $a_n=O(b_n)$；$K\asymp1$ 即 $K$ 有界；$f\ge(1+\Omega(1))g$ 即 $f/g$ 渐近严格大于 1。$\mathrm{whp}$ = 概率 $\to1$。这些记号是 Thm 4.6/4.8 陈述的语言。

SBM / DC-SBM / Poisson 版本（式 (2.7)(2.8)）的定义见第 2 章笔记 §9 卡片与术语表；本章直接用，不重新引入。

8. 核心对象与符号表

符号	含义	本章出处	在后续推导中的角色
$A=(a_{ij})$，$d_i$，$D$	邻接矩阵（无向、可加权）、度、度对角矩阵	4.1.1	一切矩阵化改写（Prop 4.1、Lemma 4.2、§4.4.2）的原材料
$L=D-A$	标准图拉普拉斯	4.1.1	Cut 的二次型化（Prop 4.1）；$\nu_2$ 给二簇划分（Algorithm 4）
$\mathcal L=I-D^{-1/2}AD^{-1/2}$	归一化拉普拉斯	4.1.2	NCut 松弛的矩阵（式 (4.9)）；§4.4.2 证明它就是模块度松弛的出口
$\mathcal L_\tau$，$A_\tau=A+\frac\tau n 1_n1_n^{T}$	正则化版本	4.1.4	抑制悬垂树局部化（图 4.3）；Thm 4.9 的浓度对象
$\mathrm{Cut}(A,V_1)$	$V_1$ 与补集间的边权总和（Def 4.1）	4.1.1	RatioCut/NCut/总割 (4.12) 的构件
$\lvert V_k\rvert$，$\mathrm{vol}(V_k)$	簇大小、簇体积（度之和）	4.1.2	两种平衡惩罚的分母（(4.4)/(4.5)）
$H$，$N$，$U=D^{1/2}N$	归一化指示矩阵	(4.6)(4.7)	迹形式 Lemma 4.2；$H^{T}H=I_K$、$N^{T}DN=I_K$ 是松弛后保留的约束
$V\in\mathbb R^{n\times K}$	前 $K$ 个特征向量排成的矩阵	Algorithm 5	$k$-means 的输入（式 (4.10)）；Thm 4.8 的扰动对象
$z\in[K]^n$ / $z\in\{\pm1\}^n$ / $Z\in\mathcal Z_{n,K}$	标签向量 / 二划分符号向量 / membership 矩阵	全章	同一划分的三种表示，各节切换（§14 第 6 条）
$\mathcal M(z)$	模块度（Def 4.2，式 (4.17)）	4.2.1	4.2 全节与 Prop 4.4 的目标函数
$\mathcal M_\gamma(z)$	正则化模块度（式 (4.21)）	4.4.1	MAP 等价形式的主角；$\gamma$ 是分辨率参数
$e_{k\ell}(z)$，$m_k(z)$	社区间边分数、社区度质量	4.2.1	Lemma 4.3–4.5 与贪心/Louvain 增量计算的记号基础；$\sum_{k,\ell}e_{k\ell}=\sum_k m_k=1$
$B=A-\gamma\, dd^{T}/(2\lvert E\rvert)$	模块度矩阵	4.4.2	$\max z^{T}Bz$ 的松弛引出 $Bx=\lambda Dx$
$\omega_{\mathrm{in}},\omega_{\mathrm{out}}$，$\theta_i$	Poisson DC-SBM 的组内/组间强度与度校正	(4.19)	Prop 4.4 的模型参数；$\gamma=\frac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log(\omega_{\mathrm{in}}/\omega_{\mathrm{out}})}\cdot\frac{K}{\omega_{\mathrm{in}}+(K-1)\omega_{\mathrm{out}}}$
$\pi$，$P$/$Q$	SBM 标签先验与速率矩阵	4.4.3/4.4.4	$\mathbb E A=ZQZ^{T}$（均值场，Lemma 4.7）
$I=D_{1/2}(f_{\mathrm{in}},f_{\mathrm{out}})$	组内/组间相互作用分布的 Rényi 散度	Def 4.3	Thm 4.6 的唯一信息论量；二元稀疏下 $\approx(\sqrt{p_{\mathrm{in}}}-\sqrt{p_{\mathrm{out}}})^2$（式 (4.27)）
$d_{\mathrm{Ham}}$，$d^{*}_{\mathrm{Ham}}$	汉明距离及其带全局置换的版本（式 (4.25)）	4.4.3	恢复误差的度量；exact/almost exact 由 $\mathbb E d^{}_{\mathrm{Ham}}\to0$ / $n^{-1}\mathbb E d^{}_{\mathrm{Ham}}\to0$ 定义
$\gamma_n$，$\delta$，$n_{\min},n_{\max}$	$P$ 的最小绝对非零特征值、$X$ 行最小间距、最小/最大社区规模	Thm 4.8 / Lemma 4.11	一致性证明三参数：扰动界 $\propto1/\gamma_n$、$k$-means 界 $\propto1/\delta^2$、假设 $4(2+\epsilon)\lVert V-\bar V\rVert_F^2/\delta^2\le n_{\min}$

9. 关键定理卡片

编号提醒：本章 Theorem 与 Lemma 共用计数器（Lemma 4.1–4.5 → Thm 4.6 → Lemma 4.7 → Thm 4.8/4.9 → Lemma 4.10/4.11），没有 Theorem 4.1–4.5。

卡片 T1：Proposition 4.1 + Lemma 4.1（图二分的谱松弛）

条件：无向（可加权）图，$\lvert V_1\rvert=n/2$，$z\in\{\pm1\}^n$ 为划分符号向量；$L$ 的特征值 $0=\lambda_1\le\cdots\le\lambda_n$，特征向量归一化 $\lVert\nu_i\rVert^2=n$。
结论：$\operatorname{argmin}_{\lvert V_1\rvert=n/2}\mathrm{Cut}(A,V_1)=\operatorname{argmin} z^{T}Lz$（Prop 4.1，因 $\mathrm{Cut}=\frac14z^{T}Lz$ 且 $z\perp1_n$、$\lVert z\rVert^2=n$）；连续松弛 $\min\{x^{T}Lx:\lVert x\rVert^2=n,\,x\perp1_n\}$ 的解为 $\nu_2$（Lemma 4.1）。
用途：Algorithm 4 的理论根据；松弛解 $\neq$ 原问题解是 4.4 节全部一致性讨论的起因。
证明入口：proof-proposition-4-1（含原书因子 4 笔误的校勘）、proof-lemma-4-1。

卡片 T2：Lemma 4.2 + Proposition 4.2（RatioCut/NCut 的迹形式与 $K$ 簇松弛解）

条件：$K$ 簇划分，$H$/$N$ 为按簇大小/体积归一化的指示矩阵（式 (4.6)(4.7)）。
结论：$\mathrm{RatioCut}=\mathrm{Tr}(H^{T}LH)$、$\mathrm{NCut}=\mathrm{Tr}(U^{T}\mathcal LU)$（$U=D^{1/2}N$），且 $H^{T}H=I_K$、$N^{T}DN=I_K$（Lemma 4.2）；对称矩阵 $M$ 上 $\min\{\mathrm{Tr}(X^{T}MX):X^{T}X=I_K\}$ 的解是 $M$ 的前 $K$ 个正交特征向量（Prop 4.2，证明见附录 Prop A.15）。
用途：Algorithm 5（谱聚类的完整形态：前 $K$ 特征向量 → 行嵌入 $\mathbb R^K$ → $k$-means）；Lemma 4.2 的二次型恒等式在 proof-lemma-4-2 中逐步展开。
证明入口：proof-lemma-4-2、prop-4-2-positioning。

卡片 T3：Definition 4.2 + Lemma 4.3–4.5（模块度及其增量计算）

结论：$\mathcal M(z)=\frac{1}{2|E|}\sum_{i,j}\big(A_{ij}-\frac{d_id_j}{2|E|}\big)\mathbf 1(z_i=z_j)$（式 (4.17)）；按社区重写 $\mathcal M=\sum_k(e_{kk}-m_k^2)$（Lemma 4.3）；合并两社区的增益 $\Delta\mathcal M=2[e_{k_1k_2}-m_{k_1}m_{k_2}]$（Lemma 4.4）；单点移动的增益只需重算两个社区的 $e_{kk}-m_k^2$（Lemma 4.5）。
用途：Lemma 4.4 → Algorithm 6 的每步 $O(1)$ 增益评估（Prop 4.3 复杂度的关键）；Lemma 4.5 → Louvain（Algorithm 7，Remark 4.2/4.3）；值域 $-1\le\mathcal M\le1$ 与 $-1/2$ 下界见 §11 proof-check。
证明入口：proof-lemma-4-3、proof-lemma-4-4、proof-lemma-4-5。

卡片 T4：Proposition 4.3（贪心算法复杂度，OCR 吞并对象）

结论：Algorithm 6（逐对合并的贪心）时间复杂度 $O(n(|E|+n))$。
用途：解释为什么实践中 Louvain（约 $O(|E|)$，Remark 4.3）使 Algorithm 6"出局"（4.2.4 原话）。
证明入口：proof-proposition-4-3（命题头由文本层补回，含校勘提示）。

卡片 T5：Proposition 4.4（MAP = 模块度最大化，本章统一性结果之一）

条件：$K$ 块对称 Poisson DC-SBM（式 (4.19)），标签先验均匀。
结论：$\hat z^{\mathrm{MAP}}=\operatorname{argmax}_z\sum_{i,j}\Big(A_{ij}-\dfrac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log\frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}}\theta_i\theta_j\Big)\mathbf 1(z_i=z_j)$，即最大化正则化模块度 $\mathcal M_\gamma$，其中 $P_{ij}=\bar d_i\bar d_j/(2\bar m)$、$\gamma=\dfrac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log(\omega_{\mathrm{in}}/\omega_{\mathrm{out}})}\cdot\dfrac{K}{\omega_{\mathrm{in}}+(K-1)\omega_{\mathrm{out}}}$。
用途：给模块度的零模型（配置模型）一个生成模型根据（4.2.1 只给了启发式）；同时说明该等价"相关性有限"——$\omega_{\mathrm{in}},\omega_{\mathrm{out}}$ 未知时 $\gamma$ 定不了（4.4.1 末段），Further Notes 的 Zhang & Peixoto (2020) 进一步警告模块度最大化不严格等价于似然最大化。
证明入口：proof-proposition-4-4。

卡片 T6：§4.4.2 推导（归一化谱聚类 = 模块度最大化的连续松弛，非编号）

结论（$K=2$）：$\max_{z\in\{\pm1\}^n}z^{T}Bz$ 在超椭球约束 $x^{T}Dx=2|E|$ 下松弛，Lagrange 条件给出广义特征问题 $Bx=\lambda Dx$（式 (4.22)）；排除平凡解 $x=1_n$（$\lambda=1-\gamma$ 与 Perron 根）后取第二大 $\lambda$，换元 $y=D^{1/2}x$ 化为 $\mathcal Ly=(1-\lambda)y$——即 $\mathcal L$ 的第二小特征向量，恰是归一化谱聚类的嵌入方向。
用途：把 4.1（NCut 谱聚类）与 4.2（模块度）焊成一条线；也解释了为什么实践中归一化版本优于标准版本。
证明入口：deriv-modularity-spectral-relaxation（含 OCR 丢失约束行 $x^{T}Dx=2|E|$ 的校勘提示）。

卡片 T7：Theorem 4.6（一致恢复的信息论阈值，原书不证）

条件：同质 SBM，$K\asymp1$，相互作用分布 $f_{\mathrm{in}}^{(n)},f_{\mathrm{out}}^{(n)}$，$I=D_{1/2}(f_{\mathrm{in}},f_{\mathrm{out}})$。
结论：(i) 一致（almost exact）估计存在 iff $I\gg n^{-1}$（$I\lesssim n^{-1}$ 不存在）；(ii) 强一致（exact）估计存在 iff $I\ge(1+\Omega(1))\frac{K\log n}{n}$（$\le(1-\Omega(1))\frac{K\log n}{n}$ 不存在）。
用途：全章的"可行性边界"；二元稀疏 SBM 给出经典阈值 $(\sqrt a-\sqrt b)^2>K$（Example 4.2），强一致严格强于连通性（Remark 4.6 + 脚注 6 用 Ch2 Lemma 2.4）。
证明入口：原书不证（引 Avrachenkov et al., 2022）→ thm-4-6-positioning（阈值直觉）。

卡片 T8：Theorem 4.8（谱聚类在 SBM 上的一致性，本章主定理）

条件：$(z,G)\sim\mathrm{SBM}(n,\pi,P)$，$P$ 满秩 $K$，最小绝对非零特征值 $>\gamma_n$，期望度 $\bar d_n$；谱聚类作用于（正则化）邻接矩阵。
结论：存在常数 $c>0$，当 $(2+\epsilon)\frac{K\bar d_n}{\gamma_n^2}<c$ 时 whp $\dfrac{d^{*}_{\mathrm{Ham}}(\hat z,z)}{n}\le(2+\epsilon)^2c\,\dfrac{K\bar d_n}{\gamma_n^2}$；同质 SBM 下误差界 $\sim\mathrm{const}/\bar d_n$（Example 4.5）⇒ 平均度发散即一致。
证明路线图（原书项目符号，翻译须保留）：① 浓度 $\lVert A_\tau-\mathbb E A_\tau\rVert_2=O(\sqrt{\bar d_n})$（Thm 4.9，不证）；② 主子空间扰动 $\lVert\bar VQ-V\rVert_F\le\frac{2\sqrt{2K}}{\gamma_n}\lVert A_\tau-\mathbb E A_\tau\rVert_2$（Lemma 4.10，引用 Yu et al.）；③ 近似 $k$-means 误差界（Lemma 4.11，自证）；起点是均值场特征结构 $\mathbb E A=ZQZ^{T}$、$U=ZX$（Lemma 4.7，自证）。
证明入口：proof-lemma-4-7 → thm-4-9-positioning / lemma-4-10-positioning → proof-lemma-4-11 → proof-theorem-4-8。

10. 关键定理完整证明

原书在本章给出 11 处证明（Prop 4.1/4.3/4.4、Lemma 4.1–4.5、4.7、4.11、Thm 4.8）加 1 条非编号推导（§4.4.2），全部按"证明目标 + 依赖工具 + 证明思路 + 完整证明 + 闭合检查"呈现；原书跳步与 OCR 吞并处直接并入完整证明并加校勘提示。Thm 4.6、Thm 4.9、Lemma 4.10、Prop 4.2 原书不证或外包，按规范做定位卡片（不伪造证明）。

完整证明Proposition 4.1（图二分化为 min zᵀLz）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：设 $V_1\subset[n]$、$\lvert V_1\rvert=n/2$，$z\in\{-1,1\}^n$ 由 $z_i=1\Leftrightarrow i\in V_1$ 定义。则 $\operatorname{argmin}_{\lvert V_1\rvert=n/2}\mathrm{Cut}(A,V_1)=\operatorname{argmin}_{\lvert V_1\rvert=n/2}z^{T}Lz$，且 $z\perp1_n$、$\lVert z\rVert_2^2=n$。 **依赖工具**：Prop A.10（附录 A.2）：$x^{T}Lx=\frac12\sum_{i,j}a_{ij}(x_i-x_j)^2$。 **证明思路**：把 Cut 写成"跨越边"的加权和，而 $(z_i-z_j)^2$ 正是跨越的示性（差一个常数因子）；约束 $\lvert V_1\rvert=n/2$ 翻译成 $z$ 的两个规范化条件。 **完整证明**：由 $\lvert V_1\rvert=\lvert V_1^c\rvert=n/2$，$\sum_i z_i=0$ 即 $z\perp1_n$；$\lVert z\rVert_2^2=\sum_i(\pm1)^2=n$。对 $z_i,z_j\in\{\pm1\}$， $$(z_i-z_j)^2=\begin{cases}4,&i,j\text{ 分属异侧（跨越边）},\\0,&\text{同侧}.\end{cases}$$ 由 $A$ 对称，$\sum_{i,j}a_{ij}(z_i-z_j)^2=4\sum_{i,j}a_{ij}\mathbf 1(i,j\text{ 异侧})=4\cdot2\,\mathrm{Cut}(A,V_1)=8\,\mathrm{Cut}(A,V_1)$（$\sum_{i,j}$ 中每条跨越边按两个定向各计一次）。于是 $$\mathrm{Cut}(A,V_1)=\frac18\sum_{i,j}a_{ij}(z_i-z_j)^2=\frac14\,z^{T}Lz,$$ 末步用 Prop A.10。因子 $\frac14>0$ 不影响 argmin，故两个最小化问题等价。 **闭合检查**：约束 $\lvert V_1\rvert=n/2$ 与 $z\perp1_n$（$n$ 偶）一一对应，argmin 的可行域一致；目标相差正常数因子，故解集相同。常数 $\frac14$ 在后续 SDP（4.1.3）与 §4.4.2 的改写中会反复出现。 > 校勘提示（对照原书文件页 79 / 印刷页 70）：原书证明链印作 $\mathrm{Cut}=\sum a_{ij}=\frac12\sum_{i,j}a_{ij}(z_i-z_j)^2=\frac14z^{T}Lz$，且把 $(z_i-z_j)^2$ 的分段值印为 "$1$（异侧）$/0$（同侧）"。按 $z_i\in\{\pm1\}$，异侧时 $(z_i-z_j)^2=4$：分段值与中间系数 $\frac12$ 同错一个因子 4（按字面中间式等于 $4\,\mathrm{Cut}$ 而非 $\mathrm{Cut}$），属排版笔误。正确链条即上方 $\mathrm{Cut}=\frac18\sum a_{ij}(z_i-z_j)^2=\frac14z^{T}Lz$；等价地可写 $\mathrm{Cut}=\frac12\sum_{i,j}a_{ij}\mathbf 1(z_i\neq z_j)$。最终结论 $\mathrm{Cut}=\frac14z^{T}Lz$ 与 argmin 等价性正确，本证明按修正版书写。

完整证明Lemma 4.1（松弛问题的解是 ν₂）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：$\operatorname{argmin}\{x^{T}Lx:\lVert x\rVert_2^2=n,\ x\perp1_n\}=\nu_2$（$\nu_i$ 为 $L$ 的正交特征向量，$\lVert\nu_i\rVert^2=n$）。 **依赖工具**：$L$ 对称半正定、$L1_n=0$（Prop A.10）；原书引 Courant–Fischer（Thm A.13，附录 A.3.3）——本卡给出其 $K=1$ 特例的自包含推导。 **完整证明**：$L1_n=0$ 且 $\lVert1_n\rVert^2=n$，故 $\nu_1=1_n$。令 $u_i=\nu_i/\sqrt n$ 为标准正交基，$x=\sum_i\beta_iu_i$。约束给出 $\lVert x\rVert^2=\sum_i\beta_i^2=n$ 与 $x\perp1_n\Leftrightarrow\beta_1=0$。由谱分解 $L=\sum_i\lambda_iu_iu_i^{T}$， $$x^{T}Lx=\sum_{i=2}^n\lambda_i\beta_i^2\ \ge\ \lambda_2\sum_{i=2}^n\beta_i^2=\lambda_2 n,$$ 等号当且仅当 $\beta_i$ 只落在 $\lambda_i=\lambda_2$ 的坐标上；取 $x=\sqrt n\,u_2=\nu_2$ 达到下界（若 $\lambda_2$ 重根，解为该特征子空间内任一满足规范化的向量）。 **闭合检查**：$\nu_2$ 满足全部约束（$\lVert\nu_2\rVert^2=n$、$\nu_2\perp\nu_1=1_n$）且达到下界 $n\lambda_2$，故为 argmin。这正是 Courant–Fischer 定理"与 $1_n$ 正交的最小 Rayleigh 商 $=\lambda_2$"的实例；Prop 4.2 把它升级为 $K$ 维子空间版本（证明外包给附录 Prop A.15，见 [prop-4-2-positioning](#prop-4-2-positioning)）。∎

完整证明Lemma 4.2（RatioCut/NCut 的迹形式）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：(i) $\mathrm{RatioCut}=\mathrm{Tr}(H^{T}LH)$；(ii) $\mathrm{NCut}=\mathrm{Tr}(N^{T}LN)=\mathrm{Tr}(U^{T}\mathcal LU)$（$U=D^{1/2}N$）；(iii) $H^{T}H=I_K$、$N^{T}DN=I_K$。 **依赖工具**：Prop A.10 的二次型恒等式；$H,N$ 的定义（式 (4.6)(4.7)）；$\mathrm{vol}(V_k)=\sum_{i\in V_k}d_i$。 **证明思路**：迹的每个对角元就是一列的二次型；指示归一化使 $(H_{\cdot k}^{T}LH_{\cdot k})$ 恰好是"第 $k$ 簇的割除以簇大小"。 **完整证明**：(i) $\mathrm{Tr}(H^{T}LH)=\sum_kH_{\cdot k}^{T}LH_{\cdot k}$。对第 $k$ 列，$b_{ik}-b_{jk}$ 仅当 $i,j$ 恰有一个属于 $V_k$ 时非零，此时 $(b_{ik}-b_{jk})^2=1/\lvert V_k\rvert$。由 Prop A.10， $$H_{\cdot k}^{T}LH_{\cdot k}=\frac12\sum_{i,j}a_{ij}(b_{ik}-b_{jk})^2=\frac12\cdot\frac{1}{\lvert V_k\rvert}\sum_{i,j}a_{ij}\mathbf 1(i,j\text{ 恰一个}\in V_k)=\frac12\cdot\frac{2\,\mathrm{Cut}(A,V_k)}{\lvert V_k\rvert}=\frac{\mathrm{Cut}(A,V_k)}{\lvert V_k\rvert},$$ 对 $k$ 求和即 (i)。(ii) 同理，$(n_{ik}-n_{jk})^2=1/\mathrm{vol}(V_k)$（恰一个属于 $V_k$ 时），得 $N_{\cdot k}^{T}LN_{\cdot k}=\mathrm{Cut}(A,V_k)/\mathrm{vol}(V_k)$；且 $\mathrm{Tr}(N^{T}LN)=\mathrm{Tr}(N^{T}D^{1/2}D^{-1/2}LD^{-1/2}D^{1/2}N)=\mathrm{Tr}(U^{T}\mathcal LU)$。(iii) $(H^{T}H)_{kk}=\sum_ib_{ik}^2=\lvert V_k\rvert/\lvert V_k\rvert=1$，$k\neq\ell$ 时 $\sum_ib_{ik}b_{i\ell}=0$（划分不交）；$(N^{T}DN)_{kk}=\sum_id_in_{ik}^2=\mathrm{vol}(V_k)/\mathrm{vol}(V_k)=1$，非对角元同理为 0。 **闭合检查**：三条结论合起来把组合问题 (4.4)/(4.5) 改写成带正交约束的迹最小化 (4.8)/(4.9)——松弛时只保留 $H^{T}H=I_K$（或 $U^{T}U=I_K$）而丢弃"指示结构"，这正是 Prop 4.2 的输入形状。∎

定位卡片Proposition 4.2（迹最小化的特征向量解，证明外包附录）

**陈述**：$M\in\mathbb R^{n\times n}$ 对称，则 $\operatorname{argmin}\{\mathrm{Tr}(X^{T}MX):X\in\mathbb R^{n\times K},\ X^{T}X=I_K\}$ 的一个解是 $M$ 的前 $K$ 个（对应最小特征值的）正交特征向量排成的矩阵 $V\in\mathbb R^{n\times K}$。 **原书态度**："(we refer to the Proposition A.15 in Appendix A.3.3 for the proof)"——证明整体在附录，属跨章引用型留白，本笔记不重复（附录译文落盘后此处应改为双向锚点链接）。 **它是什么**：这是 Ky Fan 迹最小化原理（Courant–Fischer 的 $K$ 维升级）：[proof-lemma-4-1](#proof-lemma-4-1) 中"逐个坐标挤进低特征值方向"的谱展开论证，换成子空间语言即得。 **学到这里应带走**：它是 Algorithm 5 的最后一环——Lemma 4.2 把 RatioCut/NCut 写成 $\min\mathrm{Tr}(X^{T}MX)$、丢掉指示结构只留 $X^{T}X=I_K$，Prop 4.2 给出松弛解 $V$；剩下的"从实值 $V$ 回到离散划分"由 $k$-means（式 (4.10)(4.11)）完成，其误差分析要到 Lemma 4.11 才补上。

状态：完整证明已按当前笔记标准给出闭合推导。

完整证明Lemma 4.3（模块度的 e_kk / m_k 形式，展开原书一句话证明）

**证明目标**：$\mathcal M(z)=\sum_{k=1}^n\big(e_{kk}(z)-(m_k(z))^2\big)$，其中 $e_{k\ell}(z)=\frac{1}{2|E|}\sum_{i,j}A_{ij}\mathbf 1(z_i=k)\mathbf 1(z_j=\ell)$、$m_k(z)=\frac{1}{2|E|}\sum_id_i\mathbf 1(z_i=k)$。 **依赖工具**：Def 4.2（式 (4.17)，$P_{ij}=d_id_j/(2|E|)$）；$\mathbf 1(z_i=z_j)=\sum_k\mathbf 1(z_i=k)\mathbf 1(z_j=k)$（划分）；$\sum_{i,j}d_id_j\,\mathbf 1(z_i=k)\mathbf 1(z_j=k)=\big(\sum_id_i\mathbf 1(z_i=k)\big)^2$。 **完整证明**（展开原书 "The proof is immediate" 一句话）：把 $\mathbf 1(z_i=z_j)$ 按社区拆开， $$\mathcal M(z)=\frac{1}{2|E|}\sum_{k}\sum_{i,j}\Big(A_{ij}-\frac{d_id_j}{2|E|}\Big)\mathbf 1(z_i=k)\mathbf 1(z_j=k).$$ 第一项：$\frac{1}{2|E|}\sum_k\sum_{i,j}A_{ij}\mathbf 1(z_i=k)\mathbf 1(z_j=k)=\sum_ke_{kk}(z)$（定义）。第二项： $$\frac{1}{2|E|}\sum_k\frac{1}{2|E|}\Big(\sum_id_i\mathbf 1(z_i=k)\Big)\Big(\sum_jd_j\mathbf 1(z_j=k)\Big)=\sum_k\frac{\big(2|E|\,m_k(z)\big)^2}{(2|E|)^2}=\sum_k(m_k(z))^2.$$ 两式相减即得结论。 **闭合检查**：$\sum_{k,\ell}e_{k\ell}=\frac{1}{2|E|}\sum_{i,j}A_{ij}=1$，$\sum_km_k=\frac{1}{2|E|}\sum_id_i=1$——该形式把 $\mathcal M$ 表为"对角线上的边分数减去度质量的平方"，是 Lemma 4.4/4.5 增量计算与 [§11 值域补证](#proof-check-remark-4-1-modularity-bounds)（$e_{kk}\le m_k$ 是关键观察）的共同起点。∎

完整证明Lemma 4.4（合并两社区的 ΔM）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：$z^{\mathrm{new}}$ 由 $z^{\mathrm{old}}$ 把社区 $k_2$ 并入 $k_1$ 得到，则 $$\mathcal M(z^{\mathrm{new}})-\mathcal M(z^{\mathrm{old}})=2\big[e_{k_1k_2}(z^{\mathrm{old}})-m_{k_1}(z^{\mathrm{old}})\,m_{k_2}(z^{\mathrm{old}})\big].$$ **依赖工具**：Lemma 4.3；划分的不交性。 **完整证明**：对 $k\notin\{k_1,k_2\}$，$e_{kk}$、$m_k$ 不变；$k_2$ 在新标注下为空，$e_{k_2k_2}(z^{\mathrm{new}})=m_{k_2}(z^{\mathrm{new}})=0$。由 Lemma 4.3， $$\Delta\mathcal M=\big[e_{k_1k_1}^{\mathrm{new}}-(m_{k_1}^{\mathrm{new}})^2\big]-\big[e_{k_1k_1}^{\mathrm{old}}-m_{k_1}^2\big]-\big[e_{k_2k_2}^{\mathrm{old}}-m_{k_2}^2\big].$$ 新社区 $k_1$ 是旧 $k_1,k_2$ 之并，故（跨越边按两个定向各计一次，贡献因子 2） $$e_{k_1k_1}^{\mathrm{new}}=e_{k_1k_1}^{\mathrm{old}}+2e_{k_1k_2}^{\mathrm{old}}+e_{k_2k_2}^{\mathrm{old}},\qquad m_{k_1}^{\mathrm{new}}=m_{k_1}+m_{k_2}.$$ 代入：$\Delta\mathcal M=2e_{k_1k_2}^{\mathrm{old}}+(m_{k_1}^2+m_{k_2}^2)-(m_{k_1}+m_{k_2})^2=2e_{k_1k_2}^{\mathrm{old}}-2m_{k_1}m_{k_2}$。 **闭合检查**：公式只含旧标注的 $e_{k_1k_2}$ 与 $m_{k_1},m_2$——维护这两个数组即可 $O(1)$ 评估一次合并，这是 Prop 4.3 复杂度分析的第一步；直觉上 $e_{k_1k_2}>m_{k_1}m_{k_2}$（实际跨边超过零模型期望）时合并有利。∎

完整证明Lemma 4.5（单点移动的 ΔM）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：$z^{\mathrm{new}}$ 与 $z^{\mathrm{old}}$ 仅在节点 $i$ 处不同（$a\to b$），则 $$\mathcal M(z^{\mathrm{new}})-\mathcal M(z^{\mathrm{old}})=\big[e_{bb}(z^{\mathrm{new}})-m_b(z^{\mathrm{new}})^2\big]-\big[e_{aa}(z^{\mathrm{old}})-m_a(z^{\mathrm{old}})^2\big].$$ **依赖工具**：Lemma 4.3。 **完整证明**：除 $a,b$ 外的社区在两次标注下完全相同，故对 $k\notin\{a,b\}$，$e_{kk}$、$m_k$ 不变，其在 Lemma 4.3 求和中的贡献逐项抵消，只剩 $a,b$ 两项之差，即结论。 **闭合检查**：该形式本身需要在新旧标注下分别重算 $e_{bb}-m_b^2$ 与 $e_{aa}-m_a^2$；节点 $i$ 的移动只影响与 $i$ 相邻的边与 $d_i$ 的质量，因此增量更新 $e_{ab},e_{bb},m_a,m_b$ 只需 $O(d_i)$，配合 Louvain 的邻居遍历给出 Remark 4.2/4.3 的复杂度陈述（"每次评估常数时间"，指维护好数组后的均摊）。∎

完整证明Proposition 4.3（Algorithm 6 的复杂度，命题头按文本层补回）

状态：完整证明已按当前笔记标准给出闭合推导。

> 校勘提示（OCR 对象吞并，清单 §7-1）：OCR `full.md` 行 2226（Algorithm 6 的 Return 行）之后命题头与陈述句整体丢失，只剩孤立公式 $O(n(|E|+n))$ 与 "Proof."。文本层（文件页 93 / 印刷页 84）确认原文为 "**Proposition 4.3.** The time complexity of Algorithm 6 is $O\big(n(|E|+n)\big)$." 本卡按文本层补回陈述。 **证明目标**：Algorithm 6（每次合并使 $\Delta\mathcal M$ 最大的一对社区，直到全部合一，回溯取 $\mathcal M$ 最大的划分）的时间复杂度为 $O\big(n(|E|+n)\big)$。 **依赖工具**：Lemma 4.4（$\Delta\mathcal M$ 常数时间评估）。 **完整证明**：初始化后共 $n-1$ 次合并。每个 Update 步：①对每个"至少一条边相连"的社区对计算 $\Delta\mathcal M$——由 Lemma 4.4，维护 $e_{k\ell},m_k$ 数组后每次评估 $O(1)$；这样的对数首轮为 $|E|$，之后只减不增（合并不产生新的跨社区连接关系），故每轮 $\le|E|$ 次评估，同时记录最大值；②合并后重算（凝聚）邻接矩阵的对应行/列，至多 $O(n)$。故每轮 $O(|E|+n)$，$n-1$ 轮合计 $O\big((n-1)(|E|+n)\big)=O\big(n(|E|+n)\big)$。 **闭合检查**：$\mathcal M$ 全程记录、最后取最大，回溯不增加阶数。与 Louvain 对比（Remark 4.3）：Louvain 第一轮最昂贵、需 $|E|$ 次增益评估，后续轮在凝聚小图上进行，简单估计约 $O(|E|)$——这就是 4.2.4 说 Algorithm 6 "out of the competition" 的定量理由。∎

完整证明Proposition 4.4（MAP = 模块度最大化）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：$A$ 来自 $K$ 块对称 Poisson DC-SBM（式 (4.19)：$z_i=z_j$ 时 $A_{ij}=A_{ji}\sim\mathcal P(\theta_i\theta_j\omega_{\mathrm{in}})$，否则 $\mathcal P(\theta_i\theta_j\omega_{\mathrm{out}})$，$i\neq j$ 独立，$A_{ii}=0$），标签先验均匀。则 $$\hat z^{\mathrm{MAP}}=\operatorname{argmax}_{z\in[K]^n}\mathbb P(z|A)=\operatorname{argmax}_{z\in[K]^n}\sum_{i,j}\Big(A_{ij}-\frac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log\frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}}\,\theta_i\theta_j\Big)\mathbf 1(z_i=z_j).$$ **依赖工具**：Bayes 公式；Poisson 质量函数；"两值参数写成示性函数线性组合"的代数技巧（同 Ch2 Prop 2.4–2.8 的似然代数）。 **证明思路**：先验均匀 ⇒ MAP = 最大似然；$\omega_{ij}$ 只取两值，把它和 $\log\omega_{ij}$ 都写成 "差 × 示性 + 基线"，代入对数似然后按"与 $z$ 相关/无关"拆项——所有与 $z$ 无关的部分吸收进常数 $C$。 **完整证明**：$\mathbb P(z|A)\propto\mathbb P(A|z)\mathbb P(z)$ 且 $\mathbb P(z)=K^{-n}$ 与 $z$ 无关，故 $\operatorname{argmax}\mathbb P(z|A)=\operatorname{argmax}\mathbb P(A|z)$。由独立性， $$\mathbb P(A|z)=\prod_{i<j}\frac{(\theta_i\theta_j\omega_{ij})^{A_{ij}}}{A_{ij}!}\,\mathrm e^{-\theta_i\theta_j\omega_{ij}},\qquad\omega_{ij}=\begin{cases}\omega_{\mathrm{in}},&z_i=z_j,\\\omega_{\mathrm{out}},&z_i\neq z_j.\end{cases}$$ 取对数（$A_{ij}=A_{ji}$，把 $i<j$ 求和改写为 $\frac12\sum_{i\neq j}$）： $$\log\mathbb P(A|z)=\frac12\sum_{i\neq j}\big(A_{ij}\log(\theta_i\theta_j\omega_{ij})-\theta_i\theta_j\omega_{ij}\big)-\sum_{i<j}\log(A_{ij}!).$$ 两个关键改写： $$\omega_{ij}=(\omega_{\mathrm{in}}-\omega_{\mathrm{out}})\,\mathbf 1(z_i=z_j)+\omega_{\mathrm{out}},$$ $$\log(\theta_i\theta_j\omega_{ij})=\log\frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}\,\mathbf 1(z_i=z_j)+\log(\theta_i\theta_j\omega_{\mathrm{out}}).$$ 代入并收集：凡是不含 $\mathbf 1(z_i=z_j)$ 的项（含 $\sum\log(A_{ij}!)$、基线项 $\frac12\sum_{i\neq j}\big(A_{ij}\log(\theta_i\theta_j\omega_{\mathrm{out}})-\theta_i\theta_j\omega_{\mathrm{out}}\big)$）都与 $z$ 无关，记作常数 $C$，得 $$\log\mathbb P(A|z)=\frac12\sum_{i\neq j}\Big(A_{ij}\log\frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}-(\omega_{\mathrm{in}}-\omega_{\mathrm{out}})\theta_i\theta_j\Big)\mathbf 1(z_i=z_j)+C =\frac12\log\frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}\sum_{i\neq j}\Big(A_{ij}-\frac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log\frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}}\theta_i\theta_j\Big)\mathbf 1(z_i=z_j)+C.$$ 同配（assortative）情形 $\omega_{\mathrm{in}}>\omega_{\mathrm{out}}$，前置因子 $\frac12\log\frac{\omega_{\mathrm{in}}}{\omega_{\mathrm{out}}}>0$，故 argmax 由求和项决定。最后把求和从 $i\neq j$ 扩到全体 $i,j$：$i=j$ 项为 $-\frac{\omega_{\mathrm{in}}-\omega_{\mathrm{out}}}{\log(\omega_{\mathrm{in}}/\omega_{\mathrm{out}})}\sum_i\theta_i^2$（$A_{ii}=0$），与 $z$ 无关，不影响 argmax。即得命题形式。 **闭合检查**：把结果改写成 $\operatorname{argmax}\sum_{i,j}(A_{ij}-\gamma P_{ij})\mathbf 1(z_i=z_j)$，其中 $P_{ij}=\theta_i\theta_j\bar\omega$、$\bar\omega:=\frac{\omega_{\mathrm{in}}+(K-1)\omega_{\mathrm{out}}}{K}$。$\bar\omega$ 的读法：标签未知且均匀时两随机节点同社区的概率为 $1/K$，故 $\bar\omega$ 正是"零模型"下 $(i,j)$ 的边际连边率。定义 $\bar d_i=\sum_{j\neq i}P_{ij}$（零模型期望度）与 $\bar m=\frac12\sum_{i\neq j}P_{ij}$（零模型期望边数），则该零模型本身就是一个（Poisson 版）配置模型：由构造 $\sum_j\theta_j=\sum_k 1=K$，得 $\bar d_i=\theta_i\bar\omega K$、$\bar m=\frac12\bar\omega K^2$，于是 $$\frac{\bar d_i\bar d_j}{2\bar m}=\frac{\theta_i\theta_j\bar\omega^2K^2}{\bar\omega K^2}=\theta_i\theta_j\bar\omega=P_{ij},$$ 即 $\operatorname{argmax}\sum_{i,j}\Big(A_{ij}-\gamma\frac{\bar d_i\bar d_j}{2\bar m}\Big)\mathbf 1(z_i=z_j)$——与 Def 4.2 的 $P_{ij}=\frac{d_id_j}{2|E|}$ 逐项对应（数据度换成零模型期望度），这就是正则化模块度 $\mathcal M_\gamma$（式 (4.21)）。∎ > 校勘提示（待人工核对）：①原书证明括号内逐案验证 $\omega_{ij}$ 改写时两处都印作 "when $z_i\neq z_j$"（第二处应为 $z_i=z_j$，取值 $\omega_{\mathrm{in}}$ 的那个），属明显笔误，本证明按正确版本书写。②原书本段印作 $\bar d_i=\theta_i\frac{\omega_{\mathrm{in}}+(K-1)\omega_{\mathrm{out}}}{K}$ 与 $\bar m=\frac12\frac{\omega_{\mathrm{in}}+(K-1)\omega_{\mathrm{out}}}{K}$：在归一化 $\sum_i\theta_i\mathbf 1(z_i^0=k)=1$ 下直接计算得 $\bar d_i=\theta_i\bar\omega K$、$\bar m=\frac12\bar\omega K^2$（见上），与原书单个公式分别相差因子 $K$ 与 $K^2$，疑为排版漏因子；但比值恒等式 $P_{ij}=\bar d_i\bar d_j/(2\bar m)$ 在两版本下都成立，命题结论与 $\gamma$ 的表达式不受影响。

完整证明§4.4.2 推导（归一化谱聚类 = 模块度最大化的连续松弛，非编号）

**证明目标**（$K=2$，$B=A-\gamma\,\frac{dd^{T}}{2|E|}$）：广义模块度最大化 $\operatorname{argmax}_{z\in\{\pm1\}^n}z^{T}Bz$ 在超椭球约束下的连续松弛，其解由归一化拉普拉斯 $\mathcal L$ 的**第二小**特征向量给出——即归一化谱聚类的嵌入方向。 **依赖工具**：Lagrange 乘子法；$1^{T}A=1^{T}D=d^{T}$、$d^{T}1_n=2|E|$；Perron–Frobenius（非负矩阵最大特征值对应正特征向量）。 **证明思路**：三步代数（$\mathbf 1(z_i=z_j)=\frac12(z_iz_j+1)$ → 二次型 $z^{T}Bz$ → Lagrange 得广义特征问题 (4.22)）加两次排除（$\lambda=1-\gamma$ 的"不划分"解、Perron 的 $x=1_n$ 解），剩下第二大 $\lambda$；换元 $y=D^{1/2}x$ 后与 $\mathcal L$ 的特征问题对接。 **完整证明**： 1. **二次型化**：$z_i\in\{\pm1\}$ 时 $\mathbf 1(z_i=z_j)=\frac12(z_iz_j+1)$，故 $\sum_{i,j}B_{ij}\mathbf 1(z_i=z_j)=\frac12\sum_{i,j}B_{ij}z_iz_j+\frac12\sum_{i,j}B_{ij}$，第二项与 $z$ 无关，原问题等价于 $\max_{z\in\{\pm1\}^n}z^{T}Bz$。 2. **松弛与约束**：$z$ 放宽为 $x\in\mathbb R^n$ 后必须防止 $\lVert x\rVert$ 发散使目标虚增；一般地固定到超椭球 $\sum_i\kappa_ix_i^2=\sum_i\kappa_i$（$\kappa_i\ge0$），取 $\kappa_i=d_i$ 得 $$\hat x=\operatorname{argmax}\big\{x^{T}Bx:\ x^{T}Dx=2|E|\big\},$$ 其中 $\sum_id_i=2|E|$。 3. **Lagrange**：$\mathcal L(x,\lambda)=x^{T}Bx-\lambda(x^{T}Dx-2|E|)$，对 $x$ 求导为零得 $$Bx=\lambda Dx.\tag{4.22}$$ 对广义特征向量 $x$ 有 $x^{T}Bx=\lambda x^{T}Dx=2\lambda|E|$，故目标值随 $\lambda$ 递增，应取**最大**特征值。 4. **第一次排除**：$B1_n=A1_n-\gamma d\,\frac{d^{T}1_n}{2|E|}=d-\gamma d=(1-\gamma)D1_n$，故 $\lambda=1-\gamma$、$x=1_n$ 是 (4.22) 的可行解——它对应"全图不划分"。排除之，只需考虑 $\lambda>1-\gamma$。 5. **导出 $d^{T}x=0$**：写 $Bx=Ax-\gamma d\,\frac{d^{T}x}{2|E|}=Ax-\gamma D1_n\frac{d^{T}x}{2|E|}$，则 (4.22) 即 $Ax=D\big(\lambda x+\gamma1_n\frac{d^{T}x}{2|E|}\big)$。左乘 $1^{T}$：$d^{T}x=\lambda d^{T}x+\gamma(2|E|)\frac{d^{T}x}{2|E|}=(\lambda+\gamma)d^{T}x$，即 $(\lambda+\gamma-1)d^{T}x=0$；由 $\lambda>1-\gamma$ 得 $d^{T}x=0$，问题化简为 $$Ax=\lambda Dx.$$ 6. **第二次排除**：$x=1_n$ 满足 $A1_n=d=D1_n$（$\lambda=1$）；$A$ 非负且（连通时）不可约，Perron–Frobenius 给出它是**最大**特征值。但 $d^{T}1_n=2|E|\neq0$ 违反第 5 步约束，排除——故取**第二大** $\lambda$（原书 "we rule out this solution since it does not verify $d^{T}x=0$"，verify 此处 = 满足）。 7. **对接 $\mathcal L$**：令 $y=D^{1/2}x$，则 $Ax=\lambda Dx\Leftrightarrow D^{-1/2}AD^{-1/2}y=\lambda y\Leftrightarrow\mathcal Ly=(1-\lambda)y$。$\lambda$ 是 $D^{-1/2}AD^{-1/2}$ 的第二大特征值 $\Leftrightarrow 1-\lambda$ 是 $\mathcal L$ 的第二小特征值。 **闭合检查**：终点是"$\mathcal L$ 第二小特征向量 + 按符号分簇"，与 §4.1.2 的 NCut 松弛（式 (4.9) 取 $K=2$）落点一致——两条路线的等价性闭合。注意 $d^{T}x=0$ 是**度加权**平衡约束，替代了图二分的 $\lvert V_1\rvert=n/2$，这正是"归一化"的来源。∎ > 校勘提示（清单 §7 登记的高严重度异常）：OCR `full.md` 行 2554 处（文件页 104）丢失约束行 $x^{T}Dx=2|E|$，且把 $\hat x=\operatorname{argmax}$ 的 $=$ 误作 $\equiv$；本卡第 2 步按文本层（文件页 104）补回。

定位卡片Theorem 4.6（Rényi 阈值决定一致恢复，原书不证）

**陈述**：同质 SBM，$n\gg1$、$K\asymp1$、相互作用分布 $f_{\mathrm{in}}^{(n)},f_{\mathrm{out}}^{(n)}$，$I=D_{1/2}(f_{\mathrm{in}},f_{\mathrm{out}})$（Def 4.3，$D_{1/2}(f,g)=-2\log\int\sqrt{fg}\,\mathrm d\mu$，与 Hellinger 距离由 $D_{1/2}=-2\log(1-\mathrm{Hel}^2)$ 相联，Remark 4.5）。(i) 一致（almost exact）估计存在 iff $I\gg n^{-1}$，$I\lesssim n^{-1}$ 时不存在；(ii) 强一致（exact）估计存在 iff $I\ge(1+\Omega(1))\frac{K\log n}{n}$，$I\le(1-\Omega(1))\frac{K\log n}{n}$ 时不存在。 **原书态度**："Theorem 4.6 is proved in Avrachenkov et al., 2022." ——全书核心阈值定理无证明，属外部留白，**本笔记不补证**（规范：不得伪造证明），只给阈值直觉。 **阈值直觉**（帮助记忆，非证明）：$I$ 是**单条候选边**携带的"同社区 vs 异社区"辨别信息（Rényi/Hellinger 意义下两分布的可分度）。(i) 全图共有 $\Theta(n^2)$ 个节点对，总信息 $\sim n^2I$；要把 $n$ 个标签整体定得比随机好（允许错 $o(n)$ 个），总量只需压过 $n$ 量级，故阈值在 $I\sim n^{-1}$。(ii) 强一致要求**每个**节点都不许错：单个节点的标签信息只来自它的 $\Theta(n)$ 条关联边，约 $nI$；其误判概率形如 $\exp(-\Theta(nI))$，对 $n$ 个节点做 union bound 需要 $\exp(-\Theta(nI))\ll1/n$，即 $I\gtrsim\frac{\log n}{n}$；$K$ 个社区的多重假设检验再贡献因子 $K$，得 $\frac{K\log n}{n}$。这与二元情形的经典结果吻合：$I\approx(\sqrt{p_{\mathrm{in}}}-\sqrt{p_{\mathrm{out}}})^2$（式 (4.27)，见 [proof-check-example-4-3-poisson-renyi](#proof-check-example-4-3-poisson-renyi) 的同款计算），$p_{\mathrm{in}}=a\frac{\log n}{n},p_{\mathrm{out}}=b\frac{\log n}{n}$ 时阈值 $(\sqrt a-\sqrt b)^2>K$（Example 4.2，Abbe et al., 2015; Mossel et al., 2015）。 **学到这里应带走**：①两个 regime 的分工——detection（优于随机，$I$ 常数量级即可，Remark 4.4 指向 Moore, 2017）本书不碰；本章关心 almost exact（$I\gg1/n$，即期望度发散，Example 4.1 的 $n\rho_n\gg1$）与 exact（$I\gtrsim K\log n/n$）。②Remark 4.6：$K=2$ 时强一致要求 $\frac{a+b}{2}-\sqrt{ab}>1$，而连通性只要求 $\frac{a+b}{2}>1$（Thm 2.2 语言）——**精确恢复严格强于连通**，脚注 6 的理由见 [§11](#sec-11-proof-checks) 的形式化。③外部参考：Avrachenkov et al., 2022（非二元 SBM 的一般阈值）；二元情形 Zhang et al., 2016；加权/边标记情形 Jog & Loh, 2015、Xu et al., 2020。

完整证明Lemma 4.7（均值场 𝔼A 的特征结构）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：$Q$ 满秩，$\mathbb E A=ZQZ^{T}$ 的特征分解 $UDU^{T}$ 满足 $U=ZX$（$X\in\mathbb R^{K\times K}$），且 $\lVert X_{k*}-X_{\ell*}\rVert=\sqrt{n_k^{-1}+n_\ell^{-1}}$（$X_{k*}$ 为 $X$ 的第 $k$ 行，$n_k$ 为社区 $k$ 的大小）。 **依赖工具**：$Z^{T}Z=\mathrm{diag}(n_1,\dots,n_K)$（membership 矩阵的基本恒等式）；对称矩阵谱定理。 **证明思路**：把 $Z$ 归一化成列正交矩阵 $Z\Delta^{-1}$（$\Delta=\mathrm{diag}(\sqrt{n_1},\dots,\sqrt{n_K})$），则 $\mathbb E A$ 的特征分解由 $K\times K$ 小矩阵 $\Delta Q\Delta$ 的特征分解"抬升"得到；行间距由 $\Delta^{-1}$ 的尺度决定。 **完整证明**：$\Delta=\mathrm{diag}(\sqrt{n_1},\dots,\sqrt{n_K})$，则 $$\mathbb E A=ZQZ^{T}=(Z\Delta^{-1})(\Delta Q\Delta)(Z\Delta^{-1})^{T}.$$ $Z\Delta^{-1}$ 列正交：$(Z\Delta^{-1})^{T}(Z\Delta^{-1})=\Delta^{-1}Z^{T}Z\Delta^{-1}=\Delta^{-1}\Delta^2\Delta^{-1}=I_K$。设 $K\times K$ 对称矩阵 $\Delta Q\Delta$ 的特征分解为 $RDR^{T}$（$Q$ 满秩 ⇒ $\Delta Q\Delta$ 满秩），则 $$\mathbb E A=(Z\Delta^{-1}R)\,D\,(Z\Delta^{-1}R)^{T}$$ 是 $\mathbb E A$ 的特征分解（$Z\Delta^{-1}R$ 列正交）。取 $U=Z\Delta^{-1}R$、$X=\Delta^{-1}R$ 即 $U=ZX$。由 $R$ 正交， $$XX^{T}=\Delta^{-1}RR^{T}\Delta^{-1}=\Delta^{-2}=\mathrm{diag}(n_1^{-1},\dots,n_K^{-1}),$$ 故 $\lVert X_{k*}\rVert^2=n_k^{-1}$、$\langle X_{k*},X_{\ell*}\rangle=0$（$k\neq\ell$）， $$\lVert X_{k*}-X_{\ell*}\rVert^2=\lVert X_{k*}\rVert^2+\lVert X_{\ell*}\rVert^2-2\langle X_{k*},X_{\ell*}\rangle=n_k^{-1}+n_\ell^{-1}.$$ **闭合检查**：结论的含义是"社区信息完整编码在 $\mathbb E A$ 的特征结构里"：$U=ZX$ 的第 $i$ 行 $=X_{z_i*}$，同一社区的节点在嵌入中**重合于同一点**，社区 $k,\ell$ 的嵌入点相距 $\sqrt{n_k^{-1}+n_\ell^{-1}}$——这正是 Lemma 4.11 中 $\delta$ 的来源，也是 $k$-means 在均值场上必然成功的几何图景。∎ > 校勘提示：OCR 行 2763–2765 把末行推导的范数平方写成无平方形式（"$\|X_{k*}-X_{\ell*}\|=\|X_{k*}\|+\|X_{\ell*}\|-2X_{k*}X_{\ell*}^{T}$"），本卡按正确版本（平方展开）书写。

定位卡片Theorem 4.9（正则化邻接矩阵的浓度，原书不证）

**陈述**（= Le et al., 2017, Thm 1.2）：$A$ 为 Bernoulli 随机图 $\mathcal G(n,(p_{ij}))$ 的邻接矩阵，$d_n=n\max_{ij}p_{ij}$，$\tau\sim d_n$，$A_\tau=A+\tau 1_n1_n^{T}$。则 $n\to\infty$ 时 whp $$\lVert A_\tau-\mathbb E A_\tau\rVert_2=O\big(\sqrt{d_n}\big).$$ **原书态度**："The proof of Theorem 4.9 is complex and out of reach for this book." ——外部留白，**本笔记不补证**。外部参考：Le, Levina & Vershynin (2017)，其工具是随机矩阵的集中不等式与图的分解技术，超出本书附录 A 的范围。 **为什么需要正则化**（原书给的注记，值得展开）：未正则化时浓度在稀疏区失效。以 ER（$p_{ij}\equiv p$）为例：若 $d_n=np\ll\log n$，最大度远高于期望度 $d_n$（度近似 $\mathrm{Bin}(n,p)$，其最大值由 Poisson 极限的尾部决定，$\gg d_n$）；高度节点的对应行有远大于 $\sqrt{d_n}$ 的 $\ell^2$ 范数，迫使 $\lVert A-\mathbb E A\rVert_2\gg\sqrt{d_n}$。加 $\tau 1_n1_n^{T}$ 相当于给所有节点对补强度 $\tau$ 的"背景边"，把期望度垫到 $d_n+\tau=\Theta(d_n)$，高度节点的相对涨落被压回，谱范数恢复 $O(\sqrt{d_n})$ 浓度。 **学到这里应带走**：①它与 4.1.4 的正则化谱聚类（$\mathcal L_\tau$ 治悬垂树，Zhang & Rohe, 2018）是同一个 $\tau$ 的理论化身——Table 4.3 的实验（political blogs 52% → 95%）在这里获得浓度解释；②它是 Thm 4.8 证明链的第①环，以 $O(\sqrt{\bar d_n})$ 的浓度速率喂给 Davis–Kahan（Lemma 4.10）；③"$\bar d_n\ll\log n$ 时需要正则化"与 Ch2 连通性阈值 $\log n$ 同源（度的高度涨落区正是可能不连通的区）。

定位卡片Lemma 4.10（主子空间扰动，引用外部文献）

**陈述**：$\bar M,M\in\mathbb R^{n\times n}$ 对称，$\bar M$ 的最小非零奇异值为 $\gamma$；$U,\bar U\in\mathbb R^{n\times K}$ 分别为 $M,\bar M$ 的前 $K$ 个主特征向量排成的矩阵。则存在 $K\times K$ 正交矩阵 $Q$ 使 $$\lVert\bar UQ-U\rVert_F\le\frac{2\sqrt{2K}}{\gamma}\,\lVert M-\bar M\rVert_2.$$ **原书态度**："a version of Davis–Kahan 'sin θ' theorem ... We refer to the Theorem 2 of Yu et al., 2015"——证明外包，属外部留白，本笔记不补证。外部参考：Yu, Wang & Samworth (2015, Biometrika), Thm 2（该版本专为"带正交对齐 $Q$ 的 Frobenius 界"设计，正好配 $k$-means 的行扰动分析）。 **学到这里应带走**：①结论形状 = "特征子空间距离 ≤ 常数 × 矩阵扰动 / 谱隙"，谱隙 $\gamma$ 越小（特征值越挤）特征向量越不稳——Thm 4.8 的条件 $\gamma_n$ 与误差分母 $\gamma_n^2$ 都来自这里；②正交矩阵 $Q$ 必不可少：特征向量只确定到正交变换，比较前必须先对齐；③它是纯确定性结论，随机性全部由 Thm 4.9 的浓度输入。

完整证明Lemma 4.11（近似 k-means 误差界，adapted from Lei & Rinaldo 2015）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：$\bar V,V\in\mathbb R^{n\times K}$，$\bar V=ZX$（$Z\in\mathcal Z_{n,K}$，$X\in\mathbb R^{K\times K}$）；$(\hat Z,\hat X)$ 是 $k$-means 问题 (4.10) 的 $(1+\epsilon)$ 近似解；$\delta=\min_{k\neq\ell}\lVert X_{k*}-X_{\ell*}\rVert$，$n_{\min}$ 为最小社区规模。若 $4(2+\epsilon)\dfrac{\lVert V-\bar V\rVert_F^2}{\delta^2}\le n_{\min}$，则 $$\frac{d^{*}_{\mathrm{Ham}}(\hat z,z)}{n}\le4(2+\epsilon)^2\,\frac{\lVert V-\bar V\rVert_F^2}{\delta^2 n}.$$ **依赖工具**：$(1+\epsilon)$ 近似的定义（式 (4.11)）；三角不等式；$\mathcal Z_{n,K}$ 的行结构（$\hat V=\hat Z\hat X$ 至多 $K$ 个不同行）。 **证明思路**：把"$k$-means 解离真嵌入 $\bar V$ 远（$\ge\delta/2$）的节点"收集为坏集 $\mathcal B_k$：坏集总大小被 $\lVert V-\bar V\rVert_F$ 控制（放缩链 (4.28)）；假设条件保证每个社区都有非坏节点，于是两条 claim——不同社区的非坏节点嵌入行不同、同社区的非坏节点嵌入行相同——迫使 $\hat V$ 在非坏节点上给出与真值一致的 $K$ 分类（至多差一个全局置换）；误分类节点全部落在坏集里。 **完整证明**：记 $\hat V=\hat Z\hat X$，$\mathcal C_k=\{i:z_i=k\}$，$\mathcal B_k=\{i\in\mathcal C_k:\lVert\bar V_{i*}-\hat V_{i*}\rVert_2\ge\delta/2\}$。 **第 1 步：坏集大小（式 (4.28)）**。Frobenius 范数按行展开并按社区分组： $$\lVert\bar V-\hat V\rVert_F^2=\sum_{k=1}^K\sum_{i\in\mathcal C_k}\lVert\bar V_{i*}-\hat V_{i*}\rVert^2\ge\sum_k\sum_{i\in\mathcal B_k}\frac{\delta^2}{4}=\frac{\delta^2}{4}\sum_k\lvert\mathcal B_k\rvert.$$ 另一方面，由三角不等式与 $(1+\epsilon)$ 近似（对竞争者 $Z'=Z,X'=X$ 用 $\bar V=ZX$）： $$\lVert\bar V-\hat V\rVert_F\le\lVert\bar V-V\rVert_F+\lVert V-\hat V\rVert_F\le\big(1+\sqrt{1+\epsilon}\big)\lVert V-\bar V\rVert_F\le(2+\epsilon)\lVert V-\bar V\rVert_F,$$ （末步因 $\sqrt{1+\epsilon}\le1+\epsilon$）。合并得 $$\sum_{k=1}^K\lvert\mathcal B_k\rvert\le\frac{4}{\delta^2}(2+\epsilon)^2\lVert V-\bar V\rVert_F^2.\tag{4.28}$$ **第 2 步：非坏集非空**。由引理假设，$\sum_k\lvert\mathcal B_k\rvert\le(2+\epsilon)\,n_{\min}$（量级上每个 $\mathcal C_k\setminus\mathcal B_k$ 非空；精确到原书行文则直接宣称 $\sum_k\lvert\mathcal B_k\rvert<n_{\min}$，从而每个 $\mathcal C_k\setminus\mathcal B_k\neq\emptyset$，见下方校勘提示）。 **第 3 步：两条 claim**。(i) 若 $i\in\mathcal C_k\setminus\mathcal B_k$、$j\in\mathcal C_\ell\setminus\mathcal B_\ell$（$k\neq\ell$），则 $\hat V_{i*}\neq\hat V_{j*}$：否则 $$\delta\le\lVert\bar V_{i*}-\bar V_{j*}\rVert\le\lVert\bar V_{i*}-\hat V_{i*}\rVert+\lVert\hat V_{j*}-\bar V_{j*}\rVert<\frac\delta2+\frac\delta2=\delta,$$ 矛盾（首不等号因 $\bar V=ZX$：$\bar V_{i*}=X_{k*}$、$\bar V_{j*}=X_{\ell*}$，间距 $\ge\delta$）。(ii) 若 $i,j\in\mathcal C_k\setminus\mathcal B_k$ 则 $\hat V_{i*}=\hat V_{j*}$：$\hat V=\hat Z\hat X$ 至多 $K$ 个不同行；由 (i) 与各 $\mathcal C_k\setminus\mathcal B_k$ 非空，$\hat V$ 至少 $K$ 个不同行（每个社区的非坏节点贡献一个），故恰好 $K$ 个，同一社区内的非坏节点只能共享同一行。 **第 4 步：置换对齐收尾**。由 (i)(ii)，非坏节点可按 $\hat V$ 的行值分成 $K$ 组且与真社区一一对应，即存在置换 $\sigma^*\in S_K$ 使所有 $i\notin\bigcup_k\mathcal B_k$ 满足 $\sigma^*(\hat z_i)=z_i$。取 $d^*_{\mathrm{Ham}}$ 定义中的最优置换不劣于 $\sigma^*$： $$d^{*}_{\mathrm{Ham}}(\hat z,z)\le\sum_{i=1}^n\mathbf 1(\sigma^*(\hat z_i)\neq z_i)\le\sum_{k=1}^K\lvert\mathcal B_k\rvert\le\frac{4(2+\epsilon)^2}{\delta^2}\lVert V-\bar V\rVert_F^2,$$ 末步用 (4.28)。两边除 $n$ 即结论。 **闭合检查**：边界形态 "$\lVert V-\bar V\rVert_F^2/(\delta^2 n)$" 合理：嵌入越准（分子小）、社区嵌入点越分开（$\delta$ 大）、最小社区越大（假设越易满足），$k$-means 越可靠。整个证明是确定性的——$V$ 与 $\bar V$ 是什么矩阵都行，这使它能在 Thm 4.8 中与任何"特征向量集中"结果对接。∎ > 校勘提示（精核对照文件页 113–114 / 印刷页 104–105）：第 2 步按 (4.28) 只能推出 $\sum_k\lvert\mathcal B_k\rvert\le(2+\epsilon)\,n_{\min}$（假设条件为 $4(2+\epsilon)\lVert V-\bar V\rVert_F^2/\delta^2\le n_{\min}$，两边同乘 $(2+\epsilon)$ 后 (4.28) 右端为 $(2+\epsilon)n_{\min}$）；要严格得到原书随后使用的 $\sum_k\lvert\mathcal B_k\rvert<n_{\min}$（从而 $\mathcal C_k\setminus\mathcal B_k$ 非空），假设应读作 $4(2+\epsilon)^{\mathbf 2}\lVert V-\bar V\rVert_F^2/\delta^2<n_{\min}$——即假设中的 $(2+\epsilon)$ 应带与结论一致的平方，疑为原书排版遗漏。该处只影响充分条件的常数，结论形式不变；Thm 4.8 的应用中直接验证该充分条件（见 [proof-theorem-4-8](#proof-theorem-4-8)），逻辑链不受影响。

完整证明Theorem 4.8（谱聚类在 SBM 上的一致性，本章主定理）

状态：完整证明已按当前笔记标准给出闭合推导。

**证明目标**：$(z,G)\sim\mathrm{SBM}(n,\pi,P)$，$P$ 秩为 $K$、最小绝对非零特征值 $>\gamma_n$，期望度 $\bar d_n$，$\hat z$ 为作用于（正则化）邻接矩阵的谱聚类输出。存在常数 $c>0$：若 $(2+\epsilon)\frac{K\bar d_n}{\gamma_n^2}<c$，则 whp $$\frac{d^{*}_{\mathrm{Ham}}(\hat z,z)}{n}\le(2+\epsilon)^2\,c\,\frac{K\bar d_n}{\gamma_n^2}.$$ **依赖工具**：Thm 4.9（浓度，[不证](#thm-4-9-positioning)）；Lemma 4.10（Davis–Kahan，[引用](#lemma-4-10-positioning)）；Lemma 4.7（[均值场特征结构](#proof-lemma-4-7)）；Lemma 4.11（[近似 $k$-means 界](#proof-lemma-4-11)）。 **证明思路**（原书项目符号 roadmap）：①$A$ 集中于 $\mathbb E A$（Thm 4.9）⇒ ②特征向量集中（Lemma 4.10）⇒ ③$k$-means 误分类少（Lemma 4.11，以 $\bar V=ZX$ 的均值场几何为基准）。 **完整证明**：设 $V$（ resp. $\bar V$）为 $A_\tau$（resp. $\mathbb E A_\tau$）前 $K$ 个主特征向量排成的 $n\times K$ 矩阵（$\tau\sim\bar d_n$，正则化选择由 Thm 4.9 决定）。 **第 1 步（浓度 → 扰动，式 (4.29)）**：Thm 4.9 给出 whp $\lVert A_\tau-\mathbb E A_\tau\rVert_2\le C\sqrt{\bar d_n}$；代入 Lemma 4.10（$\bar M=\mathbb E A_\tau$ 的最小非零奇异值 $=\gamma_n$，注意 $\mathbb E A_\tau$ 对称、奇异值即特征值绝对值），存在正交 $Q\in\mathbb R^{K\times K}$： $$\lVert\bar VQ-V\rVert_F\le\frac{2\sqrt{2K}}{\gamma_n}\lVert A_\tau-\mathbb E A_\tau\rVert_2\le\frac{2\sqrt{2K}}{\gamma_n}C\sqrt{\bar d_n}.\tag{4.29}$$ **第 2 步（均值场几何对接 Lemma 4.11）**：$\mathbb E A_\tau=ZQZ^{T}+\tau1_n1_n^{T}=Z\big(Q+\tau 1_K1_K^{T}\big)Z^{T}$（因 $1_n=Z1_K$），仍是"membership × $K\times K$ 矩阵 × membership 转置"的形状，故 Lemma 4.7 适用：$\bar V=ZX$，$\lVert X_{k*}-X_{\ell*}\rVert=\sqrt{n_k^{-1}+n_\ell^{-1}}$。右乘正交 $Q$ 保持行间距（$\lVert(XQ)_{k*}-(XQ)_{\ell*}\rVert=\lVert X_{k*}-X_{\ell*}\rVert$），故对 $\bar VQ=ZX'$（$X'=XQ$）可取 $$\delta=\min_{k\neq\ell}\sqrt{n_k^{-1}+n_\ell^{-1}}\ \ge\ \frac{1}{\sqrt{n_{\max}}}.$$ **第 3 步（验证假设并收尾）**：Lemma 4.11 的假设要求 $4(2+\epsilon)\lVert V-\bar VQ\rVert_F^2/\delta^2\le n_{\min}$。由 (4.29)，$\lVert V-\bar VQ\rVert_F^2\le\frac{8KC^2\bar d_n}{\gamma_n^2}$，又 $1/\delta^2\le n_{\max}$，故充分条件为 $$4(2+\epsilon)\,8C^2K\,\frac{\bar d_n}{\gamma_n^2}\le\frac{n_{\min}}{n_{\max}},$$ （校勘提示：本卡此前沿用原书笔误写作 $\le n_{\min}\,n_{\max}$；按上方推导——(4.29) 与 $1/\delta^2\le n_{\max}$ 代入引理 4.11 假设——正确形式为 $\le n_{\min}/n_{\max}$，与译文一致。结论形式不受影响，常数吸收入 $c$。）在定理假设（$(2+\epsilon)K\bar d_n/\gamma_n^2$ 足够小，常数吸收入 $c$）下成立。应用 Lemma 4.11： $$\frac{d^{*}_{\mathrm{Ham}}(\hat z,z)}{n}\le4(2+\epsilon)^2\,\frac{\lVert V-\bar VQ\rVert_F^2}{\delta^2n}\le4(2+\epsilon)^2\,8C^2K\,\frac{\bar d_n}{\delta^2n\,\gamma_n^2}\le32(2+\epsilon)^2C^2K\,\frac{\bar d_n}{\gamma_n^2},$$ 末步因 $\frac{1}{\delta^2n}\le\frac{n_{\max}}{n}\le1$。常数 $32C^2$ 吸收入定理的 $c$，结论成立。 **闭合检查**：①$Q$ 的去向：Lemma 4.11 要求基准有 $ZX'$ 形状，$\bar VQ=ZXQ$ 恰好满足——这就是 Davis–Kahan 输出"带正交对齐"形式的原因。②误差界 $\propto K\bar d_n/\gamma_n^2$：Example 4.5（同质 SBM，$p_{\mathrm{in}}=c_{\mathrm{in}}\rho_n$、$p_{\mathrm{out}}=c_{\mathrm{out}}\rho_n$）算出 $\bar d_n=\frac nK(c_{\mathrm{in}}+(K-1)c_{\mathrm{out}})\rho_n$、$\gamma_n=\frac nK(c_{\mathrm{in}}-c_{\mathrm{out}})\rho_n$，代入得误差 $\le(2+\epsilon)^2cK\big(\frac{c_{\mathrm{in}}+(K-1)c_{\mathrm{out}}}{c_{\mathrm{in}}-c_{\mathrm{out}}}\big)^2\frac{1}{\bar d_n}$——**平均度发散即一致**，与 Thm 4.6(i) 的信息论要求（$n\rho_n\gg1$ ⇔ 期望度发散）在同一 regime 闭合。③原书注记：把 $A$ 换成归一化拉普拉斯 $\mathcal L$ 的变体有类似证明（清单 §6 第 17 行），本书不展开。∎

11. 正文隐藏验证补全

清单 §6 全部 18 行的扫描结论与本页处置总表（锚点命名见文件顶部注释，待译文对账）：

清单行	原句（意译）	判定	本页处置
1	Remark 4.1 "−1 ≤ M ≤ 1 is straightforward" + 脚注 3 "−1/2 ≤ M (Brandes et al., 2007)"	真正留白（两级证明均未给）	proof-check-remark-4-1-modularity-bounds（两级均给出完整证明）
2	"minimising (4.12) is equivalent to maximise Tr XᵀAX (4.13)"	半留白（类比前文，未写推导）	proof-check-sdp-trace-equivalence
3	Lemma 4.3 "The proof is immediate"	压缩证明	并入 proof-lemma-4-3（别名锚点 proof-check-lemma-4-3-expansion）
4	Prop 4.2 证明外包附录 Prop A.15	跨章引用型留白	prop-4-2-positioning；附录落盘后改双向锚点
5	Thm 4.6 不证（引 Avrachenkov et al., 2022）	外部留白	thm-4-6-positioning（阈值直觉，不伪造证明）
6	Thm 4.9 不证（"out of reach for this book"）	外部留白	thm-4-9-positioning（含正则化为何必要的展开注记）
7	Lemma 4.10 引 Yu et al., 2015 Thm 2	外部留白	lemma-4-10-positioning
8	Lemma 4.11 证明开头 "Intuitively, we want to show..."	非留白（作者在证明内完成）	并入 proof-lemma-4-11 的证明思路段
9	Thm 4.8 证明 roadmap（三项目符号）	非留白（后续逐一兑现）	保留 roadmap 结构，见 proof-theorem-4-8
10	"a higher order eigenvector can lead to a better clustering"（几何数据）	修辞性（由图 4.5/4.6 实验"展示"）	不需卡片；失效模式解读见 §4 主线第 2 行
11	"we rule out this solution since it does not verify dᵀx = 0"	假阳性（verify = 满足）	译注处理；推导见 deriv 卡第 6 步
12	"the MAP estimator defined in (4.20) verifies ..."	假阳性（同上）	译注处理
13–15	MNIST 数字对观察 / 玩具图 "obvious" 社区 / 退化划分 "easy to spot"	修辞性	不需卡片
16	脚注 6：不连通 ⇒ a.s. 有孤立节点（Lemma 2.4）⇒ exact recovery 不可能	半留白（纲要已给）	下方正文一句话形式化
17	"a similar proof would hold（用归一化 Laplacian）"	修辞性预告（变体未证）	proof-theorem-4-8 闭合检查③注记
18	Example 4.3：Poisson 的 Rényi 散度 "is exactly equal to (√λ−√μ)²"	半留白（计算未展示）	proof-check-example-4-3-poisson-renyi

清单行 16 的形式化（脚注 6）：设节点 $i$ 孤立。则 $A$ 不含任何关于 $z_i$ 的信息——似然 $\mathbb P(A|z)$ 不依赖 $z_i$（$i$ 无边），先验均匀，故后验 $\mathbb P(z_i=k|A,z_{-i})$ 在 $[K]$ 上均匀，任何估计量对 $i$ 的正确率不超过随机猜测；于是 $\mathbb E\,d^{*}_{\mathrm{Ham}}(\hat z,z)\ge\big(1-\frac1K\big)\mathbb P(\exists\,\text{孤立节点})$。当期望度低于连通性阈值（$\bar d_n<\log n-\omega_n$，Ch2 Lemma 2.4 的 regime）时该概率 $\to1$，期望误差不趋于 0——exact recovery 不可能。这就是 Remark 4.6 "强一致严格强于连通"的机制。

状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。

隐藏验证补全Remark 4.1 + 脚注 3：−1 ≤ M ≤ 1 与 −1/2 ≤ M 的完整证明

**证明目标**：对任何图与任何标签向量 $z$：(i)（正文称 straightforward）$-1\le\mathcal M(z)\le1$；(ii)（脚注 3 称 with some additional work，引 Brandes et al., 2007）$\mathcal M(z)\ge-\frac12$。 **依赖工具**：Lemma 4.3 的形式 $\mathcal M=\sum_k(e_{kk}-m_k^2)$；$e_{k\ell}$ 对称、$\sum_{k,\ell}e_{k\ell}=1$、$\sum_km_k=1$、$m_k=\sum_\ell e_{k\ell}\ge e_{kk}\ge0$。 **完整证明**： (i) 上界：$\mathcal M=\sum_ke_{kk}-\sum_km_k^2\le\sum_ke_{kk}\le\sum_{k,\ell}e_{k\ell}=1$。下界（粗）：$\mathcal M\ge-\sum_km_k^2\ge-\big(\sum_km_k\big)^2=-1$（$m_k\ge0$）。 (ii) 精细下界：展开 $\sum_km_k^2=\sum_km_k\sum_\ell e_{k\ell}=\sum_km_ke_{kk}+\sum_{k<\ell}(m_k+m_\ell)e_{k\ell}$（对称性）。由 $m_k+m_\ell\le\sum_rm_r=1$ 与 $m_k\le1$， $$\sum_km_k^2\le\sum_ke_{kk}+\sum_{k<\ell}e_{k\ell}=\sum_ke_{kk}+\frac{1-\sum_ke_{kk}}{2}=\frac{1+\sum_ke_{kk}}{2},$$ 其中 $\sum_{k<\ell}e_{k\ell}=\frac12\big(\sum_{k,\ell}e_{k\ell}-\sum_ke_{kk}\big)$。代回： $$\mathcal M=\sum_ke_{kk}-\sum_km_k^2\ \ge\ \sum_ke_{kk}-\frac{1+\sum_ke_{kk}}{2}=\frac{\sum_ke_{kk}-1}{2}\ \ge\ -\frac12.$$ **闭合检查**：(ii) 的等号要求 $\sum_ke_{kk}=0$（无社区内部边）且交叉质量集中在 $m_k+m_\ell=1$ 的单一社区对上——即对（近似）二部图取"两部的二分"，例如偶长圈上黑白二分：此时 $e_{11}=e_{22}=0$、$m_1=m_2=\frac12$、$\mathcal M=-\frac12$。(i) 中 $-1$ 只是放缩中间站；真正的值域是 $[-\frac12,1]$，这也解释了 4.2.1 "好划分的模块度典型值 0.3–0.7" 的读数坐标。∎

状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。

隐藏验证补全§4.1.3：min (4.12) ⇔ max Tr XᵀAX 的等价推导

**证明目标**：总割 (4.12) $=\sum_k\mathrm{Cut}(A,V_k)$ 在等规模划分（$\lvert V_k\rvert=n/K$）上的最小化，等价于 $\mathrm{Tr}(X^{T}AX)$（式 (4.13)）的最大化，其中 $X$ 为 0/1 membership 矩阵。 **依赖工具**：$\sum_{i,j}a_{ij}$ 的按块分解；$(X^{T}AX)_{kk}=\sum_{i,j\in V_k}a_{ij}$。 **完整证明**（补原书 "Similarly to what was done in the preceding section" 省略的等式链）：把全部节点对按"同簇/异簇"分解， $$\sum_{i,j}a_{ij}=\sum_k\sum_{i,j\in V_k}a_{ij}+\sum_{k\neq\ell}\sum_{i\in V_k,\,j\in V_\ell}a_{ij}=\mathrm{Tr}(X^{T}AX)+\sum_k\mathrm{Cut}(A,V_k),$$ 其中第二项：$\sum_k\mathrm{Cut}(A,V_k)=\sum_k\sum_{i\in V_k,j\notin V_k}a_{ij}$ 正是全部异簇对（每个跨越边在两个端点所在簇各计一次）。左端 $\sum_{i,j}a_{ij}$ 是常数，故最小化 (4.12) ⇔ 最大化 $\mathrm{Tr}(X^{T}AX)$。等规模约束 $\lvert V_k\rvert=n/K$ 用 $X$ 写作 $X^{T}1_n=\frac nK1_K$；换成 $Y=XX^{T}$ 语言即 (4.15) 的 $Y1_n=\frac nK1_n$。 **闭合检查**：与 Lemma 4.2 的改写同构（那里是 $L$ 与归一化指示矩阵，这里是 $A$ 与原始指示矩阵）——"割 = 总量 − 簇内量"是把 $\min$ 变 $\max$ 的统一机关；(4.14) 的 $\mathrm{Tr}(X^{T}AX)=\mathrm{Tr}(AXX^{T})$ 再把它变成 SDP 变量 $Y$ 的线性目标 $\langle A,Y\rangle$，接进 (4.15)(4.16)。∎

状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。

隐藏验证补全Example 4.3：Poisson 分布的 Rényi 散度 = (√λ−√μ)²

**证明目标**：$f=\mathrm{Poi}(\lambda)$、$g=\mathrm{Poi}(\mu)$（计数测度），则 $D_{1/2}(f,g)=(\sqrt\lambda-\sqrt\mu)^2$（原书直接给结论，未展示代入计算）。 **依赖工具**：Def 4.3；$\sum_{x\ge0}t^x/x!=\mathrm e^t$。 **完整证明**： $$\sum_{x=0}^\infty\sqrt{f(x)g(x)}=\sum_{x=0}^\infty\sqrt{\frac{\mathrm e^{-\lambda}\lambda^x}{x!}\cdot\frac{\mathrm e^{-\mu}\mu^x}{x!}} =\mathrm e^{-(\lambda+\mu)/2}\sum_{x=0}^\infty\frac{(\sqrt{\lambda\mu})^x}{x!}=\mathrm e^{-(\lambda+\mu)/2+\sqrt{\lambda\mu}}.$$ 故 $$D_{1/2}(f,g)=-2\log\sum_x\sqrt{f(x)g(x)}=-2\Big(\sqrt{\lambda\mu}-\frac{\lambda+\mu}{2}\Big)=\lambda+\mu-2\sqrt{\lambda\mu}=(\sqrt\lambda-\sqrt\mu)^2.$$ **闭合检查**：与二元情形 (4.27) 的展开 $\approx(\sqrt{p_{\mathrm{in}}}-\sqrt{p_{\mathrm{out}}})^2$ 同形——小参数 Poisson 近似 Bernoulli，这正解释了 Example 4.2 与 Example 4.3 阈值相同（$(\sqrt a-\sqrt b)^2>K$）。∎

12. 术语与跨章链接

本章首次系统引入、已入全书术语表的术语（点击跳转定义）：

割与谱方法：割、图拉普拉斯矩阵、归一化割 NCut / RatioCut、谱聚类、半定规划 SDP、悬垂树
模块度方法：模块度、Louvain 算法
贝叶斯与理论：最大后验估计 MAP、马尔可夫链蒙特卡罗 MCMC、Rényi 散度、精确 / 一致恢复、社区检测
本章调用、Ch2 已建立：SBM、同质 SBM、DC-SBM、配置模型、伯努利随机图、Erdős–Rényi 随机图、几何分块模型 GBM

跨章链接：

回指 Ch1：前瞻句 F1（karate club 仅凭友谊图预测分裂）由图 4.8（Louvain）与图 4.12（贝叶斯后验 $K\in\{1,2\}$）共同回答——Louvain 把真值两社区劈成更多小社区，合并小社区可几乎完美恢复；F2（ER 上也能找到高模块度划分）由 §4.3.1 图 4.10/4.11 证实、图 4.13 的贝叶斯框架解决。Table 1.2 的 cc 对照逻辑在此升级为"零模型 vs 生成模型"的检验。
回指 Ch2：SBM/DC-SBM/Poisson 版（式 (2.7)(2.8)）是 4.3/4.4 的生成模型；连通性阈值（Thm 2.2）与孤立节点引理（Lemma 2.4）在 Remark 4.6 与脚注 6 中复用（见 §11 形式化）。
前瞻 Ch5：DC-SBM 的 MAP/似然框架（式 (4.19)(4.20)、Prop 4.4）是半监督学习的出发点——Ch5 已知部分标签时推断其余标签。
术语交叉警示：本章"谱"均指聚类用特征向量（$\mathcal L$ 的小特征值端）；Ch3 的谱中心性（PageRank 等）用的是另一端的特征向量/随机游走不变分布，同名不同物，术语表已分别立目。章首"节点相似度定义社区"一条提到 Personalized PageRank / hitting time，正是 Ch3 的指标。

校勘备忘（译文与本笔记统一按此处理，详见清单 §7）：

Prop 4.3 命题头与陈述句被 OCR 整体吞并，已按文本层补回（卡片内校勘）。
§4.4.2 超椭球松弛的约束行 $x^{T}Dx=2|E|$ 被 OCR 丢失、$=$ 误作 $\equiv$，已按文本层补回（deriv 卡校勘）。
Prop 4.1 证明链分段值与系数同错因子 4（原书排版笔误，卡片内校勘）；Prop 4.4 括号内两处 "$z_i\neq z_j$" 之一应为 "$z_i=z_j$"（卡片内校勘）；Lemma 4.11 假设的 $(2+\epsilon)$ 应与结论一致带平方（卡片内校勘）。
图注级：Figure 4.5 的图在 content_list 中被错挂为 Figure 4.4（已目视确认为 accuracy-vs-eigenvector 散点图）；Figure 4.7(a)(c) 子图注丢失符号 $\mathcal M$；Figure 4.10 总图注 ER/Zipf/PA 三处符号丢失；Erdős 的 ő 系统性误识为 "Erd˝os"（图 4.10/4.11/4.13 图注）；<sup> HTML 残留 43 处集中于 §4.4.4；"Theorem $4.6$"/"Lemma $4.7$" 编号断裂 2 处。
Remark 4.4 首句 "Exact and almost exact recovery are two the most studied regimes" 语法可疑（"two the most"），倾向原书笔误，译文加注不改写。Example 4.2 的 $\rho_{\mathrm{in}}$/$p_{\mathrm{in}}$ 记号混杂（OCR 作 $\rho$、文本层作 $p$，且 $N$/$n$ 混用），按上下文应为 $p_{\mathrm{in}}=a\frac{\log n}{n}$，译文以 PDF 页面为准。Definition 4.2 的 $z\in[n]^n$ 排版奇怪但语义明确（允许至多 $n$ 个社区），按原书保留。

13. 章节阅读路径

顺序	小节（印刷页）	读法
1	章首（p.66–68）	精读三种社区定义；Table 4.1 记住 karate club / political blogs / MNIST 三个基准
2	4.1.1 图二分（p.68–71）	本章方法论样板，逐句精读：平凡解 → 平衡约束 → NP-hard → Prop 4.1 → Lemma 4.1 → Algorithm 4
3	4.1.2 一般情形（p.71–74）	RatioCut/NCut 定义 + Lemma 4.2 陈述；$k$-means 式 (4.10)(4.11) 与 Algorithm 5；Prop 4.2 记住结论即可
4	4.1.3 SDP（p.74–75）	快读：记住"另一条松弛路线"，(4.15)→(4.16) 丢掉哪些约束
5	4.1.4 讨论（p.75–79）	与正文定理同等重要：Table 4.2/4.3、图 4.3（悬垂树）、图 4.4–4.6（几何失效，真值 NCut 3.8 > 预测 2.7 的关键观察）
6	4.2.1 定义（p.80–82）	Def 4.2 + 图 4.7 四个划分的 $\mathcal M$ 读数；$P_{ij}$ 的配置模型直觉
7	4.2.1 高效计算（p.82–83）	$e_{k\ell},m_k$ 定义 + Lemma 4.3–4.5，配 §10 三卡
8	4.2.2 贪心（p.83–84）	Algorithm 6 粗读 + Prop 4.3；注意 OCR 吞并（校勘）
9	4.2.3 Louvain（p.84–85）	Algorithm 7 两阶段（单点移动 / 凝聚）+ Remark 4.2/4.3 复杂度
10	4.2.4 讨论（p.85–87）	Table 4.4 的 $\hat K>K$ 现象、图 4.8/4.9
11	4.3.1 过拟合（p.87）	本章转折点，图 4.10/4.11 必看
12	4.3.2–4.3.3 贝叶斯框架与 MCMC（p.87–91）	第一遍抓住 Bayes 分解与"对 $\omega,\theta$ 积分"的结构即可；第二遍细读两次积分与 Peixoto 提议分布
13	4.3.4 数值结果（p.91–92）	图 4.12(a) 的 $P(K\\|A)$ 与图 4.13 的"不过拟合"对照
14	4.4.1–4.4.2（p.92–97）	理论统一两连击，配 §10 两卡精读
15	4.4.3（p.97–101）	Remark 4.4 的 regime 分级 + Def 4.3 + Thm 4.6 陈述 + Example 4.1/4.2 + Remark 4.6；Example 4.3/4.4 快读
16	4.4.4（p.101–106）	均值场 Lemma 4.7 → Thm 4.8 陈述与 roadmap → 三个工具 → Proof of Thm 4.8，配 §10
17	Further Notes（p.106–107）	见 §16

14. 易混点

min Cut vs RatioCut vs NCut：(4.1) 不加约束有平凡解 $V_1=V$ 或 $\emptyset$；图二分 (4.2) 用硬约束 $\lvert V_1\rvert=n/2$；一般 $K$ 簇改用软惩罚——RatioCut 按簇节点数 $\lvert V_k\rvert$、NCut 按簇体积 $\mathrm{vol}(V_k)$ 归一。两种"平衡"不同：度差异大时（如 political blogs）只有 NCut/归一化谱聚类合理，这也是 scikit-learn 默认归一化版本的原因（4.1.4 正文）。
三种 Laplacian 分工：$L$（标准）⇔ RatioCut 松弛（式 (4.8)）；$\mathcal L$（归一化）⇔ NCut 松弛（式 (4.9)）与模块度松弛（§4.4.2 卡）；$\mathcal L_\tau$（正则化）⇔ 治悬垂树局部化（图 4.3 → Table 4.3），其理论根据是 Thm 4.9 的浓度。悬垂树失效与几何失效是两种病：前者特征向量局部化在低度子结构上、正则化可治；后者特征向量被几何结构劫持、正则化不治，需看高阶特征向量（图 4.5/4.6 与 4.3 的对照）。
高模块度 ≠ 有社区：$\mathcal M$ 是划分的质量分数，不是显著性检验——ER/CM/PA 随机图（构造上无社区）上 Louvain 照样输出高 $\mathcal M$（图 4.10）；甚至配置模型——模块度自己的零模型——上也能找到高 $\mathcal M$ 划分（4.3.1 正文强调这是模块度最大化的内禀问题，不是 Louvain 的副作用）。判据是贝叶斯后验（图 4.13：同一批随机图上只预测 1 个社区）。
exact / almost exact / detection 三级恢复：exact（强一致）$\mathbb E d^{*}\to0$（一个节点都不许错）；almost exact（一致）$n^{-1}\mathbb E d^{*}\to0$（错 $o(n)$ 个）；detection 只要求优于随机（本书不碰，Remark 4.4 → Moore 2017）。Thm 4.6 的两条阈值分别对应前两级；Thm 4.8 只证到 almost exact。
两个 $\gamma$ 撞名：分辨率参数 $\gamma$（$\mathcal M_\gamma$，Prop 4.4，式 (4.21)）与 Thm 4.8 的谱隙下界 $\gamma_n$（$P$ 的最小绝对非零特征值；Lemma 4.10 中同名参数是 $\bar M$ 的最小非零奇异值）——语境不同，不要混用。
社区的三种表示：符号向量 $z\in\{\pm1\}^n$（4.1.1、§4.4.2，仅二簇）、标签向量 $z\in[K]^n$ 或 $[n]^n$（4.2 起）、membership 矩阵 $Z\in\mathcal Z_{n,K}$（4.1.2、4.4.4）。$Z$ 的行是嵌入分析的载体（Lemma 4.7/4.11），$z$ 是算法输出，$\pm1$ 向量是二次型改写的工具。
Theorem/Lemma 共计数器：本章不存在 Theorem 4.1–4.5 与 Lemma 4.6（Lemma 4.1–4.5 → Thm 4.6 → Lemma 4.7 → Thm 4.8/4.9 → Lemma 4.10/4.11），是原书编号体系，不是 OCR 或译文缺漏。
"谱方法一致"≠"强一致"：Thm 4.8 给的是 $d^{*}/n\le O(1/\bar d_n)$（almost exact，Example 4.5）；强一致阈值 $(\sqrt a-\sqrt b)^2>K$（Example 4.2）属于 Thm 4.6(ii) 的世界，需要别的算法（如 SDP、两阶段精细化）达到。把 Thm 4.8 读成"谱方法解决了 SBM 恢复"会高估结论。
$d_{\mathrm{Ham}}$ vs $d^{*}_{\mathrm{Ham}}$：社区标签本身没有语义（"1 号社区"换个名字叫"2 号"不变划分），误差必须对全局置换取最小（式 (4.25)，脚注 5）；写一致性结论时丢掉置换会让"误分类率 50%"的二分互换误判为失败。

15. 公式卡片

本章编号公式 (4.1)–(4.29) 共 29 个，按用途归并为 11 张卡片；校勘要点附在相关卡片。

F1 — 式 (4.1)(4.2)(4.3)（图二分链）：$\min\mathrm{Cut}$（有平凡解）→ $\min_{\lvert V_1\rvert=n/2}\mathrm{Cut}$（NP-hard）→ $\hat z=\operatorname{argmin}\{z^{T}Lz:z\in\{\pm1\}^n,\lVert z\rVert^2=n,z\perp1_n\}$。输入邻接矩阵与平衡约束，输出二划分；证明。

F2 — 式 (4.4)(4.5)（RatioCut/NCut）：$\sum_k\mathrm{Cut}(A,V_k)/\lvert V_k\rvert$ 与 $\sum_k\mathrm{Cut}(A,V_k)/\mathrm{vol}(V_k)$。小簇受大惩罚 ⇒ 平衡划分；两种归一化的区别见 §14 第 1 条。

F3 — 式 (4.6)(4.7)(4.8)(4.9)（迹形式）：$H,N$ 归一化指示矩阵；$\mathrm{RatioCut}=\mathrm{Tr}(H^{T}LH)$、$\mathrm{NCut}=\mathrm{Tr}(U^{T}\mathcal LU)$。松弛保 $H^{T}H=I_K$ 弃指示结构 ⇒ Prop 4.2 的特征向量解。证明。

F4 — 式 (4.10)(4.11)（k-means 与近似）：$\min_{Z,X}\lVert ZX-V\rVert_F^2$，NP-hard 但有 $(1+\epsilon)$ 多项式近似（Kumar et al., 2004）。Algorithm 5 的 Clustering Step；Lemma 4.11 的"近似比"就是这里的 $1+\epsilon$。

F5 — 式 (4.12)–(4.16)（SDP 路线）：总割 $\sum_k\mathrm{Cut}(A,V_k)$ ⇔ $\max\mathrm{Tr}(X^{T}AX)$（补证）⇔ $Y=XX^{T}$ 语言下的 $\max\langle A,Y\rangle$（约束 $Y\in\{0,1\}^{n\times n}$、$Y\succeq0$、秩 $K$、$Y_{ii}=1$、$Y1_n=\frac nK1_n$）⇒ SDP 松弛 (4.16)（丢 0/1 与秩约束，$Y_{ii}\le1$）。

F6 — 式 (4.17)（模块度，本章的心脏）：$\mathcal M(z)=\frac{1}{2|E|}\sum_{i,j}\big(A_{ij}-\frac{d_id_j}{2|E|}\big)\mathbf 1(z_i=z_j)$。配套：$e_{k\ell},m_k$ 定义、$\mathcal M=\sum_k(e_{kk}-m_k^2)$（Lemma 4.3）、合并增益 $\Delta\mathcal M=2(e_{k_1k_2}-m_{k_1}m_{k_2})$（Lemma 4.4）、值域 $[-\frac12,1]$（§11 补证）。

F7 — 式 (4.18)（边际似然）：$\mathbb P(A|z)=\int\mathbb P(A|z,\omega,\theta)\mathbb P(\omega|z)\mathbb P(\theta|z)\,\mathrm d\omega\mathrm d\theta$，$\omega_{k\ell}$ 取均值 $\bar\omega=2|E|/n^2$ 的指数先验（最大熵）、$\theta$ 取归一化约束 $\sum_i\theta_i\mathbf 1(z_i=k)=n_k$ 的均匀先验；配先验 $\mathbb P(z)=\frac{\prod_kn_k!}{n!}\cdot\binom{n-1}{K-1}^{-1}\cdot\frac1n$（三层：块数 / 块大小 / 具体划分，不对 $K$ 与块大小做任何倾向）。用途：4.3.2 的后验目标与 MCMC 的接受比（证据 $\mathbb P(A)$ 约掉）。

F8 — 式 (4.19)(4.20)(4.21)（MAP 与正则化模块度）：Poisson DC-SBM $A_{ij}\sim\mathcal P(\theta_i\theta_j\omega_{\mathrm{in}/\mathrm{out}})$；$\hat z^{\mathrm{MAP}}=\operatorname{argmax}\mathbb P(z|A)$（式 (4.20)）= $\mathcal M_\gamma$ 最大化（Prop 4.4），$\mathcal M_\gamma(z)=\sum_{i,j}(A_{ij}-\gamma P_{ij})$（式 (4.21)，Reichardt & Bornholdt 2006）。

F9 — 式 (4.22)（广义特征问题）：$Bx=\lambda Dx$，$B=A-\gamma dd^{T}/(2|E|)$，约束 $x^{T}Dx=2|E|$（校勘：OCR 丢失该约束行）；排除 $x=1_n$（$\lambda=1-\gamma$ 的"不划分"解与 Perron 最大根）后取第二大 $\lambda$，换元得 $\mathcal Ly=(1-\lambda)y$。完整推导。

F10 — 式 (4.23)–(4.26)（非二元 SBM 与恢复分级）：$\mathbb P(A|z)=\prod_{i<j}f_{z_iz_j}(a_{ij})$（相互作用空间 $\mathcal S$，$f_{\mathrm{in}}/f_{\mathrm{out}}$）；$d^{*}_{\mathrm{Ham}}(\hat z,z)=\min_{\tau\in S_K}\sum_i\mathbf 1(\tau(\hat z_i)\neq z_i)$（式 (4.25)）；exact ⇔ $\mathbb E d^{*}\to0$（式 (4.26)），almost exact ⇔ $n^{-1}\mathbb E d^{*}\to0$。

F11 — 式 (4.27)–(4.29)（阈值与一致性证明的定量件）：$D_{1/2}(\mathrm{Ber}(p_{\mathrm{in}}),\mathrm{Ber}(p_{\mathrm{out}}))=(\sqrt{p_{\mathrm{in}}}-\sqrt{p_{\mathrm{out}}})^2+O(p_{\mathrm{in}}p_{\mathrm{out}})$（式 (4.27)，Taylor 展开；Example 4.1 的 $n\rho_n\gg1$ 与 Example 4.2 的 $(\sqrt a-\sqrt b)^2>K$ 由此来）；式 (4.28) 坏集界 $\sum_k\lvert\mathcal B_k\rvert\le\frac4{\delta^2}(2+\epsilon)^2\lVert V-\bar V\rVert_F^2$（Lemma 4.11）；式 (4.29) 扰动链 $\lVert\bar VQ-V\rVert_F\le\frac{2\sqrt{2K}}{\gamma_n}C\sqrt{\bar d_n}$（Thm 4.8）。

16. Further Notes 导读

本书无习题；章尾 Further Notes（印刷页 106–107）共 4 段，按"读什么、为什么读、与后续章的关系"解读。

第 1 段：本章方法的补充读物与缺陷文献——Von Luxburg (2007) 是谱聚类的标准综述：本章 §4.1 只给了"割松弛"一条推导线，该综述补齐随机游走、扰动论等其它视角与大量实现细节，想真正用谱聚类必读；Blondel et al. (2008) 与 Good et al. (2010) 是 Louvain 原文与其性能/局限分析，Jamonnak et al. (2015) 给了一个 Reddit 内容推荐的应用实例。两条警告文献尤其要带走：Traag et al. (2019) 发现 Louvain 可能输出内部不连通的社区并提出 Leiden 算法修正（本章 Table 4.4 的漂亮数字不含这类结构缺陷）；Fortunato & Barthelemy (2007) 的分辨率极限——模块度最大化有内在尺度，小于该尺度的社区会被强行合并，这是 §4.2 所有方法（不限于 Louvain）的通病，与正文"Louvain 倾向劈开真值社区"看似相反、实则互补（分辨率极限说的是另一方向的错）。Zhang & Peixoto (2020) 则从统计上泼冷水：模块度最大化不严格等价于似然最大化——读 Prop 4.4 时别把"≈"当"="，正文末句"the relevance of this equivalence is rather limited"与此呼应。

第 2 段：SBM 上的一致性理论——Lei & Rinaldo (2015) 是本节 Lemma 4.11 的出处，也是"谱方法 + 扰动 + k-means 误差"证明范式的奠基文献，吃透 Thm 4.8 的证明后想进阶就读它；Abbe et al. (2020) 把谱方法一致性推到更一般的恢复保证；Chen et al. (2021) 是谱方法各应用方向的近期综述。谱方法不是唯一达到一致的算法：SDP 路线（Hajek et al., 2016a,b；Guédon & Vershynin, 2016；Amini et al., 2018；Fei & Chen, 2019）——即本章 §4.1.3 那条线——在多个 SBM regime 达到与信息论阈值匹配的恢复，适合与 F5 公式卡对照。GBM 上的社区检测（Galhotra et al., 2018；Sankararaman & Baccelli, 2018；Avrachenkov et al., 2021a）回应了 §4.1.4 的几何失效——其中 2021a 正是"看高阶特征向量"方案的来源。

第 3 段：本章未展开的其它方法——belief propagation（Moore, 2017；Decelle et al., 2011）：稀疏 SBM 上接近信息论最优的推断算法，也是 Remark 4.4 所指 detection regime（KS 阈值）的核心工具，本书后续不展开但对理解"稀疏极限"很重要；博弈论方法（Avrachenkov et al., 2018a；Moscato et al., 2019）与 map equation（Rosvall & Bergstrom, 2008/2009）是两条非谱非模块度路线；非回溯矩阵（Krzakala et al., 2013）与 Bethe-Hessian（Saade et al., 2014）是"换矩阵"的谱方法，专治稀疏区的悬垂树式失效（与 §4.1.4/Thm 4.9 的正则化互补）；Fortunato (2010) 是社区检测问题的大综述，适合作为本章之后的全景读物。

第 4 段：本书未覆盖的开放问题——社区个数估计——Le & Levina (2015)、Bickel & Sarkar (2016)、Lei (2016)、Saldana et al. (2017)、Hu et al. (2020)。本章谱方法需预设 $K$（Algorithm 5 的输入），Louvain/贝叶斯虽不定 $K$ 但各有倾向（劈小社区 / 后验收缩）；§4.3 的 $P(K|A)$（图 4.12(a)）是本书给出的部分答案，正式假设检验路线在这批文献中。与后续章的关系：Ch5/Ch6 的推断仍以 $K$ 已知或可估为前提，这是阅读它们时应保持的警醒。

17. 学习检查表

学完本章后自查：

[ ] 能复述：三种社区定义（节点相似度 / 局部密度 / 全局模块度）与三条方法线（割、模块度、贝叶斯）的对应；每条线的 NP-hard 出处与近似方案。
[ ] 能复述：谱聚类的完整管线（矩阵选择 → 前 $K$ 特征向量 → 行嵌入 → $k$-means），以及 $L$ / $\mathcal L$ / $\mathcal L_\tau$ 三个矩阵各自的适应症与失效模式（悬垂树 vs 几何劫持）。
[ ] 能证明：$\mathrm{Cut}=\frac14z^{T}Lz$（Prop 4.1，含对原书因子笔误的辨析）、松弛解 $=\nu_2$（Lemma 4.1）、$\mathcal M=\sum_k(e_{kk}-m_k^2)$（Lemma 4.3）与合并增益公式（Lemma 4.4）。
[ ] 能证明：$-1\le\mathcal M\le1$ 与 $\mathcal M\ge-\frac12$（§11 补证），并给出等号情形的构造。
[ ] 能推导：Prop 4.4 的对数似然展开（$\omega_{ij}$ 两值改写 → 拆项 → 正则化模块度），并说明该等价的局限（$\gamma$ 依赖未知参数；Further Notes 的 Zhang & Peixoto 警告）。
[ ] 能推导：§4.4.2 全链（$z^{T}Bz$ → $Bx=\lambda Dx$ → 两次排除 → $\mathcal Ly=(1-\lambda)y$），说出两次排除各自排掉了什么。
[ ] 能解释：Thm 4.6 两条阈值（$I\gg n^{-1}$ / $I\ge(1+\Omega(1))K\log n/n$）的含义与直觉，并用式 (4.27) 推出二元阈值 $(\sqrt a-\sqrt b)^2>K$；说明"强一致严格强于连通"（Remark 4.6 + 脚注 6）。
[ ] 能重构：Thm 4.8 的证明链：均值场 $U=ZX$（Lemma 4.7）→ 浓度（Thm 4.9 的角色）→ Davis–Kahan（Lemma 4.10 的角色）→ $k$-means 界（Lemma 4.11 的 $\mathcal B_k$ 论证）→ 收尾常数；指出哪两环原书不证。
[ ] 能判别：给定一个实验现象（高 $\mathcal M$ / 大割 / 特征向量局部化 / 真值 NCut 非最小），判断它属于哪种失效模式、对应的修复（贝叶斯后验 / 正则化 / 高阶特征向量 / 接受该方法的边界）。
[ ] 能定位：karate club 问题在图 4.8/4.12 中的两种回答；Louvain 劈开真值社区（Table 4.4 的 $\hat K$）与分辨率极限（Fortunato & Barthelemy）是两个不同方向的现象。

18. 后续衔接

第 5 章 Graph-based Semi-supervised Learning：本章的生成模型推断框架（DC-SBM 似然、MAP、式 (4.19)(4.20)）在已知部分节点标签时继续——半监督学习把"全部未知"的社区检测升级为"部分已知"的标签传播；Prop 4.4 的似然代数是直接工具。
第 6 章 Temporal Networks：社区检测向时序网络扩展——本章的静态划分（含 karate club 这类一次性快照）在那里获得时间维度；Ch1 高中互动数据集的"按时间恢复班级"问题在本章方法 + 时序模型的交集中回答。
第 3 章 Centrality Indices（回看）：章首"用节点相似度定义社区"一条依赖 Personalized PageRank / hitting time 类指标；"谱"一词两章用法不同（聚类用 $\mathcal L$ 小特征端、中心性用随机游走不变分布），术语表已分别立目，交叉阅读时注意。
第 2 章（回看）与附录 A：SBM/DC-SBM/Poisson 版（式 (2.7)(2.8)）是本章生成模型仓库；Thm 2.2/Lemma 2.4 在 Remark 4.6 与脚注 6 中复用；Prop A.10/A.15 与 Thm A.13（Courant–Fischer）是 §4.1 全部谱论证的附录支点，附录落盘后 prop-4-2-positioning 应回链。
第 7 章 Sampling：本章的基准数据集与估计问题（如社区比例的估计）在抽样章从"拿不到全网"的角度重审。
术语表维护：本章译文落盘后，术语表中第 4 章条目（割、谱聚类、模块度等 12 条）的"首次系统引入"占位锚点需回链到译文实际小节（由 glossary 工人执行）。