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

证明目标：设 $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 等价性正确，本证明按修正版书写。

证明目标：$\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）。∎

证明目标：(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 的输入形状。∎

证明目标：$\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 值域补证（$e_{kk}\le m_k$ 是关键观察）的共同起点。∎

证明目标：$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}$（实际跨边超过零模型期望）时合并有利。∎

源文断点：原书声称 $$\Delta\mathcal M=\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].$$ 这不是“只剩 $a,b$ 两个社区”能够推出的式子：它漏掉了社区 $a$ 的新贡献和社区 $b$ 的旧贡献。

依赖工具：Lemma 4.3。

正确的一般恒等式：记 $F_k(z)=e_{kk}(z)-m_k(z)^2$。除 $a,b$ 外的社区贡献逐项抵消，准确地得到 $$\Delta\mathcal M=F_a(z^{\mathrm{new}})+F_b(z^{\mathrm{new}})-F_a(z^{\mathrm{old}})-F_b(z^{\mathrm{old}}).\tag{4.5-corr}$$ 这已经足以作为任何实现的安全更新式。

无自环图的显式增量式：令 $$s_i:=\frac{d_i}{2|E|},\qquad r_{ik}:=\frac1{2|E|}\sum_jA_{ij}\mathbf 1(z_j^{\mathrm{old}}=k).$$ 移动 $i:a\to b$（$a\ne b$）时， $$m_a'=m_a-s_i,\quad m_b'=m_b+s_i,\quad e_{aa}'=e_{aa}-2r_{ia},\quad e_{bb}'=e_{bb}+2r_{ib}.$$ 将它们代入 (4.5-corr)： $$ \begin{aligned} \Delta\mathcal M &=\{-2r_{ia}-[(m_a-s_i)^2-m_a^2]\}+\{2r_{ib}-[(m_b+s_i)^2-m_b^2]\}\\ &=2\big[(r_{ib}-r_{ia})+s_i(m_a-m_b)-s_i^2\big]. \end{aligned} $$

闭合检查：若 $i$ 与 $a,b$ 都没有相邻边，则 $r_{ia}=r_{ib}=0$，增量只由零模型质量变化给出。显式式是在 $a\ne b$ 的移动假设下推导的；$a=b$ 不是其代入点，而应由算法直接判为“不移动”、返回增量 0。维护 $m_a,m_b$ 与节点到各候选社区的边权和即可在邻居扫描中计算该增量。∎

校勘提示（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" 的定量理由。∎

证明目标：$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$ 的表达式不受影响。

证明目标（$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）补回。

证明目标：$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}$"），本卡按正确版本（平方展开）书写。

证明目标：$\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}$ 为最小社区规模。按可闭合的校正形式，若 $8(2+\epsilon)\dfrac{\lVert V-\bar V\rVert_F^2}{\delta^2}<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}$$

为闭合下一步，不先放松平方：由 $(a+b)^2\le2a^2+2b^2$ 与 $\lVert V-\hat V\rVert_F^2\le(1+\epsilon)\lVert V-\bar V\rVert_F^2$， $$\lVert\bar V-\hat V\rVert_F^2\le2(2+\epsilon)\lVert V-\bar V\rVert_F^2,$$ 从而得到同阶但更紧的坏集界 $$\sum_{k=1}^K\lvert\mathcal B_k\rvert\le\frac{8(2+\epsilon)}{\delta^2}\lVert V-\bar V\rVert_F^2.\tag{4.28a}$$

第 2 步：非坏集非空。由校正后的严格假设与 (4.28a)，$\sum_k\lvert\mathcal B_k\rvert<n_{\min}\le|\mathcal C_k|$ 对每个 $k$ 成立，因此每个 $\mathcal C_k\setminus\mathcal B_k$ 都非空。

第 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）：原书假设 $4(2+\epsilon)\lVert V-\bar V\rVert_F^2/\delta^2\le n_{\min}$ 不能推出随后宣称的 $\sum_k|\mathcal B_k|<n_{\min}$。直接把 (4.28) 与该假设相乘只会得到 $(2+\epsilon)n_{\min}$；简单把假设补成平方虽足够，却会无谓增加对 $\epsilon$ 的依赖。上面的 (4.28a) 给出更紧修复：把系数 4 改为 8 并使用严格不等式即可，仍保持对 $(2+\epsilon)$ 的线性依赖，因此与 Thm 4.8 的原参数阶一致。

证明目标：$(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（陈述错误，不能调用）；Lemma 4.10（Davis–Kahan，引用）；Lemma 4.7（平均场特征结构）；Lemma 4.11（近似 $k$-means 界）。

证明思路（原书项目符号 roadmap）：①$A$ 集中于 $\mathbb E A$（Thm 4.9）⇒ ②特征向量集中（Lemma 4.10）⇒ ③$k$-means 误分类少（Lemma 4.11，以 $\bar V=ZX$ 的平均场几何为基准）。

审计结论先行：原书证明的第 1 步不成立，因此下文不是对印刷版定理的无条件证明。以下仅记录一个可复用的条件性链条：假设另有一个实际算法使用的随机对称矩阵 $A'$，并已证明 $\lVert A'-\mathbb EA'\rVert_2\le C\sqrt{\bar d_n}$；还需验证 $\mathbb EA'$ 的前 $K$ 维空间具有 $ZX$ 结构、相应谱隙至少为 $\gamma_n$。在这些额外条件下，Davis–Kahan 与 Lemma 4.11 的后两步成立。原书取 $A'=A_\tau=A+\tau11^T$，但它不满足所声称的第一项保证。

设 $V$（resp. $\bar V$）为该条件性矩阵 $A'$（resp. $\mathbb EA'$）前 $K$ 个主特征向量排成的 $n\times K$ 矩阵。

第 1 步（条件性集中界 → 扰动，式 (4.29)）：把额外假设的 $\lVert A'-\mathbb EA'\rVert_2\le C\sqrt{\bar d_n}$ 代入 Lemma 4.10，存在正交 $Q\in\mathbb R^{K\times K}$： $$\lVert\bar VQ-V\rVert_F\le\frac{2\sqrt{2K}}{\gamma_n}\lVert A'-\mathbb E A'\rVert_2\le\frac{2\sqrt{2K}}{\gamma_n}C\sqrt{\bar d_n}.\tag{4.29}$$

第 2 步（平均场几何对接 Lemma 4.11）：在额外验证 $\mathbb EA'$ 的前 $K$ 维空间可写为 $\bar V=ZX$ 后，右乘正交 $Q$ 保持行间距，故对 $\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 要求 $8(2+\epsilon)\lVert V-\bar VQ\rVert_F^2/\delta^2<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}$，故充分条件为 $$8(2+\epsilon)\,8C^2K\,\frac{\bar d_n}{\gamma_n^2}<\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$，结论成立。

闭合检查：①在补充的集中界、总体空间和谱隙三项假设下，后两步确实给出误差阶 $K\bar d_n/\gamma_n^2$；②这些假设不能由印刷版 Thm 4.9 获得，故本卡不再使用“完整证明”标签；③若改用正则化拉普拉斯或度削减邻接矩阵，必须重新核对总体嵌入和算法输出，不能只替换一个矩阵名。∎

证明目标：对任何图与任何标签向量 $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.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)。∎

证明目标：$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$）。∎