第 02 章学习笔记：随机图模型

证明目标：$G\sim\mathcal G(n,(p_{ij}))$ 时，$\mathbb P(A)=\prod_{1\le i<j\le n}p_{ij}^{A_{ij}}(1-p_{ij})^{1-A_{ij}}$。

依赖工具：边采样相互独立（Definition 2.1）；$\mathrm{Ber}(p)$ 的质量函数可写成 $p^{x}(1-p)^{1-x}$（$x\in\{0,1\}$）。

证明思路：独立性拆乘积，逐边用指示函数写法统一两种取值。

完整证明：由边的独立性，$\mathbb P(A)=\prod_{i<j}\mathbb P(A_{ij})$。对每个 $(i,j)$， $$\mathbb P(A_{ij})=\begin{cases}p_{ij},&A_{ij}=1,\\1-p_{ij},&A_{ij}=0,\end{cases}$$ 而这恰好可以统一写成 $\mathbb P(A_{ij})=p_{ij}^{A_{ij}}(1-p_{ij})^{1-A_{ij}}$（$A_{ij}=1$ 时第二个因子为 $1$，$A_{ij}=0$ 时第一个因子为 $1$）。代入乘积即得结论。

闭合检查：展开指数和即 $\prod_{i<j:A_{ij}=1}p_{ij}\prod_{i<j:A_{ij}=0}(1-p_{ij})$，与逐边独立伯努利采样完全一致。∎

证明目标：$G\sim\mathcal G_{n,p}$ 时，$\mathbb P(A)=(1-p)^{\frac{n(n-1)}2}\Big(\dfrac{p}{1-p}\Big)^{|E|}=p^{|E|}(1-p)^{\frac{n(n-1)}2-|E|}$。

依赖工具：Proposition 2.1；$|E|=\sum_{i<j}A_{ij}$。

完整证明：由 Prop 2.1 并令 $p_{ij}\equiv p$， $$\mathbb P(A)=\prod_{i<j}p^{A_{ij}}(1-p)^{1-A_{ij}}=\prod_{i<j}(1-p)\Big(\frac{p}{1-p}\Big)^{A_{ij}}=(1-p)^{\frac{n(n-1)}2}\Big(\frac{p}{1-p}\Big)^{\sum_{i<j}A_{ij}},$$ 注意到 $\sum_{i<j}A_{ij}=|E|$ 即得第一种形式；提出 $p^{|E|}$ 得第二种等价形式。

闭合检查：节点对总数为 $\binom n2=\frac{n(n-1)}2$，非边数为 $\frac{n(n-1)}2-|E|$，指数核对无误。∎

端点口径：含 $p/(1-p)$ 的写法默认 $0<p<1$。在 $p=0$ 或 $p=1$ 时应使用 $p^{|E|}(1-p)^{\binom n2-|E|}$ 的原始乘积式，并按确定性空图/完全图直接解释，避免出现 $0/0$。

证明目标：$G\sim\mathcal G(n,p)$ 时任一节点度 $d_i$ 服从二项分布，平均度为 $np$（原书记法）。

依赖工具：$d_i=\sum_{j=1}^n A_{ij}$；独立伯努利变量之和为二项分布。

完整证明：固定节点 $i$。$d_i=\sum_{j\ne i}A_{ij}$（$A_{ii}=0$），其中 $\{A_{ij}:j\ne i\}$ 是 $n-1$ 个独立 $\mathrm{Ber}(p)$ 变量，故精确地 $d_i\sim\mathrm{Bin}(n-1,p)$，$\mathbb E d_i=(n-1)p$。原书按脚注 2 的记号约定写作 $\mathrm{Bin}(n,p)$ 与 $\bar d=np$——两者在 $n\to\infty$ 的渐近陈述中无差别。

闭合检查：本命题只在渐近语境（2.1.3 节）被调用，$\mathrm{Bin}(n-1,p)$ 与 $\mathrm{Bin}(n,p)$ 的差异为 $O(p)$，不影响任何后续结论；但在有限 $n$ 的精确计算（如手算小图度分布）时应使用 $n-1$。

校勘提示：原书陈述 "distributed according to $\mathrm{Bin}(n,p)$" 是记号简化；精确分布为 $\mathrm{Bin}(n-1,p)$。原书脚注 2 已声明 $\bar d_n=np_n$ 取代精确均值 $(n-1)p_n$ 的约定。∎

证明目标：$G_n\sim\mathcal G(n,p_n)$ 含至少一个孤立节点的概率满足 $$\lim_{n\to\infty}\mathbb P(\exists\ \text{isolated node})=\begin{cases}0,&p_n\ge\dfrac{\log n+\omega_n}{n}\ \text{对某}\ \omega_n\to+\infty,\\\\1,&p_n\le\dfrac{\log n-\omega_n}{n}\ \text{对某}\ \omega_n\to+\infty.\end{cases}$$

依赖工具：Markov 不等式（一阶矩方法，原书 Prop A.6 / Cor A.2）；Chebyshev 不等式（二阶矩方法，原书 Prop A.7 / Cor A.5）；$\log(1-x)=-x+O(x^2)$（$x\to0$）。

证明思路：孤立点数 $I_n=\sum_i\mathbf 1(A_i)$。上阈值方向：$\mathbb E I_n\to0$ 加一阶矩方法直接收尾。下阈值方向：$\mathbb E I_n\to\infty$ 不够（期望可由小概率大数值贡献），必须算二阶矩证 $I_n$ 集中在均值附近；难点是事件 $A_1$ 与 $A_2$ 不独立——节点 1 孤立意味着边 $(1,2)$ 缺席，微弱提高节点 2 孤立的概率，方差里多出因子 $\frac{1}{1-p_n}$。

完整证明：记 $A_i$="节点 $i$ 孤立"，$\bar d_n=np_n$。单个节点孤立的概率为 $$\mathbb P(A_i)=(1-p_n)^{n-1},\qquad \mathbb E I_n=n(1-p_n)^{n-1}.$$

(i) 上阈值（$\bar d_n\ge\log n+\omega_n$）：这一方向不需要假设 $p_n\to0$。由 $1-x\le \mathrm e^{-x}$， $$\mathbb E I_n\le n\mathrm e^{-(n-1)p_n}=\exp\!\left(\log n-\Big(1-\frac1n\Big)\bar d_n\right)\le\exp\!\left(\frac{\log n+\omega_n}{n}-\omega_n\right)\longrightarrow0.$$ 最后一个指数趋于 $-\infty$，因为 $\omega_n\to\infty$。由 Markov 不等式， $$\mathbb P(\exists\ \text{isolated node})=\mathbb P(I_n\ge1)\le\mathbb E I_n\longrightarrow0.$$

(ii) 下阈值（$\bar d_n\le\log n-\omega_n$）：此时 $0\le p_n\le\log n/n\to0$，且 $np_n^2\le\log^2n/n\to0$。因此 $\log(1-p_n)=-p_n+O(p_n^2)$ 可用，并给出 $$\mathbb E I_n=\exp\big(\log n-(n-1)p_n+O(np_n^2)\big)\ge\exp\big(\omega_n+o(1)\big)\longrightarrow+\infty.$$ 仅有期望发散仍不能保证孤立点出现，因此用二阶矩方法。展开平方： $$\mathbb E I_n^2=\sum_i\sum_j\mathbb P(A_i\cap A_j)=n\,\mathbb P(A_1)+n(n-1)\,\mathbb P(A_1\cap A_2).$$ 关键计算：给定 $A_1$ 时边 $(1,2)$ 确定缺席，节点 2 只需再与 $3,\dots,n$ 这 $n-2$ 个节点无边，故 $$\mathbb P(A_1\cap A_2)=\mathbb P(A_2\mid A_1)\,\mathbb P(A_1)=(1-p_n)^{n-2}\,\mathbb P(A_1)=\frac{\mathbb P(A_1)^2}{1-p_n}.$$ 又 $(\mathbb E I_n)^2=n^2\mathbb P(A_1)^2$。合并： $$\operatorname{Var}(I_n)=n\mathbb P(A_1)+\frac{n(n-1)}{1-p_n}\mathbb P(A_1)^2-n^2\mathbb P(A_1)^2\le n\mathbb P(A_1)+n^2\mathbb P(A_1)^2\Big(\frac{1}{1-p_n}-1\Big)=\mathbb E I_n+(\mathbb E I_n)^2\frac{p_n}{1-p_n}.$$ 由二阶矩方法（Chebyshev 的推论）， $$\mathbb P(I_n=0)\le\frac{\operatorname{Var}(I_n)}{(\mathbb E I_n)^2}\le\frac{1}{\mathbb E I_n}+\frac{p_n}{1-p_n}\longrightarrow0,$$ 因为 $\mathbb E I_n\to\infty$ 且 $p_n\le(\log n)/n\to0$。即 $\mathbb P(\exists\ \text{isolated node})\to1$。

闭合检查：(i) 给出上阈值方向 $\mathbb P\to0$、(ii) 给出下阈值方向 $\mathbb P\to1$，与引理陈述的两个分支一一对应。注意整个证明只用 $\mathbb E I_n$ 的渐近与 $\frac{p_n}{1-p_n}\to0$，不需要 $p_n$ 的精确速率——这正是陈述中用任意 $\omega_n\to\infty$ 刻划"离阈值距离"的原因。∎

证明目标：$G_n\sim\mathcal G(n,p_n)$，$\bar d_n=np_n$，$\omega_n\to+\infty$。(a) $\bar d_n<\log n-\omega_n$ ⇒ $G_n$ 几乎必然不连通；(b) $\bar d_n>\log n+\omega_n$ ⇒ $G_n$ 几乎必然连通。

依赖工具：Lemma 2.4（本页证明）；Markov 不等式与并集界；Cayley 定理（$k$ 个标记顶点的树共 $k^{k-2}$ 棵，原书引 Hofstad 2016 定理 3.17）；Stirling 下界 $k!\ge k^k\mathrm e^{-k}$；$1-x\le\mathrm e^{-x}$；$f(x)=x\mathrm e^{1-x/2}$ 在 $x\ge2$ 递减。

证明思路：(a) 是 Lemma 2.4 下阈值方向的直接推论——有孤立点必不连通。(b) 是真正的工作：把"不连通"按孤立点有无分解， $$\mathbb P(G_n\ \text{不连通})\le\mathbb P(I_n\ge1)+\mathbb P(G_n\ \text{不连通且}\ I_n=0),$$ 第一项由 Lemma 2.4(i) 趋于 0。第二项中，不连通且无孤立点意味着存在大小 $2\le k\le\lfloor n/2\rfloor$ 的连通分量。直接数分量不可行（分量的概率取决于其内部边数，可从树的 $k-1$ 条到完全的 $\binom k2$ 条），于是用“与外界无边的 $k$ 顶点生成树”事件作上界：每个 $k$ 分量至少含一棵生成树，故树数 $X_k$ 可控制分量数；树的数目再由 Cayley 定理精确给定。最后用一阶矩方法对 $k$ 求和：$k=2$ 回到精确式单独估计，$k\ge3$ 用粗几何界控制尾和。

完整证明：(a) 设 $\bar d_n<\log n-\omega_n$。由 Lemma 2.4 下阈值方向，$G_n$ 几乎必然含孤立节点，故几乎必然不连通。∎(a)

(b) 设 $\bar d_n\ge\log n+\omega_n$。如上分解，$\mathbb P(I_n\ge1)\to0$（Lemma 2.4(i)）。下证第二项趋于 0。

第 1 步（树放大型并集界）：设 $X_k$ 为"与外界无边的 $k$ 顶点生成树"的棵数。$k$ 连通分量必含生成树，故 $X_k\ge$（大小为 $k$ 的分量数）；不连通且无孤立点 ⇒ 存在 $k\in\{2,\dots,\lfloor n/2\rfloor\}$ 使 $X_k\ge1$（分量不超过一半顶点，总可取到小的那一侧）。由并集界与 Markov 不等式， $$\mathbb P(G_n\ \text{不连通且}\ I_n=0)\le\sum_{k=2}^{\lfloor n/2\rfloor}\mathbb P(X_k\ge1)\le\sum_{k=2}^{\lfloor n/2\rfloor}\mathbb E X_k.\tag{2.1}$$

第 2 步（$\mathbb E X_k$ 的精确式）：选 $k$ 个顶点有 $\binom nk$ 种；其上生成树由 Cayley 定理有 $k^{k-2}$ 棵；树的 $k-1$ 条边都在的概率为 $p_n^{k-1}$；树与其余 $n-k$ 个顶点之间的 $k(n-k)$ 对全不连边的概率为 $(1-p_n)^{k(n-k)}$。各因子独立相乘： $$\mathbb E X_k=\binom nk\,k^{k-2}p_n^{k-1}(1-p_n)^{k(n-k)}.$$

第 3 步（粗几何界，$k\ge3$ 用）：由 Stirling 下界，$\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}\le\frac{n^k}{k!}\le\big(\frac{n\mathrm e}{k}\big)^k$；对 $k\le n/2$ 有 $n-k\ge n/2$，故 $(1-p_n)^{k(n-k)}\le\mathrm e^{-p_nk(n-k)}\le\mathrm e^{-k\bar d_n/2}$。于是 $$\mathbb E X_k\le\frac{n^k\mathrm e^k}{k^k}\,k^{k-2}p_n^{k-1}\mathrm e^{-k\bar d_n/2}=\frac{n\mathrm e^k}{k^2}\bar d_n^{\,k-1}\mathrm e^{-k\bar d_n/2}\le n\big(\bar d_n\mathrm e^{1-\bar d_n/2}\big)^k,$$ 末步用到 $\frac{\mathrm e}{k^2\bar d_n}\le1$（$n$ 大时 $\bar d_n\ge\log n\ge1$）。记 $f(x)=x\mathrm e^{1-x/2}$，$f'(x)=\mathrm e^{1-x/2}(1-x/2)<0$（$x>2$），故 $f$ 在 $x\ge2$ 递减；$\bar d_n\ge\log n$ 给出 $$\mathbb E X_k\le n\,q_n^k,\qquad q_n:=f(\log n)=\frac{\mathrm e\log n}{\sqrt n}\le\frac12\ \ (n\ \text{充分大}).$$ 几何级数收尾：对任意 $m\ge1$， $$\sum_{k=m}^{\lfloor n/2\rfloor}\mathbb E X_k\le n\,\frac{q_n^m}{1-q_n}\le2n\,q_n^m.$$ 取 $m=3$：$2nq_n^3=\dfrac{2\mathrm e^3\log^3n}{\sqrt n}\to0$。

第 4 步（$k=2$：回到精确式单独估计——本笔记补齐）：粗界在 $k=2$ 失效（$2nq_n^2=\frac{\mathrm e^2}2\log^2n\not\to0$），须回到精确式并保留 $(1-p_n)^{2(n-2)}$ 的全部指数。这里“单独估计”只是本笔记对证明步骤的描述，不是原书命名的术语，也不声称所得界在阶或常数上最优： $$\mathbb E X_2=\binom n2\,p_n(1-p_n)^{2(n-2)}\le\frac{n^2}2p_n\,\mathrm e^{-2p_n(n-2)}=\frac{n\bar d_n}2\,\mathrm e^{-2\bar d_n+4p_n}\le\frac{\mathrm e^4}2\,n\bar d_n\,\mathrm e^{-2\bar d_n},$$ 其中 $2\bar d_n(1-\frac2n)=2\bar d_n-4p_n\ge2\bar d_n-4$。函数 $h(d)=nd\mathrm e^{-2d}$ 在 $d\ge1$ 递减，代入 $\bar d_n\ge\log n+\omega_n$： $$\mathbb E X_2\le\frac{\mathrm e^4}2\,n(\log n+\omega_n)\,n^{-2}\mathrm e^{-2\omega_n}=\frac{\mathrm e^4}2\,\frac{(\log n+\omega_n)\mathrm e^{-2\omega_n}}{n}\longrightarrow0.$$

第 5 步（合并）：由式 (2.1)， $$\mathbb P(G_n\ \text{不连通且}\ I_n=0)\le\mathbb E X_2+\sum_{k=3}^{\lfloor n/2\rfloor}\mathbb E X_k\longrightarrow0+0=0.$$ 于是 $\mathbb P(G_n\ \text{不连通})\le\mathbb P(I_n\ge1)+\mathbb P(\text{不连通且}\ I_n=0)\to0$，即 $G_n$ 几乎必然连通。∎(b)

闭合检查：(a)(b) 分别对应引理的下、上阈值方向加生成树计数；阈值 $\log n$ 来自孤立点概率 $(1-p_n)^{n-1}\approx\mathrm e^{-\bar d_n}$ 与 $\frac1n$ 的交叉点，而"无孤立点 ⇒ 连通"的余下缺口由 $X_k$ 计数闭合。两个方向合起来说明：连通性相变本质上是"最后一个孤立点消失"的相变，对数度情形下图不连通的唯一障碍就是孤立节点。

校勘提示（对照原书文件页 35 / 印刷页 26）：①原书把第 3 步的 $q_n$ 写成 $\frac{\mathrm e\log n}{2\sqrt n}$，多出的因子 $\frac12$ 从 $f(\log n)=\frac{\mathrm e\log n}{\sqrt n}$ 推不出来，疑为笔误；该因子不影响任何收敛结论，本证明按无因子的正确版本书写。②原书称该粗界"足以显示 $\sum_{k=2}^{\lfloor n/2\rfloor}\mathbb E X_k$ 收敛到零"，但代入 $m=2$ 得 $2nq_n^2=\Theta(\log^2n)\not\to0$——粗界实际只闭合 $k\ge3$ 的尾巴，$k=2$ 必须单独处理（第 4 步，本笔记补齐；结论不变）。③原书随后一句 "Showing that $\mathbb E X_1$ goes to zero is immediate" 中的 $X_1$ 不在式 (2.1) 的求和范围（$k$ 从 2 起）；它是第 3 步界公式对 $k=1$ 的形式代入，恰等于孤立节点数期望，见 proof-check-thm-2-2-ex1。

证明目标：$t$ 步后 $|V_t|=t$、$|E_t|=t$，且式 (2.2) 给出合法概率分布。

依赖工具：每步加 1 个节点、1 条边；度与边数关系 $\sum_i d_i(t)=2|E_t|$（自环计度 2）。

完整证明：$t=1$ 时 $|V_1|=|E_1|=1$（一个节点带一个自环）；之后每步恰加 1 节点 1 边，归纳得 $|V_t|=|E_t|=t$。验证式 (2.2) 归一： $$\sum_{i=1}^{t+1}\mathbb P\big((v_{t+1},v_i)\in E_{t+1}\mid G_t\big)=\frac{1}{2t+1}+\sum_{i=1}^{t}\frac{d_i(t)}{2t+1}=\frac{1+2|E_t|}{2t+1}=\frac{1+2t}{2t+1}=1,$$ 其中第一项是新节点自环的概率，求和项用 $\sum_{i=1}^t d_i(t)=2|E_t|=2t$。各项非负且总和为 1，故为概率分布。

闭合检查：归一化恰好依赖"自环计度 2"的约定——若自环计度 1 则 $\sum d_i(t)=2t-1$，总概率少 $\frac{1}{2t+1}$。Definition 2.4 的自环约定不是随意的。∎

证明目标：令 $N_k(t)$ 为时刻 $t$ 度为 $k$ 的节点数，并令原书定义的“总度分布”$P(k,t)=\mathbb E N_k(t)/t$。对每个固定 $k\ge1$，证明 $$P(k,t)\longrightarrow p_k:=\frac{4}{k(k+1)(k+2)},\qquad p_k\sim4k^{-3}.$$

依赖工具：式 (2.2) 的连接概率；Lemma 2.5（$\sum_i d_i(t)=2t$）；条件期望；一个一阶稳定递推小引理。全程不把离散递推替换成微分方程。

证明思路：直接追踪 $N_k(t)$ 的一步增量。旧的 $k-1$ 度节点被选中会使 $N_k$ 加一，旧的 $k$ 度节点被选中会使 $N_k$ 减一；新节点若连向旧节点则度为 1，若选择自环则度为 2。对这个精确递推取期望并除以 $t$，再按 $k$ 归纳证明极限存在，最后直接解离散递推。

第 1 步：写出不丢自环项的精确主方程。 给定 $G_t$，所有度为 $k-1$ 的旧节点被选中的总概率为 $\frac{(k-1)N_{k-1}(t)}{2t+1}$；这使 $N_k$ 增加 1。所有度为 $k$ 的旧节点被选中的总概率为 $\frac{kN_k(t)}{2t+1}$；这使 $N_k$ 减少 1。新节点以概率 $\frac{2t}{2t+1}$ 连向某个旧节点并以度 1 入图，以概率 $\frac1{2t+1}$ 形成自环并以度 2 入图。因此，令 $N_0(t)=0$，有 $$\mathbb E\!\left[N_k(t+1)-N_k(t)\mid G_t\right] =\frac{(k-1)N_{k-1}(t)-kN_k(t)}{2t+1}+r_{k,t},$$ 其中 $$r_{k,t}:=\frac{2t}{2t+1}\mathbf1_{\{k=1\}}+\frac1{2t+1}\mathbf1_{\{k=2\}}.$$ 这一步也解释了原书边界条件的缺口：新节点并非必以度 1 入图；概率 $1/(2t+1)$ 的自环会使它以度 2 入图。该项趋于 0，所以不改变极限分布，但有限 $t$ 时不能删掉。

第 2 步：把计数递推改写为比例递推。 记 $a_k(t)=\mathbb E N_k(t)$、$x_k(t)=a_k(t)/t=P(k,t)$。对上式再取期望，并使用 $a_k(t)=t x_k(t)$，得到 $$x_k(t+1)-x_k(t)=\frac1{t+1}\left[r_{k,t}+\frac{t(k-1)}{2t+1}x_{k-1}(t)-\left(1+\frac{tk}{2t+1}\right)x_k(t)\right].\tag{★}$$

这里使用一个初等稳定递推事实：若有界序列 $x_t$ 满足 $$x_{t+1}-x_t=\frac{c-dx_t+o(1)}{t+1},\qquad d>0,$$ 则 $x_t\to c/d$。证明很短：令 $y_t=x_t-c/d$，则 $y_{t+1}=(1-d/(t+1))y_t+o(1)/(t+1)$；对任意 $\varepsilon>0$，充分大时把误差夹在 $\pm\varepsilon/(t+1)$，迭代比较得到 $\limsup|y_t|\le\varepsilon/d$，再令 $\varepsilon\downarrow0$。

第 3 步：按 $k$ 归纳，证明极限存在。 对 $k=1$，式 (★) 中 $x_0(t)=0$、$r_{1,t}\to1$，故稳定递推事实给出 $$p_1:=\lim_{t\to\infty}x_1(t)=\frac{1}{1+1/2}=\frac23.$$ 假设 $x_{k-1}(t)\to p_{k-1}$。由于 $r_{k,t}\to\mathbf1_{\{k=1\}}$，再次应用稳定递推事实， $$p_k=\frac{\mathbf1_{\{k=1\}}+\frac{k-1}{2}p_{k-1}}{1+rac{k}{2}}. $$ 因此对 $k\ge2$， $$p_k=\frac{k-1}{k+2}p_{k-1}.$$ 归纳不仅算出了候选极限，也证明了原书直接假设的 $P(k,t)$ 极限确实存在。

第 4 步（正文小检查的解答）：直接解离散递推。 由 $p_1=2/3$， $$p_k=\frac23\prod_{j=2}^k\frac{j-1}{j+2}=\frac{4}{k(k+1)(k+2)}\sim4k^{-3}.$$ 它自动归一，因为 $$\sum_{k\ge1}\frac{4}{k(k+1)(k+2)}=2\sum_{k\ge1}\left(\frac1{k(k+1)}-\frac1{(k+1)(k+2)}\right)=1.$$ 故 $(p_k)_{k\ge1}$ 是概率分布，尾部指数为 3。∎

闭合检查：指数 3 来自"每步一条边"与"按度线性正比"两个假设：每条新边把总度抬高 2，度的相对增速 $\frac{k}{2t}$ 对 $k$ 线性，导致分布尾部按 $k^{-(1+2)}=k^{-3}$ 衰减。Remark 2.4 指出 Hofstad 2016 的一般模型（每步 $m$ 条边、参数 $\delta$）给出其他指数。

证明边界（Remark 2.5）：上面已经严格证明了原书明确定义的 $P(k,t)=\mathbb E N_k(t)/t$ 对每个固定 $k$ 的极限，并补回了自环边界项；没有用“差分约等于微分”的近似。若把命题进一步解释为随机经验比例 $N_k(t)/t$ 本身几乎必然收敛，则还需鞅集中等工具，超出本章先修范围；原书所引 Hofstad（2016）处理这一更强结论。原书另把纯幂律写成 $P(k)=Ck^{-3}$ 后称 $C=\sum k^{-3}$，归一方向写反；而本模型的精确离散极限并非对所有 $k$ 都等于纯粹的 $Ck^{-3}$，它是 $4/[k(k+1)(k+2)]$，只在尾部渐近为 $4k^{-3}$。

证明目标：$(z,G)\sim\mathrm{SBM}(n,\pi,P)$ 时，$\mathbb P(z)=\prod_{k=1}^K\pi_k^{|C_k^z|}$，且 $$\mathbb P(G|z)=\prod_{1\le i<j\le n}P_{z_iz_j}^{A_{ij}}(1-P_{z_iz_j})^{1-A_{ij}},\tag{2.4}$$ 把跨社区计数对称化后， $$\mathbb P(G|z)=\prod_{1\le k\le\ell\le K}P_{k\ell}^{\widetilde N_{k\ell}(1)}(1-P_{k\ell})^{\widetilde N_{k\ell}(0)}.$$ 这里 $$\widetilde N_{kk}(a)=\sum_{i<j}\mathbf1(A_{ij}=a)\mathbf1(z_i=k)\mathbf1(z_j=k),$$ 而对 $k<\ell$， $$\widetilde N_{k\ell}(a)=\sum_{i<j}\mathbf1(A_{ij}=a)\big[\mathbf1(z_i=k,z_j=\ell)+\mathbf1(z_i=\ell,z_j=k)\big].$$ 原书式 (2.5) 的 $N_{k\ell}(a)$ 只写了方括号中的第一个方向，无法覆盖所有无向节点对；正文已用校勘提示保留并说明这一源文问题。

依赖工具：标签 $z_i$ 独立同分布于 $\pi$（Definition 2.6）；给定 $z$ 时 $G$ 是 $\mathcal G(n,(P_{z_iz_j}))$ 的 Bernoulli 图 ⇒ Proposition 2.1。

完整证明：由标签独立性，$\mathbb P(z)=\prod_{i=1}^n\pi_{z_i}$；把同一 $k$ 的因子合并，$\pi_{z_i}=\pi_k$ 当 $i\in C_k^z$，故 $\mathbb P(z)=\prod_{k=1}^K\pi_k^{|C_k^z|}$。给定 $z$ 时，边 $(i,j)$ 的连边概率为 $P_{z_iz_j}$ 且各边独立，即 $G\mid z\sim\mathcal G(n,(P_{z_iz_j}))$，代入 Proposition 2.1 得 (2.4)。

现在把 (2.4) 中每个 $i<j$ 的因子按无序社区对 $\{z_i,z_j\}$ 分组。若两端都在社区 $k$，它恰贡献给 $\widetilde N_{kk}(A_{ij})$；若两端分别在不同社区 $k<\ell$，无论较小节点编号的标签是 $k$ 还是 $\ell$，方括号中恰有一个指示函数等于 1，所以它恰贡献给 $\widetilde N_{k\ell}(A_{ij})$。每个节点对被计一次且只计一次，因此连边因子 $P_{k\ell}$ 的指数为 $\widetilde N_{k\ell}(1)$，非边因子 $1-P_{k\ell}$ 的指数为 $\widetilde N_{k\ell}(0)$，得到修正后的 (2.5)。

闭合检查：对每个 $k<\ell$，$\widetilde N_{k\ell}(0)+\widetilde N_{k\ell}(1)=|C_k^z||C_\ell^z|$；对 $k=\ell$，两者之和为 $\binom{|C_k^z|}{2}$。总和再等于 $\binom n2$，证明没有漏边或重计。修正后的 (2.5) 表明给定 $z$ 后，这些块间计数是 $G$ 的充分统计量。∎

证明目标：同质 SBM（$P_{z_iz_j}=p_{\mathrm{in}}$ 若 $z_i=z_j$，否则 $p_{\mathrm{out}}$）下， $$\mathbb P(G|z)=\Big(\frac{p_{\mathrm{in}}}{1-p_{\mathrm{in}}}\Big)^{|E|}(1-p_{\mathrm{in}})^{\frac{n(n-1)}2}\Big(\frac{1-p_{\mathrm{out}}}{1-p_{\mathrm{in}}}\Big)^{\sum_{k<\ell}|C_k^z|\cdot|C_\ell^z|}\Big(\frac{p_{\mathrm{out}}}{1-p_{\mathrm{out}}}\cdot\frac{1-p_{\mathrm{in}}}{p_{\mathrm{in}}}\Big)^{N_{\mathrm{out}}^z},$$ 其中 $N_{\mathrm{out}}^z=\sum_{i<j}\mathbf 1(A_{ij}=1)\mathbf 1(z_i\ne z_j)$ 为跨社区边数。

依赖工具：上一卡修正后的式 (2.5)；$\widetilde N_{k\ell}(0)+\widetilde N_{k\ell}(1)=\begin{cases}|C_k^z|\cdot|C_\ell^z|,&k\ne\ell,\\\\\binom{|C_k^z|}2,&k=\ell;\end{cases}$；恒等式 $\sum_k\binom{|C_k^z|}2+\sum_{k<\ell}|C_k^z||C_\ell^z|=\binom n2$；$\sum_k \widetilde N_{kk}(1)=|E|-N_{\mathrm{out}}^z$。

完整证明：由修正后的 (2.5)，把 $\widetilde N_{k\ell}(0)=$（该社区对的节点对总数）$-\widetilde N_{k\ell}(1)$ 拆开并代入 $p_{\mathrm{in}}/p_{\mathrm{out}}$： $$\mathbb P(G|z)=\prod_{k}(1-p_{\mathrm{in}})^{\binom{|C_k^z|}2}\prod_{k<\ell}(1-p_{\mathrm{out}})^{|C_k^z||C_\ell^z|}\times\Big(\frac{p_{\mathrm{in}}}{1-p_{\mathrm{in}}}\Big)^{\sum_k \widetilde N_{kk}(1)}\Big(\frac{p_{\mathrm{out}}}{1-p_{\mathrm{out}}}\Big)^{\sum_{k<\ell}\widetilde N_{k\ell}(1)}.$$ 对底数部分提出公共因子 $(1-p_{\mathrm{in}})^{\binom n2}$：由上面恒等式，$\sum_k\binom{|C_k^z|}2=\binom n2-\sum_{k<\ell}|C_k^z||C_\ell^z|$，故 $$\prod_{k}(1-p_{\mathrm{in}})^{\binom{|C_k^z|}2}\prod_{k<\ell}(1-p_{\mathrm{out}})^{|C_k^z||C_\ell^z|}=(1-p_{\mathrm{in}})^{\binom n2}\Big(\frac{1-p_{\mathrm{out}}}{1-p_{\mathrm{in}}}\Big)^{\sum_{k<\ell}|C_k^z||C_\ell^z|}.$$ 对几率部分：$\sum_k \widetilde N_{kk}(1)=|E|-N_{\mathrm{out}}^z$，$\sum_{k<\ell}\widetilde N_{k\ell}(1)=N_{\mathrm{out}}^z$，故 $$\Big(\frac{p_{\mathrm{in}}}{1-p_{\mathrm{in}}}\Big)^{|E|-N_{\mathrm{out}}^z}\Big(\frac{p_{\mathrm{out}}}{1-p_{\mathrm{out}}}\Big)^{N_{\mathrm{out}}^z}=\Big(\frac{p_{\mathrm{in}}}{1-p_{\mathrm{in}}}\Big)^{|E|}\Big(\frac{p_{\mathrm{out}}}{1-p_{\mathrm{out}}}\cdot\frac{1-p_{\mathrm{in}}}{p_{\mathrm{in}}}\Big)^{N_{\mathrm{out}}^z}.$$ 两式相乘即命题陈述。

闭合检查：特例核对——$p_{\mathrm{in}}=p_{\mathrm{out}}=p$ 时退化为 Corollary 2.1 的 $\mathbb P(A)=(1-p)^{\binom n2}\big(\frac{p}{1-p}\big)^{|E|}$（此时含 $|C_k^z|$ 与 $N_{\mathrm{out}}^z$ 的两个因子都变成 1），代数自洽。该式说明：给定 $z$ 后同质 SBM 的似然只依赖 $|E|$、$N_{\mathrm{out}}^z$ 与社区大小——这是 Ch4 modularity 类目标函数的源头形状。∎

证明目标：同质 SBM、标签均匀（$\pi=(\frac1K,\dots,\frac1K)$）时，任一节点的期望度为 $$\bar d=\Big(\frac nK-1\Big)p_{\mathrm{in}}+n\frac{K-1}K\,p_{\mathrm{out}}.$$

依赖工具：$d_i=\sum_{j\ne i}A_{ij}$；期望线性性（不需要独立性）；给定 $z$ 时 $A_{ij}\sim\mathrm{Ber}(P_{z_iz_j})$。

证明思路：原书证明仅一句 "It is similar to the proof of Proposition 2.2. A given node has $\frac nK-1$ potential neighbors in its community, and $\frac nK(K-1)$ in the other communities."——即按"社区大小恰为期望值 $n/K$"的图景数潜在邻居，再乘各自连边概率。补全如下，并给出严格的无条件版本对照。

完整证明（补全；详见 proof-check-prop-2-6）：固定节点 $i$，设 $z_i=k$。按原书的期望图景，社区 $k$ 内除 $i$ 外有 $\frac nK-1$ 个潜在邻居，每个与 $i$ 连边概率 $p_{\mathrm{in}}$；其余 $K-1$ 个社区共 $n\frac{K-1}K$ 个潜在邻居，每个连边概率 $p_{\mathrm{out}}$。由期望线性性， $$\mathbb E d_i=\Big(\frac nK-1\Big)p_{\mathrm{in}}+n\frac{K-1}K\,p_{\mathrm{out}}.$$

严格对照（笔记补充）：不做"社区大小恰好 $n/K$"的假设，直接对随机标签取期望。给定 $z_i=k$，其余每个节点 $j$ 独立地以 $\frac1K$ 概率落在社区 $k$（连边概率 $p_{\mathrm{in}}$）、以 $\frac{K-1}K$ 概率落在外部（连边概率 $p_{\mathrm{out}}$），故 $$\mathbb E d_i=(n-1)\Big(\frac1K p_{\mathrm{in}}+\frac{K-1}K p_{\mathrm{out}}\Big)=\Big(\frac{n-1}K\Big)p_{\mathrm{in}}+\frac{(n-1)(K-1)}K p_{\mathrm{out}}.$$ 与原书公式相差 $O(p_{\mathrm{in}}+p_{\mathrm{out}})$（原书把 $(n-1)/K$ 写成 $n/K-1$、把 $(n-1)(K-1)/K$ 写成 $n(K-1)/K$），稀疏情形下渐近一致。

闭合检查：$K=1$ 时退化为 ER 的 $(n-1)p$（精确版）或 $(n-1)p_{\mathrm{in}}$（原书版取 $\frac nK-1=n-1$），一致；$p_{\mathrm{out}}=0$ 时期望度为同社区邻居数乘 $p_{\mathrm{in}}$，合理。∎

证明目标：区分原书公式与本章无自环约定下的精确公式。原书写作 $$\mathbb E d_i=\theta_i\,n\sum_{\ell=1}^K\pi_\ell P_{k\ell},$$ 而在 $A_{ii}=0$ 且采样 $z$ 后满足精确归一化 $\sum_{j:z_j=\ell}\theta_j=n\pi_\ell$ 时，应为 $$\mathbb E(d_i\mid z)=\theta_i\,n\sum_{\ell=1}^K\pi_\ell P_{k\ell}-\theta_i^2P_{kk}.$$

依赖工具：无自环时 $d_i=\sum_{j\ne i}A_{ij}$；给定 $z$ 时 $A_{ij}\sim\mathrm{Ber}(\theta_i\theta_jP_{z_iz_j})$（$i\ne j$，且假设参数小于 1）；归一化 $\sum_j\theta_j\mathbf 1(z_j=\ell)=n\pi_\ell$。

完整证明：给定 $z$， $$\begin{aligned} \mathbb E(d_i\mid z) &=\sum_{j\ne i}\theta_i\theta_jP_{kz_j}\\ &=\theta_i\sum_{\ell=1}^K P_{k\ell}\sum_{\substack{j:z_j=\ell\\j\ne i}}\theta_j\\ &=\theta_i\sum_{\ell=1}^K P_{k\ell}\left(n\pi_\ell-\theta_i\mathbf1_{\{\ell=k\}}\right)\\ &=\theta_i n\sum_{\ell=1}^K\pi_\ell P_{k\ell}-\theta_i^2P_{kk}. \end{aligned}$$ 第二步按社区分组，第三步使用归一化并从社区 $k$ 的和中删去节点 $i$ 自身。若模型允许 $A_{ii}\sim\mathrm{Ber}(\theta_i^2P_{kk})$ 的自环，把 $j=i$ 项加回后才恰好得到原书公式；但本章注 2.1 明确采用 $A_{ii}=0$。

闭合检查：在固定平衡 SBM 特例 $\theta_i\equiv1$、$\pi_\ell=1/K$ 下，修正式给出 $\mathbb E d_i=n\sum_\ell\pi_\ell P_{k\ell}-P_{kk}$，即同社区少算自身这一位；对同质 SBM 正好化为 $(n/K-1)p_{\mathrm{in}}+n(K-1)p_{\mathrm{out}}/K$，与命题 2.6 的固定平衡口径一致。原书式与精确式的差值就是被误计为潜在自环的 $\theta_i^2P_{kk}$。∎

证明目标：ERGM 中，记 $A_{ij}^+$/$A_{ij}^-$ 为把边 $(i,j)$ 置 1/0 的图、$A_{ij}^c$ 为其余所有边与非边，则 $$\operatorname{logit}\mathbb P\big(A_{ij}=1\mid A_{ij}^c\big)=\theta^{T}\big(g(A_{ij}^+)-g(A_{ij}^-)\big).$$

依赖工具：ERGM 定义 $\mathbb P(A|\theta)=\exp(\theta^{T}g(A))/\kappa(\theta)$；条件概率定义。

完整证明：固定 $A_{ij}^c$ 后，$A_{ij}$ 只有 1 和 0 两个取值，故 $$\mathbb P\big(A_{ij}=1\mid A_{ij}^c\big)=\frac{\mathbb P(A_{ij}^+)}{\mathbb P(A_{ij}^+)+\mathbb P(A_{ij}^-)}=\frac{\exp\big(\theta^{T}g(A_{ij}^+)\big)}{\exp\big(\theta^{T}g(A_{ij}^+)\big)+\exp\big(\theta^{T}g(A_{ij}^-)\big)},$$ 归一化常数 $\kappa(\theta)$ 在分子分母中相同而消去。同理 $$\mathbb P\big(A_{ij}=0\mid A_{ij}^c\big)=\frac{\exp\big(\theta^{T}g(A_{ij}^-)\big)}{\exp\big(\theta^{T}g(A_{ij}^+)\big)+\exp\big(\theta^{T}g(A_{ij}^-)\big)}.$$ 两式相除取对数： $$\operatorname{logit}\mathbb P\big(A_{ij}=1\mid A_{ij}^c\big)=\log\frac{\mathbb P(A_{ij}=1\mid A_{ij}^c)}{\mathbb P(A_{ij}=0\mid A_{ij}^c)}=\theta^{T}\big(g(A_{ij}^+)-g(A_{ij}^-)\big).\qquad\blacksquare$$

闭合检查：回到 Example 2.12 核对——Bernoulli 图取 $g(A)=A_{ij}$（每边一个统计量），$g(A_{ij}^+)-g(A_{ij}^-)=1$ 作用在第 $(i,j)$ 分量，得 $\operatorname{logit}\mathbb P(A_{ij}=1)=\theta_{ij}$，与 $\theta_{ij}=\log\frac{p_{ij}}{1-p_{ij}}$ 一致。一般 ERGM 中该式把参数解释为"翻转一条边引起的统计量变化"的权重，是 ERGM logistic 回归式估计（如 MPLE）的基础。∎

任务：原书在 Theorem 2.2(b) 证明末尾写道 "Showing that $\mathbb E X_1$ goes to zero is immediate, and going back to Equation (2.1) it follows that ..."，补出这一行估计。

补全：按 $X_k$ 的定义（与外界无边的 $k$ 顶点生成树的棵数），$X_1$ 是"与所有其他节点无边的单节点树"的棵数——即孤立节点数 $I_n$。因此，由 $1-p_n\le\mathrm e^{-p_n}$ 与 $\bar d_n\ge\log n+\omega_n$， $$\begin{aligned} \mathbb E X_1=\mathbb E I_n &=n(1-p_n)^{n-1}\\ &\le\exp\!\left(\log n-\Big(1-\frac1n\Big)\bar d_n\right)\\ &\le\exp\!\left(\frac{\log n+\omega_n}{n}-\omega_n\right)\longrightarrow0. \end{aligned}$$ 这与 Lemma 2.4 情形 (i) 的收尾完全相同（见 proof-lemma-2-4），且不额外假设 $p_n\to0$；这就是 "immediate" 的含义。

两点澄清（笔记注记）：①式 (2.1) 的求和从 $k=2$ 开始，$\mathbb E X_1$ 并不在该和式中——它对应第 3 步粗界公式 $\mathbb E X_k\le nq_n^k$ 对 $k=1$ 的形式代入（$nq_n^1=\mathrm e\log n\sqrt n\not\to0$，所以粗界对 $k=1$ 也失效，必须回到精确式）；②在 $I_n=0$ 的条件下 $X_1$ 恒为 0，所以无论是否提及 $\mathbb E X_1$，主证明逻辑不受影响。该句在原书中的作用是把粗界公式的适用边界交代清楚。∎

任务：原书对 Proposition 2.6（同质均匀 SBM 的期望度）只写 "It is similar to the proof of Proposition 2.2. A given node has $\frac nK-1$ potential neighbors in its community, and $\frac nK(K-1)$ in the other communities." 补出完整推导。

补全证明：固定节点 $i$，记其社区为 $k$。度可以写成 $d_i=\sum_{j\ne i}A_{ij}$（与 Prop 2.2 相同的出发点——这就是 "similar" 所指）。取期望（线性性不要求独立）： $$\mathbb E d_i=\sum_{j\ne i}\mathbb P\big((i,j)\in E\big).$$ 在原书的期望图景下（各社区大小恰为 $n/K$）：$j$ 与 $i$ 同社区的共 $\frac nK-1$ 个，每个贡献 $p_{\mathrm{in}}$；$j$ 在其余 $K-1$ 个社区的共 $\frac nK(K-1)=n\frac{K-1}K$ 个，每个贡献 $p_{\mathrm{out}}$。合并： $$\bar d=\mathbb E d_i=\Big(\frac nK-1\Big)p_{\mathrm{in}}+n\frac{K-1}K\,p_{\mathrm{out}}.\qquad\blacksquare$$

辨析（笔记注记）：与 Prop 2.2 的类比只在"度 = 指示变量求和"这一步成立；SBM 中 $A_{ij}$ 边际同分布但不独立（共享随机标签 $z_i,z_j$），所幸期望线性性不需要独立性。若改用严格的无条件计算（不对社区大小取期望图景），得 $\mathbb E d_i=(n-1)\big(\frac{p_{\mathrm{in}}}K+\frac{(K-1)p_{\mathrm{out}}}K\big)$，与原书公式相差 $O(p_{\mathrm{in}}+p_{\mathrm{out}})$，稀疏情形下渐近一致；两种写法都在 proof-proposition-2-6 卡中给出。∎