第 02 章学习笔记：随机图模型
第 02 章学习笔记：随机图模型
配套译文：
内部译文（已落盘；术语表中的 sec-2- 小节锚点已与译文一致）。 本章是全书地基，也是全书证明系统的第一次完整亮相：42 个编号语义对象、9 个编号公式、13 处原书证明、3 个生成算法。核心矛盾只有一条——ER 模型能严格分析但不能解释真实网络的结构性质，于是本章后半部分逐级引入机制模型与结构模型，最后用 ERGM 把它们重新统一*。Theorem 2.2（连通性相变）是本章唯一"必须会证"的大定理；Theorem 2.1（巨分量相变）原书明确不证，本笔记只做定位。
1. 一句话定位
本章回答一个问题：用什么概率模型生成"像真实网络"的图，以及这些模型各自能解释、不能解释第 1 章的哪条经验共性——答案是先建立可严格分析的基线（Bernoulli 图 / ER，给出度分布与两个相变阈值），再用配置模型、优先连接、空间模型分别补上"任意度序列、幂律、边传递性"三个缺口，用 SBM 族补上"社区结构"，最后用 ERGM 把全部模型收进一个指数族框架；第 4–6 章的全部推断问题都建立在本章的生成模型之上。
2. 本章导读
本章按"基线 → 基线的极限定理 → 机制补丁 → 结构补丁 → 统一框架"五步推进：
- 章首 Notations（印刷页 17）：随机图模型 = "全体图构成的集合上的一个概率分布"；度序列 $d=(d_1,\dots,d_n)$ 与度分布的记号在此固定。这段话很短，但它是全章乃至全书的语言基础。
- 2.1.1 Definition（印刷页 18–19）：先给最一般的 Bernoulli 随机图 $\mathcal G(n,(p_{ij}))$（Definition 2.1）——每条边独立、概率可以各不相同；ER 模型 $\mathcal G(n,p)$ 只是 $p_{ij}\equiv p$ 的特例（Example 2.1）。Proposition 2.1 给出邻接矩阵的乘积似然，是全书一切似然推断的起点。Algorithm 1/2 解决"怎么采样"：稀疏时用几何分布跳过失败区间，复杂度从 $O(n^2)$ 降到 $O(|E|)$。
- 2.1.2 Degree Distribution（印刷页 20）：Proposition 2.2 给出 ER 的度分布 $\mathrm{Bin}(n,p)$；Remark 2.2 立刻指出它与真实网络的重尾度分布不符——这是本章后半部分全部新模型的动机。
- 2.1.3 Phase Transition Phenomena（印刷页 20–26）：本章理论核心。先固定两个 regime：常数度 $p_n=a/n$ 与对数度 $p_n=a\log n/n$；用 Figure 2.1–2.3 的经验观察引出两个相变——平均度 $\bar d_n=1$ 处巨分量出现（Theorem 2.1，原书不证，引 Hofstad 2016），$\bar d_n=\log n$ 处全图连通（Theorem 2.2，原书完整证明）。证明工具是一阶矩/二阶矩方法（Lemma 2.4）加生成树计数（Cayley 定理），是全书方法论密度最高的三页。
- 2.2 Other Random Graph Models（印刷页 26–34）：三个"机制补丁"——配置模型 $\mathrm{CM}_n(d)$ 拟合任意给定度序列（Definition 2.2，Algorithm 3）；优先连接用"富者愈富"的增长机制解释幂律的来源（Definition 2.3–2.4，Proposition 2.3 证出指数 3，Remark 2.5 声明证明不完全严格）；SERN（Definition 2.5）用几何距离解释边传递性，RGG 与 Waxman 是两个特例。Table 2.1 把四个模型 × 四个性质汇总成一张对照表。
- 2.3 Clustered Random Graphs: Block Models（印刷页 34–40）：补"社区结构"。SBM（Definition 2.6）是 ER 的直接推广：节点先有社区标签 $z$，连边概率取决于两端标签；随后逐级放宽——DC-SBM 加节点度校正 $\theta_i$、PABM 让人气随社区变化、SGBM 把几何与社区合并。这一节是第 4 章的生成模型仓库。
- 2.4 Exponential Random Graph Model（印刷页 40–43）：统一框架 ERGM（Definition 2.11）：$\mathbb P(A|\theta)\propto\exp(\theta^{T}g(A))$。Example 2.12 证明所有 Bernoulli 图都是 ERGM；p₁ 模型（Holland–Leinhardt）给出有向图的经典参数化（式 (2.9)）；Proposition 2.8 建立参数 $\theta$ 与条件对数几率的一般对应。
- Further Notes（印刷页 43–44）：3 段文献指引，无习题。解读见本页 §16。
3. 本页使用方式
按你在正文中最可能卡住的位置直接跳转：
- Theorem 2.2 的证明读到"spanning trees"就懵了——为什么数连通分量要数生成树？→ §10 证明卡 proof-theorem-2-2 的"证明思路"段先讲清这个放大步骤，再读完整证明。
- "Showing that $\mathbb E X_1$ goes to zero is immediate"看不出哪里 immediate → §11 proof-check-thm-2-2-ex1：一行估计，$\mathbb E X_1=\mathbb E I_n\sim\mathrm e^{-\omega_n}$。
- 原书粗几何界真的够吗？（$\sum_{k=2}\mathbb E X_k$ 代入粗界其实不收敛）→ §10 proof-theorem-2-2 的校勘提示：粗界只闭合 $k\ge 3$ 的尾巴，$k=2$ 必须单独尖估计，本笔记已补齐。
- Proposition 2.6 的证明只有一句 "similar to the proof of Proposition 2.2" → §11 proof-check-prop-2-6 给出补全证明与原书公式的精确版本辨析。
- 分不清两个 regime、两个相变、两个阈值 → §14 易混点 第 1、2 条 + §9 卡片 T1/T2：巨分量相变在常数度 regime（$\bar d=1$），连通性相变在对数度 regime（$\bar d=\log n$），不是一回事。
- SBM / DC-SBM / PABM / SGBM 四个模型谁推广谁 → §5 概念地图 第三行 + §14 第 6、7 条。
- ERGM 的 $\theta$ 和 logit 到底什么关系 → §10 proof-proposition-2-8 + §15 公式卡片 F9 区域。
- 只想知道每个模型"能解释什么、不能解释什么" → 正文 Table 2.1 + 本页 §5 地图 与 §9 卡片 T0。
4. 本章主线
| 推进层 | 要解决的问题 | 关键转折 | 后续用途 |
|---|---|---|---|
| 2.1.1 母模型与 ER | 随机图最基本的概率结构是什么 | 一切归约为独立 $\mathrm{Ber}$ 边 ⇒ 似然是乘积（Prop 2.1）；ER 只是 $p_{ij}\equiv p$ 的特例 | 全书似然推断的出发点；Algorithm 2 的稀疏采样技巧在 Ch4 模拟 SBM 时复用（Remark 2.6） |
| 2.1.2–2.1.3 度分布与相变 | ER 的宏观形态何时、怎样突变 | 两个阈值：$\bar d=1$ 巨分量（Thm 2.1 不证）、$\bar d=\log n$ 连通（Thm 2.2 全证）；矩方法 + Cayley 计数首次登场 | 相变方法论全书反复使用；Ch4 的 SBM 相变与阈值分析以此为模板 |
| 2.2 机制模型 | ER 不能解释重尾度分布与边传递性，怎么办 | 换生成机制：给定度序列（CM）、增长+富者愈富（PA）、几何邻近（SERN） | Prop 2.3 的幂律指数 3 是 PA 类模型的基准结果；RGG/Waxman 是 Ch5 图构造的对照 |
| 2.3 分块模型 | 如何给网络装上"社区" | 节点先抽标签 $z$，连边概率取决于标签对；逐级放宽 SBM→DC-SBM→PABM，几何化得 SGBM | Ch4 社区检测的全部生成模型；式 (2.4)(2.5)(2.8) 是 Ch4 似然与谱方法分析的输入 |
| 2.4 ERGM | 上述模型能否放进一个统一统计框架 | 指数族 $\mathbb P(A)\propto\mathrm e^{\theta^{T}g(A)}$；$\theta$ 与条件 logit 一一对应（Prop 2.8） | 描述性建模与指数族推断的框架；p₁ 模型连接有向网络文献 |
5. 本章学习路线 / 概念地图
因果读法：一个母模型（Bernoulli 图）生出可分析的基线（ER），基线的极限定理暴露它的三个缺口，每个缺口由一个机制模型补上，社区结构由分块模型补上，最后 ERGM 证明这些模型本来就在同一个指数族里。
① 母模型（2.1.1）
Bernoulli 图 $\mathcal G(n,(p_{ij}))$
边独立，概率可逐边不同；似然 = 乘积（Prop 2.1）
Bernoulli 图 $\mathcal G(n,(p_{ij}))$
边独立，概率可逐边不同；似然 = 乘积（Prop 2.1）
→
② ER 基线 $\mathcal G(n,p)$
度 $\sim\mathrm{Bin}(n,p)$（Prop 2.2）
可严格分析，但不重尾、无三角形、无社区
度 $\sim\mathrm{Bin}(n,p)$（Prop 2.2）
可严格分析，但不重尾、无三角形、无社区
→
③ 两个相变（2.1.3）
常数度 regime $\bar d=1$：巨分量（Thm 2.1，不证）
对数度 regime $\bar d=\log n$：连通（Thm 2.2，全证）
工具：一阶矩/二阶矩 + Cayley 生成树计数
常数度 regime $\bar d=1$：巨分量（Thm 2.1，不证）
对数度 regime $\bar d=\log n$：连通（Thm 2.2，全证）
工具：一阶矩/二阶矩 + Cayley 生成树计数
⇓ 暴露缺口
④a 配置模型 $\mathrm{CM}_n(d)$
任意给定度序列
机制：半边随机配对；代价：允许自环/重边
任意给定度序列
机制：半边随机配对；代价：允许自环/重边
④b 优先连接
幂律的来源解释
机制：增长 + 按度正比连边；Prop 2.3：指数 3
幂律的来源解释
机制：增长 + 按度正比连边；Prop 2.3：指数 3
④c SERN（RGG/Waxman）
边传递性
机制：几何邻近 ⇒ 三角形多；代价：边不再相互独立
边传递性
机制：几何邻近 ⇒ 三角形多；代价：边不再相互独立
⑤ 分块模型（2.3）
SBM → DC-SBM → PABM（人气逐级放宽）
SERN → SGBM（几何 + 社区）
全部是 ① 的特例：$p_{ij}=P_{z_iz_j}$ 型
SBM → DC-SBM → PABM（人气逐级放宽）
SERN → SGBM（几何 + 社区）
全部是 ① 的特例：$p_{ij}=P_{z_iz_j}$ 型
→
⑥ ERGM 统一（2.4）
$\mathbb P(A)\propto\mathrm e^{\theta^{T}g(A)}$
例 2.12：所有 Bernoulli 图都是 ERGM；Prop 2.8：$\theta$ ↔ 条件 logit
$\mathbb P(A)\propto\mathrm e^{\theta^{T}g(A)}$
例 2.12：所有 Bernoulli 图都是 ERGM；Prop 2.8：$\theta$ ↔ 条件 logit
→
⑦ 全书
Ch4 社区检测（SBM 族）
Ch5 图 SSL
Ch6 时序扩展
Ch4 社区检测（SBM 族）
Ch5 图 SSL
Ch6 时序扩展
6. 分层阅读路线
- 第一遍（主线，约 60 分钟）：章首 Notations → 2.1.1 全节（Definition 2.1、Prop 2.1、Example 2.1、Corollary 2.1）→ 2.1.2 Prop 2.2 + Remark 2.2 → 2.1.3 只读 Heuristic 段与两个定理的陈述（跳过证明）+ Example 2.2/2.3 → 2.2 各模型的定义段（Definition 2.2/2.4/2.5）+ Table 2.1 → 2.3.1 Definition 2.6 + Figure 2.11 → 2.4.1 Definition 2.11 + Example 2.12。目标：能默画 §5 的概念地图，说出每个模型补 ER 的哪个缺口、两个相变各自的阈值。
- 第二遍（证明精读，约 2–3 小时）：按依赖序读四组证明：① Lemma 2.4（一阶矩 + 二阶矩的范式，配 §10）；② Theorem 2.2(b)（生成树计数，配 §10 与 §11 的校勘与补全）；③ Prop 2.3（主方程求幂律，配 §10，注意 Remark 2.5 的不严格声明）；④ 似然代数组 Prop 2.4 → 2.5 → 2.6 → 2.7（配 §10 起各卡与 §11）；最后读 Prop 2.8（三行恒等式，但是 ERGM 推断的钥匙）。
- 第三遍（应用与计算）：把 Algorithm 1–3 写成代码（Algorithm 2 的几何分布技巧值得亲手实现）；复现 Figure 2.3（$n$ 取几百即可看到相变）与 Figure 2.7(b) 的 log-log 直线；用 Example 2.8/2.9 验证 PABM ⊃ DC-SBM ⊃ SBM 的嵌套；回到 Table 2.1 逐格追问"该性质在什么条件下成立"（图注明说许多性质后续章才证明）。
- 专题回看：学第 4 章 SBM 推断时回读 2.3 节与式 (2.4)(2.5)(2.8)；学相变理论（或读 Hofstad 2016）时回读 2.1.3 与 §10 定位卡片；学第 5 章图构造时回读 2.2.3 的 SERN 与 Waxman。
7. 初学者背景补充
本章是全书第一个"重概率"章，原书默认读者熟悉以下工具（原书引用见其附录 A：Proposition A.6/A.7、Corollary A.2/A.5）：
- 一阶矩方法（Markov 不等式）：对非负整值随机变量 $X$，$\mathbb P(X\ge 1)\le \mathbb E X$。用途：想证"某结构 a.s. 不存在"，只需算期望并证它趋于 0。Lemma 2.4 情形 (i) 与 Theorem 2.2(b) 的收尾都用它。
- 二阶矩方法（Chebyshev 不等式）：$\mathbb P(X=0)\le \dfrac{\operatorname{Var}(X)}{(\mathbb E X)^2}$。用途：想证"某结构 a.s. 存在"，光 $\mathbb E X\to\infty$ 不够（期望可能被小概率大数值拉高），必须证 $X$ 集中在均值附近。Lemma 2.4 情形 (ii) 是教科书级示范。
- Cayley 定理：$k$ 个标记顶点上的树恰有 $k^{k-2}$ 棵（原书引 Hofstad 2016 定理 3.17）。Theorem 2.2(b) 计数的组合引擎。
- Stirling 下界：$k!\ge k^k\mathrm e^{-k}$，由此 $\binom{n}{k}\le \big(\frac{n\mathrm e}{k}\big)^k$。配合 $1-x\le \mathrm e^{-x}$ 是本章全部指数估计的两个螺丝刀。
- 几何分布：独立 $\mathrm{Ber}(p)$ 序列中首次成功前的失败次数。Algorithm 2 用它跳过"不连边的节点对区间"，把稀疏 ER 的生成降到 $O(|E|)$。
- Poisson 近似：$n\omega\ll 1$ 时 $\mathrm{Poi}(\omega)$ 与 $\mathrm{Ber}(\omega)$ 接近；2.3.2 节用 Poisson 版 DC-SBM（式 (2.6)–(2.8)）换取似然的可分解性。Poisson 质量函数 $\mathbb P(X=k)=\mathrm e^{-\lambda}\lambda^k/k!$。
- logit 函数：$\operatorname{logit}(x)=\log\frac{x}{1-x}$，把 $(0,1)$ 的概率映到 $\mathbb R$。ERGM 的参数 $\theta$ 本质上是各统计量的 logit 系数（Example 2.12、Proposition 2.8）。
- 主方程（master equation）：用递推 $p(k,s,t+1)=\dots$ 追踪演化概率，再对时间取平稳极限——Prop 2.3 证明的核心技术，物理文献的标准做法；严格化需要控制"递推内取极限"的合法性（原书 Remark 2.5 声明未做）。
8. 核心对象与符号表
| 符号 | 含义 | 本章出处 | 在后续推导中的角色 |
|---|---|---|---|
| $\mathcal G(n,(p_{ij}))$ | Bernoulli 随机图（边独立、概率逐边不同） | Definition 2.1 | 全章母模型；SBM/DC-SBM/PABM 都是它的特例 |
| $\mathcal G(n,p)$，$\mathcal G_{n,p}$ | Erdős–Rényi 模型（$p_{ij}\equiv p$） | Example 2.1 | 全书基线；Table 2.1 第一列 |
| $A$，$A_{ij}$ | 邻接矩阵及其元素，$A_{ij}=A_{ji}\sim\mathrm{Ber}(p_{ij})$，$A_{ii}=0$ | Remark 2.1 | 一切似然表达式的载体（Prop 2.1、式 (2.4)、(2.8)） |
| $p_n$，$\bar d_n=np_n$ | ER 连边概率序列与平均度标度 | 2.1.3 Heuristic | 相变陈述的参数；原书脚注 2：精确均值为 $(n-1)p_n$，为记号简便取 $np_n$ |
| $\omega_n$ | 任意趋于 $+\infty$ 的序列 | Theorem 2.2、Lemma 2.4 | 刻划"离阈值 $\log n$ 有多远"；取 $\omega_n=\log\log n$ 得 Example 2.2 |
| $I_n$ | 孤立节点数，$\sum_i\mathbf 1(A_i)$ | Lemma 2.4 | 一阶矩/二阶矩方法的作用对象 |
| $X_k$ | 与外界无边的 $k$ 顶点生成树棵数 | Thm 2.2(b) 证明、式 (2.1) | "无孤立点的不连通"的计数上界 |
| $\mathrm{CM}_n(d)$ | 配置模型：度序列 $d$、半边（stub）随机配对 | Definition 2.2 | 拟合任意度序列；Example 2.4 随机正则图是其特例；自环约定计度 2 |
| $d_i(t)$ | 优先连接中节点 $v_i$ 在时刻 $t$ 的度 | Definition 2.4 | 连边概率 $d_i(t)/(2t+1)$ 的分子；$\sum_i d_i(t)=2t$（Lemma 2.5） |
| $p(k,s,t)$，$P(k,t)$，$P(k)$ | 节点 $v_s$ 在时刻 $t$ 度为 $k$ 的概率；全网度分布；其平稳极限 | Prop 2.3、式 (2.3) | 主方程递推的对象；$P(k)\sim Ck^{-3}$ |
| $(S,d)$，$\gamma$ | 度量空间与连通函数 $\gamma:\mathbb R^+\to[0,1]$ | Definition 2.5 | SERN 的两个输入；RGG 取示性函数、Waxman 取 $\min(1,q\mathrm e^{-\alpha x})$ |
| $z\in[K]^n$，$\pi$，$P$ | 社区标签向量、标签分布、块间连边概率矩阵 | Definition 2.6 | SBM 的三参数；$C_k^z=\{i:z_i=k\}$ 为社区集合 |
| $p_{\mathrm{in}}$，$p_{\mathrm{out}}$ | 同质 SBM 的同/异社区连边概率 | Definition 2.7 | Ch4 可检测性分析的常用参数化 |
| $N_{k\ell}(a)$，$N_{\mathrm{out}}^z$ | 社区对 $(k,\ell)$ 间的边（$a=1$）/非边（$a=0$）数；跨社区边数 | Prop 2.4/2.5 | 式 (2.5) 的充分统计量 |
| $\theta_i$ | DC-SBM 度校正参数 | Definition 2.8 | 归一化 $\sum_i\theta_i\mathbf 1(z_i=k)=n\pi_k$ 后可释为"节点相对人气"；$\theta_i\equiv1$ 退化为 SBM |
| $\omega_{k\ell}$ | Poisson 版 DC-SBM 的块间边密度 | 式 (2.6)–(2.8) | Ch4 谱/似然分析常用 Poisson 参数化 |
| $\lambda_{ik}$ | PABM 中节点 $i$ 与社区 $k$ 连边的倾向 | Definition 2.9 | $\lambda_{ik}=\sqrt{P_{k\ell}}$ 退化 SBM、$\theta_i\sqrt{P_{k\ell}}$ 退化 DC-SBM（Example 2.8/2.9） |
| $\gamma_{k\ell}$ | SGBM 中依赖社区对的连通函数 | Definition 2.10 | 常数退化 SBM（Ex 2.10）；示性函数得 GBM（Ex 2.11） |
| $\theta$，$g(A)$，$\kappa(\theta)$ | ERGM 参数、网络统计量向量、归一化常数 | Definition 2.11 | $\mathbb P(A|\theta)=\exp(\theta^{T}g(A))/\kappa(\theta)$ |
| $\rho,\mu,\alpha_i,\beta_j$；$R,M,A_{i+},A_{+j}$ | p₁ 模型的互惠力、密度、产出力、吸引力；互惠边数、总边数、出/入度 | 2.4.2、式 (2.9) | 有向图 ERGM 的经典参数化；注意 $\rho$ 是参数不是概率 $p$ |
9. 关键定理卡片
原书编号有跳号：Lemma 只有 2.4、2.5（无 2.1–2.3），Theorem 只有 2.1、2.2——清单确认这是原书编号而非 OCR 错误，本笔记保留原编号。
卡片 T0：Bernoulli 图似然（Proposition 2.1 + Corollary 2.1）
- 条件：$G\sim\mathcal G(n,(p_{ij}))$，$A$ 为其邻接矩阵；推论取 $p_{ij}\equiv p$。
- 结论：$\mathbb P(A)=\prod_{i<j}p_{ij}^{A_{ij}}(1-p_{ij})^{1-A_{ij}}$；ER 情形 $\mathbb P(A)=p^{|E|}(1-p)^{\frac{n(n-1)}2-|E|}$。
- 用途：一切"给图估参数"问题的出发点；Prop 2.4（SBM 似然）、Example 2.12（ERGM 化）都直接调用它。
- 证明入口：proof-proposition-2-1、proof-corollary-2-1（均为两行恒等式）。
卡片 T1：巨分量相变（Theorem 2.1，原书不证）
- 条件：$G\sim\mathcal G(n,p_n)$，常数度 regime $p_n=a/n$（$a$ 为常数）。
- 结论（a.s.）：(a) $a<1$ 时所有连通分量大小 $O(\log n)$；(b) $a=1$ 时最大分量 $O(n^{2/3})$；(c) $a>1$ 时存在唯一大小 $\Theta(n)$ 的分量——巨分量。
- 用途：常数度 regime 的定性图景；Figure 2.1、2.3(a) 的理论解释。
- 证明入口：原书明确不给证明（"complex and will not be presented in this book"，引 Hofstad 2016）。见本页 定位卡片——不要试图从 Thm 2.2 的证明反推它，两者工具不同（Thm 2.1 需要分支过程论证）。
卡片 T2：连通性相变（Theorem 2.2，本章主定理）
- 条件：$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$ a.s. 不连通（事实上 a.s. 有孤立节点）；(b) $\bar d_n>\log n+\omega_n$ ⇒ $G_n$ a.s. 连通。
- 用途：连通性阈值 $\log n$ 的严格化；Example 2.2（$\bar d_n=\log n+\log\log n$ 连通）、Example 2.3（$\bar d_n=a\log n$ 按 $a\gtrless1$ 分界）解释了 Figure 2.2、2.3(b)。
- 证明入口：proof-lemma-2-4（孤立节点引理）→ proof-theorem-2-2（含生成树计数与本笔记补齐的 $k=2$ 尖估计）；隐藏跳步见 proof-check-thm-2-2-ex1。
卡片 T3：ER 度分布（Proposition 2.2）
- 条件/结论：$G\sim\mathcal G(n,p)$ ⇒ $d_i\sim\mathrm{Bin}(n,p)$（精确为 $\mathrm{Bin}(n-1,p)$，见证明卡校勘），$\bar d=np$。
- 用途：与 Remark 2.2 合读——二项分布集中 ⇒ ER 无枢纽节点 ⇒ 不是真实网络的好模型；这是 2.2 节全部新模型的动机。
- 证明入口：proof-proposition-2-2。
卡片 T4：优先连接的幂律（Lemma 2.5 + Proposition 2.3）
- 条件：Definition 2.4 的优先连接模型（每步加一个节点、恰好连一条边，连向 $v_i$ 的概率见式 (2.2)）。
- 结论：Lemma 2.5：$|V_t|=|E_t|=t$，式 (2.2) 是合法概率分布；Prop 2.3：$t\to\infty$ 时度分布为指数 3 的幂律 $P(k)=Ck^{-3}$。
- 用途：幂律"从哪里来"的第一个机制性答案；指数 3 是 PA 类模型的基准（Remark 2.5：更一般模型得其他指数；证明不完全严格）。
- 证明入口：proof-lemma-2-5、proof-proposition-2-3（含精确离散解 $P(k)=\frac{4}{k(k+1)(k+2)}$ 的补充）。
卡片 T5：SBM 似然（Proposition 2.4 + 2.5）
- 条件/结论：$(z,G)\sim\mathrm{SBM}(n,\pi,P)$ ⇒ $\mathbb P(z)=\prod_k\pi_k^{|C_k^z|}$，$\mathbb P(G|z)$ 由式 (2.4)（逐边乘积）与式 (2.5)（按社区对重排，充分统计量 $N_{k\ell}(a)$）给出；同质 SBM 进一步化为只含 $|E|$ 与 $N_{\mathrm{out}}^z$ 的形式。
- 用途：Ch4 社区检测似然方法（含谱方法的分析）的输入；式 (2.5) 说明 $N_{k\ell}(a)$ 是充分统计量。
- 证明入口：proof-proposition-2-4、proof-proposition-2-5。
卡片 T6：期望度（Proposition 2.6 + 2.7）
- 结论：同质均匀 SBM 中 $\bar d=(\frac nK-1)p_{\mathrm{in}}+n\frac{K-1}Kp_{\mathrm{out}}$；同质 DC-SBM 中社区 $k$ 的节点 $i$ 有 $\mathbb E d_i=\theta_i n\sum_\ell\pi_\ell P_{k\ell}$。
- 用途：读图时把"看到的平均度"翻译回模型参数；Prop 2.7 说明 $\theta_i$ 直接按比例缩放期望度——这正是"度校正"的含义。
- 证明入口：proof-proposition-2-6（原书仅一句 "similar to"，补全见 proof-check-prop-2-6）、proof-proposition-2-7。
卡片 T7：ERGM 与 logit（Proposition 2.8）
- 条件/结论：任何 ERGM 中，固定其余所有边，$\operatorname{logit}\mathbb P(A_{ij}=1\mid A_{ij}^c)=\theta^{T}\big(g(A_{ij}^+)-g(A_{ij}^-)\big)$。
- 用途：把 ERGM 参数解释为"翻转一条边时各网络统计量变化量的加权和"；是 ERGM 估计（logistic 回归视角）与解释的基础。
- 证明入口：proof-proposition-2-8（三行恒等式，但值得逐行看懂）。
10. 关键定理完整证明
原书在本章给出 13 处证明。本模块按原书顺序全部以"证明目标 + 依赖工具 + 证明思路 + 完整证明 + 闭合检查"呈现；原书跳步（渐近等价、粗界收尾）直接并入完整证明并加校勘提示。Theorem 2.1 原书明确不证，按规范做定位卡片。
完整证明Proposition 2.1（Bernoulli 图的乘积似然）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：$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})$，与逐边独立伯努利采样完全一致。∎
完整证明Corollary 2.1（ER 图的似然）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：$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|$，指数核对无误。∎
完整证明Proposition 2.2（ER 的度分布）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：$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$ 的约定。∎
定位卡片Theorem 2.1（巨分量相变，原书不证）
**陈述**（常数度 regime $p_n=a/n$，a.s.）：(a) $a<1$：无超过 $O(\log n)$ 的连通分量；(b) $a=1$：存在一个 $O(n^{2/3})$ 的大分量；(c) $a>1$：存在唯一大小 $\Theta(n)$ 的巨分量。
**原书态度**："The proof of Theorem 2.1 is complex and will not be presented in this book. We refer the interested reader to (Hofstad, 2016)." ——这是原书级留白，**本笔记不补证**（规范：不得伪造证明）。
**外部参考**：Hofstad, *Random Graphs and Complex Networks*, Vol. 1（2016），第 4 章（分支过程方法）。该证明依赖分支过程耦合与探索过程分析，与本章 Thm 2.2 的矩方法不是同一套工具，无法用本章方法"顺手"推出。
**学到这里应带走**：①阈值位置 $\bar d=1$ 与三个区域的定性结论；②它与 Thm 2.2 的关系——巨分量（占比 $\Theta(1)$ 的分量）出现在 $\bar d$ 为**常数**量级，全图连通要等到 $\bar d$ 为 $\log n$ 量级，两个相变之间隔着整个"$O(1)$ 到 $\Theta(\log n)$ 平均度"地带，其中巨分量存在但仍有孤立点；③Figure 2.3(a) 是该定理的数值证据。
完整证明Lemma 2.4（孤立节点的有无）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：$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}.$$
由 $\log(1-p_n)=-p_n+O(p_n^2)$（两情形下均有 $p_n=O(\log n/n)\to0$），
$$\mathbb P(A_i)=\exp\big((n-1)\log(1-p_n)\big)=\exp\big(-(n-1)p_n+O(np_n^2)\big)=\mathrm e^{-\bar d_n(1+o(1))},$$
其中 $np_n^2=\bar d_n^2/n\to0$。于是
$$\mathbb E I_n=n\,\mathbb P(A_1)=n\,\mathrm e^{-\bar d_n(1+o(1))}.$$
**(i) 上阈值**（$\bar d_n\ge\log n+\omega_n$）：$\mathbb E I_n\le n\,\mathrm e^{-(\log n+\omega_n)(1+o(1))}=\mathrm e^{-\omega_n(1+o(1))}\to0$。由 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$）：同样代入得 $\mathbb E I_n\ge\mathrm e^{\omega_n(1+o(1))}\to+\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$ 刻划"离阈值距离"的原因。∎
完整证明Theorem 2.2（连通性相变，本章主定理）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：$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$ a.s. 不连通；(b) $\bar d_n>\log n+\omega_n$ ⇒ $G_n$ a.s. 连通。
**依赖工具**：Lemma 2.4（[本页证明](#proof-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.s. 含孤立节点，故 a.s. 不连通。∎(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$ a.s. 连通。∎(b)
**闭合检查**：(a)(b) 分别对应引理的下、上阈值方向加生成树计数；阈值 $\log n$ 来自孤立点概率 $(1-p_n)^{n-1}\approx\mathrm e^{-\bar d_n}$ 与 $\frac1n$ 的交叉点，而"无孤立点 ⇒ 连通"的余下缺口由 $X_k$ 计数闭合。两个方向合起来说明：**连通性相变本质上是"最后一个孤立点消失"的相变**，对数度 regime 下图不连通的唯一障碍就是孤立节点。
> 校勘提示（对照原书文件页 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](#proof-check-thm-2-2-ex1)。
完整证明Lemma 2.5（优先连接的规模与式 (2.2) 的合法性）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：$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 的自环约定不是随意的。∎
状态：完整证明已按当前笔记标准给出闭合推导。
完整证明Proposition 2.3（优先连接的幂律度分布，指数 3）
**证明目标**：$t\to+\infty$ 时，优先连接模型的稳态度分布满足 $P(k)=Ck^{-3}$ 型幂律，指数为 3。
**依赖工具**：式 (2.2) 的连接概率；Lemma 2.5（$\sum_i d_i(t)=2t$）；差分方程取平稳极限；一阶线性常微分方程求解。
**证明思路**：对"节点 $v_s$ 在时刻 $t$ 度为 $k$"的概率 $p(k,s,t)$ 写时间递推（主方程）：度从 $k-1$ 涨上来，或停在 $k$。对 $s$ 平均得全网度分布 $P(k,t)$ 的递推，令 $t\to\infty$ 取平稳，差分方程化为微分方程，解出 $Ck^{-3}$。
**完整证明**：固定 $s\in\{1,\dots,t\}$。在时刻 $t+1$，新节点 $v_{t+1}$ 以概率 $\frac{d_s(t)}{2t+1}$ 连向 $v_s$（式 (2.2)），故 $v_s$ 度从 $k-1$ 升至 $k$ 的概率为 $\frac{k-1}{2t+1}$、保持 $k$ 的概率为 $1-\frac{k}{2t+1}$。于是得主方程
$$p(k,s,t+1)=\frac{k-1}{2t+1}\,p(k-1,s,t)+\Big(1-\frac{k}{2t+1}\Big)p(k,s,t),\tag{2.3}$$
初值 $p(k,1,1)=\delta_{k,1}$，边界 $p(k,t,t)=\delta_{k,1}$（新节点入图时度为 1）。定义全网度分布 $P(k,t)=\frac1t\sum_{s=1}^t p(k,s,t)$。将 (2.3) 对 $s=1,\dots,t$ 求和并加上新节点 $s=t+1$ 的贡献 $p(k,t+1,t+1)=\delta_{k,1}$，得
$$(t+1)P(k,t+1)=\frac{k-1}{2t+1}\,tP(k-1,t)+\Big(1-\frac{k}{2t+1}\Big)tP(k,t)+\delta_{k,1},$$
即
$$(t+1)P(k,t+1)-tP(k,t)=\frac{t}{2t+1}\Big((k-1)P(k-1,t)-kP(k,t)\Big)+\delta_{k,1}.$$
令 $t\to\infty$ 并设 $P(k,t)\to P(k)$：左端 $(t+1)P(k,t+1)-tP(k,t)=t\big(P(k,t+1)-P(k,t)\big)+P(k,t+1)\to P(k)$（平稳时差分为 0），$\frac{t}{2t+1}\to\frac12$，得平稳方程
$$P(k)+\frac12\Big(kP(k)-(k-1)P(k-1)\Big)=\delta_{k,1}.$$
把 $kP(k)-(k-1)P(k-1)$ 看作 $\frac{\mathrm d}{\mathrm dk}\big(kP(k)\big)$ 的离散版本，对应微分方程
$$P(k)+\frac12\frac{\mathrm d\,\big(kP(k)\big)}{\mathrm dk}=0\ \Longleftrightarrow\ \frac32P(k)+\frac{k}{2}P'(k)=0\ \Longleftrightarrow\ \frac{P'(k)}{P(k)}=-\frac3k,$$
解为
$$P(k)=Ck^{-3},$$
即幂律指数为 3。∎
**笔记补充（非原书内容）：平稳方程的精确离散解。** 不解微分方程而直接解递推：$k=1$ 时 $P(1)+\frac12P(1)=1$ 得 $P(1)=\frac23$；$k\ge2$ 时 $(k+2)P(k)=(k-1)P(k-1)$，迭代得
$$P(k)=\frac23\prod_{j=2}^k\frac{j-1}{j+2}=\frac23\cdot\frac{2!\,(k-1)!}{(k+2)!/6}\cdot\frac12=\frac{4}{k(k+1)(k+2)}\sim4k^{-3}.$$
这给出渐近常数 $C=4$，且自动归一：$\sum_{k\ge1}\frac{4}{k(k+1)(k+2)}=2\sum_{k\ge1}\Big(\frac{1}{k(k+1)}-\frac{1}{(k+1)(k+2)}\Big)=2\cdot\frac12=1$（裂项望远镜）。
**闭合检查**：指数 3 来自"每步一条边"与"按度线性正比"两个假设：每条新边把总度抬高 2，度的相对增速 $\frac{k}{2t}$ 对 $k$ 线性，导致分布尾部按 $k^{-(1+2)}=k^{-3}$ 衰减。Remark 2.4 指出 Hofstad 2016 的一般模型（每步 $m$ 条边、参数 $\delta$）给出其他指数。
> 注记（Remark 2.5）：原书声明上述证明"不完全严格"——不严格之处有三：①对递推逐项取极限与求和换序未证；②平稳化 $(t+1)P(k,t+1)-tP(k,t)\to P(k)$ 预设了极限存在；③差分→微分方程是渐近近似。原书引 Hofstad 2016 为严格证明（鞅/随机游走方法），本笔记不重复。另：原书在解 $P(k)=Ck^{-3}$ 后写归一化常数 "$C=\sum_{k=1}^{\infty}k^{-3}$"，方向写反——按 $P(k)=Ck^{-3}$ 归一应取 $C=\big(\sum_{k\ge1}k^{-3}\big)^{-1}=1/\zeta(3)$；按上面的精确离散解则 $C=4$（仅渐近意义）。两处不一致均不影响"指数为 3"的结论。
完整证明Proposition 2.4（SBM 的标签分布与条件似然）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：$(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}^{N_{k\ell}(1)}(1-P_{k\ell})^{N_{k\ell}(0)},\tag{2.5}$$
其中 $N_{k\ell}(a)=\sum_{i<j}\mathbf 1(A_{ij}=a)\mathbf 1(z_i=k)\mathbf 1(z_j=\ell)$。
**依赖工具**：标签 $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) 的乘积按社区对 $(z_i,z_j)=(k,\ell)$ 重新分组：$P_{z_iz_j}$ 的指数为 $\#\{(i,j):A_{ij}=1,z_i=k,z_j=\ell\}=N_{k\ell}(1)$（$P$ 对称，$k=\ell$ 与 $k\ne\ell$ 均一致），$(1-P_{z_iz_j})$ 的指数同理为 $N_{k\ell}(0)$，得 (2.5)。
**闭合检查**：(2.5) 表明给定 $z$ 后，$\{N_{k\ell}(0),N_{k\ell}(1)\}_{k\le\ell}$ 是 $G$ 的充分统计量——Ch4 的似然类社区检测方法只需要这些块间计数。∎
完整证明Proposition 2.5（同质 SBM 的条件似然）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：同质 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)；$N_{k\ell}(0)+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 N_{kk}(1)=|E|-N_{\mathrm{out}}^z$。
**完整证明**：由 (2.5)，把 $N_{k\ell}(0)=$（对数）$-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 N_{kk}(1)}\Big(\frac{p_{\mathrm{out}}}{1-p_{\mathrm{out}}}\Big)^{\sum_{k<\ell}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 N_{kk}(1)=|E|-N_{\mathrm{out}}^z$，$\sum_{k<\ell}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 类目标函数的源头形状。∎
完整证明Proposition 2.6（同质均匀 SBM 的期望度，含原书压缩证明的补全）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：同质 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](#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$），稀疏 regime 下渐近一致。
**闭合检查**：$K=1$ 时退化为 ER 的 $(n-1)p$（精确版）或 $(n-1)p_{\mathrm{in}}$（原书版取 $\frac nK-1=n-1$），一致；$p_{\mathrm{out}}=0$ 时期望度为同社区邻居数乘 $p_{\mathrm{in}}$，合理。∎
完整证明Proposition 2.7（同质 DC-SBM 的期望度）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：同质 DC-SBM 中，社区 $k$ 的节点 $i$ 的期望度为 $\mathbb E d_i=\theta_i\,n\sum_{\ell=1}^K\pi_\ell P_{k\ell}$。
**依赖工具**：$d_i=\sum_jA_{ij}$；给定 $z$ 时 $A_{ij}\sim\mathrm{Ber}(\theta_i\theta_jP_{z_iz_j})$（假设 $\theta_i\theta_jP_{z_iz_j}<1$）；归一化 $\sum_j\theta_j\mathbf 1(z_j=\ell)=n\pi_\ell$。
**完整证明**：给定 $z$，
$$\mathbb E(d_i\mid z)=\sum_{j=1}^n\theta_i\theta_jP_{z_iz_j}=\theta_i\sum_{\ell=1}^K\Big(\sum_{j=1}^n\theta_j\mathbf 1(z_j=\ell)\Big)P_{k\ell}=\theta_i\sum_{\ell=1}^K n\pi_\ell P_{k\ell},$$
第二步按 $z_j$ 的值把求和分成 $K$ 组，第三步用归一化。该式不依赖 $z$ 的具体实现（只依赖 $z_i=k$），故无条件期望相同。
**闭合检查**：$\theta_i\equiv1$ 时退化为 $\mathbb E d_i=n\sum_\ell\pi_\ell P_{k\ell}$——即 SBM 情形；$\theta_i$ 以正比方式缩放期望度，确认"度校正参数 = 相对人气"的解释。∎
完整证明Proposition 2.8（ERGM 参数与条件 logit）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：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）的基础。∎
11. 正文隐藏验证补全
清单 §6 的扫描结论与本页处置总表：
| 清单行 | 原句（意译） | 判定 | 本页处置 |
|---|---|---|---|
| 1 | "Theorem 2.1 的证明复杂，本书不给出，见 Hofstad 2016" | 真正留白（原书级省略） | 不补证；定位卡片 |
| 2 | "Showing that $\mathbb E X_1$ goes to zero is immediate" | 小留白（一句话跳步） | proof-check-thm-2-2-ex1 |
| 3 | Prop 2.6 "similar to the proof of Proposition 2.2" | 压缩证明 | proof-check-prop-2-6（完整证明同时并入 proof-proposition-2-6） |
| 4 | Remark 2.5："上述证明不完全严格" | 原书自证不严格 | 注记，见 proof-proposition-2-3 卡内；不强制补证 |
| 5–7 | 度序列存在性警示 / Prop 2.8 "Observe that" / Figure 2.1–2.3 经验观察 | 修辞性，无留白 | 不需证明卡片；图观察由 Thm 2.1/2.2 严格化 |
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
隐藏验证补全Thm 2.2 证明中 "$\mathbb E X_1$ goes to zero is immediate"（清单 §6 第 2 行）
**任务**：原书在 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$。因此
$$\mathbb E X_1=\mathbb E I_n=n(1-p_n)^{n-1}=n\,\mathrm e^{-\bar d_n(1+o(1))}\le n\,\mathrm e^{-(\log n+\omega_n)(1+o(1))}=\mathrm e^{-\omega_n(1+o(1))}\longrightarrow0,$$
其中渐近式与 Lemma 2.4 情形 (i) 中的计算完全相同（见 [proof-lemma-2-4](#proof-lemma-2-4)），这就是 "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 的压缩证明 "similar to the proof of Proposition 2.2"（清单 §6 第 3 行）
**任务**：原书对 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}})$，稀疏 regime 下渐近一致；两种写法都在 [proof-proposition-2-6](#proof-proposition-2-6) 卡中给出。∎
12. 术语与跨章链接
本章首次系统引入、已入全书术语表的术语（点击跳转定义；术语表中的"首次系统引入"小节锚点为占位，译文落盘后回链）：
- 母模型与基线：邻接矩阵、伯努利随机图、Erdős–Rényi 随机图（Ch1 已引入直觉，本章给正式定义）
- 相变与度分布：巨分量（严格定义与存在性结论本章给出）、相变
- 机制模型：配置模型、随机正则图、优先连接（正式定义与幂律证明在本章）、主方程、空间嵌入随机网络 SERN、随机几何图、Waxman 模型
- 分块模型：聚簇随机图、随机分块模型 SBM、同质（对称）SBM、度校正 SBM、受欢迎度调整分块模型 PABM、软几何分块模型 SGBM
- 指数族：指数随机图模型 ERGM、p₁ 模型、对数几率 logit
跨章链接：
- 回看 Ch1：第 1 章笔记 §11 前瞻句 F3（ER 连通性图感）由本章 Thm 2.2 兑现、F4（PA 幂律承诺）由 Prop 2.3 兑现；Ch1 的五条共性是本章 Table 2.1 的四个性质列（连通/巨分量、小世界、幂律、边传递性）的来源。
- 前瞻 Ch4：2.3 节全部模型（SBM/DC-SBM/PABM）与式 (2.4)(2.5)(2.8) 是社区检测章的生成模型与似然输入；社区检测问题本身在 Ch1 §1.3.1 提出。
- 前瞻 Ch5：2.2.3 的 SERN 几何视角与 Ch1 的高斯核/KNN 图构造一脉相承，图半监督学习章以这类图为输入。
- 脚注 1 的史料：ER 模型 Gilbert (1959) 与 Erdős–Rényi (1959) 两个来源并行，原书脚注已说明，术语表保留人名原文。
13. 章节阅读路径
| 顺序 | 小节（印刷页） | 读法 |
|---|---|---|
| 1 | 章首 Notations（p.17） | 精读：随机图模型 = 图集合上的概率分布；度序列/度分布记号 |
| 2 | 2.1.1（p.18–19） | 精读 Definition 2.1 与 Prop 2.1；Algorithm 1/2 了解思想（几何分布跳区间），不必背伪码；脚注 1 史料 |
| 3 | 2.1.2（p.20） | 快读：Prop 2.2 一行证明 + Remark 2.2 的动机段 |
| 4 | 2.1.3 Heuristic（p.20–22） | 精读：两个 regime 的区分是全章分水岭；Figure 2.1/2.2 注意常数度 vs 对数度的 panel 归属（OCR 图注错位，以译文为准） |
| 5 | 2.1.3 Main statements（p.22–23） | 精读两定理陈述 + Example 2.2/2.3；Thm 2.1 记住"不证"即可 |
| 6 | 2.1.3 Proof of the connectivity phase transition（p.23–26） | 本章核心三页，配本页 §10 Lemma 2.4 → Thm 2.2 两卡逐段对照 |
| 7 | 2.2.1 配置模型（p.26–28） | 精读 Definition 2.2（半边配对）；Algorithm 3 看图即可；Example 2.4/2.5 |
| 8 | 2.2.2 优先连接（p.28–32） | 精读 Motivation（静态模型为何不够）+ Definition 2.4 的式 (2.2)；Prop 2.3 证明配 §10；Remark 2.5 必读 |
| 9 | 2.2.3 空间网络（p.32–34） | 精读 Definition 2.5 的统一性（RGG/Waxman 皆为特例）；末段"边不再相互独立"的讨论是理解 SERN 的关键 |
| 10 | 2.2.4 Summary（p.34） | Table 2.1 逐格对照本页 §5 地图；记住图注"许多性质后续章才证明" |
| 11 | 2.3.1–2.3.2（p.34–38） | 精读 Definition 2.6/2.7/2.8；Prop 2.4–2.7 配 §10 各卡；Poisson 版式 (2.6)–(2.8) 知道存在即可（Ch4 才真正用） |
| 12 | 2.3.3–2.3.4（p.39–40） | 快读：PABM/SGBM 只需记住嵌套关系（Example 2.8–2.11） |
| 13 | 2.4（p.40–43） | 精读 Definition 2.11 + Example 2.12；p₁ 模型四参数（$\rho,\mu,\alpha_i,\beta_j$）的语义；Prop 2.8 三行证明 |
| 14 | Further Notes（p.43–44） | 见 §16 |
14. 易混点
- 两个 regime、两个相变、两个阈值：常数度 regime $p_n=a/n$ 对应巨分量相变（Thm 2.1，阈值 $\bar d=1$）；对数度 regime $p_n=a\log n/n$ 对应连通性相变（Thm 2.2，阈值 $\bar d=\log n$）。$\bar d=1$ 时出现巨分量但图仍远不连通（孤立点大量存在）；从 $\bar d=\Theta(1)$ 到 $\bar d=\Theta(\log n)$ 之间是"有巨分量但不连通"地带。Figure 2.1（常数度）与 Figure 2.2（对数度）的 panel 归属在 OCR 中错位，以译文/本页 §13 为准。
- "有巨分量" ≠ "连通"：巨分量是占比 $\Theta(1)$ 的最大分量，允许其余节点散落在小分量与孤立点中；连通要求分量数为 1。Thm 2.2(b) 的证明正是在闭合这个差距：先杀孤立点（Lemma 2.4），再杀小分量（$X_k$ 计数）。
- $\mathbb E I_n\to\infty$ 推不出"存在孤立点"：期望可被"小概率 × 大数值"拉高。这是 Lemma 2.4 情形 (ii) 必须用二阶矩方法的全部理由，也是全书反复出现的矩方法分工：证"无"用一阶矩，证"有"用二阶矩。
- $\omega_n\to\infty$ 不可省略：Thm 2.2 的条件是 $\bar d_n>\log n+\omega_n$ 而非 $\bar d_n\ge\log n$。在恰好 $\bar d_n=\log n$ 的临界窗内，连通概率既非 0 也非 1（精细理论给出 $\mathrm e^{-\mathrm e^{-c}}$ 型极限），矩方法的估计量在窗内不闭合。Example 2.2/2.3 演示了如何选 $\omega_n$。
- $\mathcal G(n,(p_{ij}))$ / $\mathcal G(n,p)$ / $\mathrm{CM}_n(d)$ 的度分布不是一回事：Bernoulli 图的 $d_i$ 是独立但不同分布的伯努利和（Poisson binomial）；ER 是 $\mathrm{Bin}(n-1,p)$；配置模型的度序列是给定的（不是随机变量，随机性在配对）。三者常被混为一谈。
- DC-SBM 的 $\theta$ 有不可识别性：同社区 $\theta_i$ 全体乘 $c$、$P_{k\ell}$ 相应除以 $c$（$k\ne\ell$）或 $c^2$（$k=\ell$）模型不变，故必须归一化（原书取 $\sum_i\theta_i\mathbf 1(z_i=k)=n\pi_k$）；读文献时注意另一种常见归一化 $\sum_i\theta_i\mathbf 1(z_i=k)=1$，两者不可直接混用。
- PABM 与 DC-SBM 的差别在"人气是否随社区变"：DC-SBM 的 $\theta_i$ 是一个数——受欢迎的节点在所有社区都受欢迎；PABM 的 $\lambda_{ik}$ 是 $n\times K$ 矩阵——节点可以在社区 1 是枢纽、在社区 2 无人问津。Example 2.8/2.9 给出退化方向：PABM ⊃ DC-SBM ⊃ SBM（注意两式中的根号 $\sqrt{P_{k\ell}}$，pdftotext 文本层丢根号，以 内部 OCR 页面 为准）。
- ERGM 中 $\theta$ 与 $g(A)$ 的角色：$g(A)$ 是你选的网络统计量（边数、三角形数、度序列……），$\theta$ 是对应权重；$\theta^{T}\big(g(A_{ij}^+)-g(A_{ij}^-)\big)$ 是"翻转边 $(i,j)$ 的统计量增量"的加权和（Prop 2.8）。归一化常数 $\kappa(\theta)$ 含对全部 $2^{\binom n2}$ 个图的求和，一般不可解析计算——这是 ERGM 推断难的根源（本章不展开）。
- p₁ 模型的 $\rho$ 不是概率 $p$：$\rho$（互惠力）、$\mu$（密度）、$\alpha_i$（产出力）、$\beta_j$（吸引力）都是 $\mathbb R$ 上的指数族参数，可正可负；OCR 把本节标题误作 "The $\phi1$ Model"，应为 "The $p_1$ Model"（Holland–Leinhardt）。$R=\sum_{ij}A_{ij}A_{ji}$ 是互惠边数，不是相关系数。
- Lemma 编号跳号：Lemma 只有 2.4、2.5（无 2.1–2.3），Theorem 无 2.3——清单全书范围核实为原书编号，非 OCR 错误；引用时沿用原编号，不要自行"补全"重排。
15. 公式卡片
本章 9 个编号公式按"输入 → 输出 → 用途"整理；校勘要点附在相关卡片。
F1 — 式 (2.1)（Thm 2.2(b) 的并集界，文件页 34）： $$\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.$$ 输入 $X_k$（与外界无边的 $k$ 树）；输出"无孤立点不连通"的概率上界；用途：把连通性问题化为计数估计（证明）。
F2 — 式 (2.2)（优先连接概率，文件页 38）： $$\mathbb P\big((v_{t+1},v_i)\in E_{t+1}\mid G_t\big)=\begin{cases}\dfrac{1}{2t+1},&v_i=v_{t+1},\\\\\dfrac{d_i(t)}{2t+1},&\text{否则}.\end{cases}$$ 分母 $2t+1=\sum_i d_i(t)+1$（自环贡献 1）；归一性由 Lemma 2.5 保证。
F3 — 式 (2.3)（主方程，文件页 40）： $$p(k,s,t+1)=\frac{k-1}{2t+1}p(k-1,s,t)+\Big(1-\frac{k}{2t+1}\Big)p(k,s,t).$$ 初值 $p(k,1,1)=\delta_{k,1}$、边界 $p(k,t,t)=\delta_{k,1}$；幂律推导的引擎（证明）。
F4 — 式 (2.4)/(2.5)（SBM 条件似然，文件页 44）：$\mathbb P(G|z)=\prod_{i<j}P_{z_iz_j}^{A_{ij}}(1-P_{z_iz_j})^{1-A_{ij}}=\prod_{k\le\ell}P_{k\ell}^{N_{k\ell}(1)}(1-P_{k\ell})^{N_{k\ell}(0)}$。前者逐边、后者按社区对；$N_{k\ell}(a)$ 是充分统计量（证明）。
F5 — 式 (2.6)/(2.7)（Poisson 版 DC-SBM / SBM，文件页 47）：$A_{ij}=A_{ji}\sim\mathrm{Poi}(\theta_i\theta_j\omega_{z_iz_j})$；$\theta_i\equiv1$ 退化为 $\mathrm{Poi}(\omega_{z_iz_j})$。$n\omega_{k\ell}\ll1$ 时与伯努利版实践中等价，换来似然可分解。
F6 — 式 (2.8)（Poisson DC-SBM 似然，文件页 48）： $$\mathbb P(A\mid z,\theta,\omega)=\prod_{i<j}\frac{(\theta_i\theta_j\omega_{z_iz_j})^{A_{ij}}}{A_{ij}!}\mathrm e^{-\theta_i\theta_j\omega_{z_iz_j}}=\frac{\prod_i\theta_i^{d_i}}{\prod_{i<j}A_{ij}!}\prod_k\omega_{kk}^{m_{kk}}\mathrm e^{-\frac{n_k^2}2\omega_{kk}}\prod_{k<\ell}\omega_{k\ell}^{m_{k\ell}}\mathrm e^{-n_kn_\ell\omega_{k\ell}},$$ $n_k$ 为块 $k$ 节点数、$m_{k\ell}$ 为块间边数（$k=\ell$ 时计两倍）。用途：Ch4 谱方法与似然推断的标准输入。
F7 — 式 (2.9)（p₁ 模型，文件页 51）： $$\mathbb P(A)\propto\exp\Big(\rho R+\mu M+\sum_i\alpha_iA_{i+}+\sum_j\beta_jA_{+j}\Big),$$ $R$ 互惠边数、$M$ 总边数、$A_{i+}$/$A_{+j}$ 出/入度。四参数语义：$\mu$ 密度、$\alpha_i$ 产出力、$\beta_j$ 吸引力、$\rho$ 互惠力；全零除 $\mu$ 时退化为有向 ER（$\mu=\operatorname{logit}p$）。校勘：小节标题为 "The $p_1$ Model"，OCR 误作 $\phi1$。
F8 — ERGM 化恒等式（Example 2.12，文件页 50，未编号但反复引用）：Bernoulli 图 $\mathbb P(A)=\prod_{i<j}p_{ij}^{A_{ij}}(1-p_{ij})^{1-A_{ij}}=\kappa(\theta)^{-1}\exp\big(\sum_{i<j}\theta_{ij}A_{ij}\big)$，其中 $\theta_{ij}=\operatorname{logit}p_{ij}=\log\frac{p_{ij}}{1-p_{ij}}$、$\kappa(\theta)=\prod_{i<j}(1-p_{ij})^{-1}$；ER 特例 $g(A)=|E|$、$\theta=\operatorname{logit}p$。用途：证明"所有 Bernoulli 图（含 ER、SBM、DC-SBM）都是 ERGM"。
F9 — Prop 2.8 的 logit 关系（文件页 52）：$\operatorname{logit}\mathbb P(A_{ij}=1\mid A_{ij}^c)=\theta^{T}\big(g(A_{ij}^+)-g(A_{ij}^-)\big)$。ERGM 推断的钥匙（证明）。
另有两组值得记住的未编号估计：Lemma 2.4 的 $\mathbb P(A_i)=(1-p_n)^{n-1}\sim\mathrm e^{-\bar d_n}\sim\frac1n\mathrm e^{\mp\omega_n}$（连通性阈值 $\log n$ 的来源）；Thm 2.2(b) 的 $\mathbb E X_k=\binom nkk^{k-2}p_n^{k-1}(1-p_n)^{k(n-k)}$（Cayley 计数的样板）。
16. Further Notes 导读
本书无习题；章尾 Further Notes（印刷页 43–44）共 3 段，是本节的"延伸阅读说明书"。
第 1 段：补充读物（按相关度排序）——Barabási 2016（有免费在线交互版 networksciencebook.com）：网络科学的通俗全景，适合建立直觉，与本章 2.2 节对应最强（PA 模型的 Barabási–Albert 源头）；Hofstad 2016：本章全部"原书不证/不严格"之处的严格化出处（Thm 2.1 的分支过程证明、PA 的严格理论、Cayley 定理也是引它的定理 3.17）——想走理论路线的读者，这本书是本章的影子教材；Durrett 2007 与 Chung & Lu 2006：随机图动力学与"大平均度"模型的经典处理；Janson et al. 2011 与 Bollobás 2001：偏数学证明的经典专著（$\mathcal G(n,p)$ 的完整渐近理论），适合在读完本书后系统补强度。
第 2 段：本章未覆盖的模型——Watts–Strogatz 小世界模型（1998）：格点加少量随机重连，同时实现高聚类与短距离，正是 Ch1 易混点"小世界 vs 聚类"张力下的经典模型，本书留白，感兴趣读原论文即可；Abbe 2018：SBM 综述，Ch4 社区检测的理论背景（可检测性阈值等），建议学 Ch4 时配套读；Penrose 2003：随机几何图专著，2.2.3 节的严格化与 RGG 连通性阈值在此。
第 3 段：无标度几何图——双曲几何图模型（Krioukov et al. 2010）：把节点放进双曲空间，几何与幂律度分布兼得（RGG 的"边传递性"与 PA 的"幂律"在一个模型里），是对 Table 2.1"没有模型兼得全部性质"现状的重要补充；本书后续不展开，作为研究方向指路。
与本页的关系：第 1 段的 Hofstad 2016 对应 §10 定位卡片 与 Prop 2.3 注记；第 2 段的 Abbe 2018 是 §18 后续衔接 中 Ch4 的理论伴侣。
17. 学习检查表
学完本章后自查：
- [ ] 能复述：Bernoulli 图 $\mathcal G(n,(p_{ij}))$ 的定义，以及 ER、SBM、DC-SBM、PABM 各自如何作为它的特例写出 $p_{ij}$。
- [ ] 能复述：两个 regime 的定义与两个相变的阈值、结论（$\bar d=1$ 巨分量、$\bar d=\log n$ 连通），并说明"有巨分量 ≠ 连通"。
- [ ] 能证明：Lemma 2.4 完整证明（一阶矩收尾 (i)、二阶矩收尾 (ii)，含 $\mathbb P(A_1\cap A_2)=\mathbb P(A_1)^2/(1-p_n)$ 的关键计算）。
- [ ] 能证明：Thm 2.2(b) 的证明骨架：分解 → 生成树放大 → $\mathbb E X_k$ 的 Cayley 计数 → $k=2$ 尖估计 + $k\ge3$ 几何收尾；能说明原书粗界为何对 $k=2$ 失效。
- [ ] 能推导：主方程 (2.3) → 平稳方程 → $P(k)=Ck^{-3}$ 的链条，并说出 Remark 2.5 指出的三个不严格之处。
- [ ] 能推导：Prop 2.4 的 (2.4)(2.5) 与 Prop 2.5 的同质 SBM 似然（含 $K=1$ 退化核对）。
- [ ] 能计算：Prop 2.6/2.7 的期望度公式（含两种归一化的区别）；Example 2.2/2.3 中 $\omega_n$ 的取法。
- [ ] 能判别：给定一段描述，判断它属于哪个模型（配置模型/PA/SERN/SBM/DC-SBM/PABM/SGBM/ERGM），并指出嵌套关系（PABM⊃DC-SBM⊃SBM，SGBM 常数化得 SBM）。
- [ ] 能判别：p₁ 模型四个参数（$\rho,\mu,\alpha_i,\beta_j$）的语义，以及 $\theta_{ij}=\operatorname{logit}p_{ij}$ 的 ERGM 化恒等式。
- [ ] 能定位：Table 2.1 四模型 × 四性质各自的大致结论与"许多性质后续章才证明"的告诫；Further Notes 三段各自指向哪类读物。
18. 后续衔接
- 第 3 章 Centrality Indices：本章各模型的度分布结论（ER 二项集中、PA 幂律）是"度中心性"作为基准指标的模型背景；优先连接中的枢纽形成机制解释了为何真实网络需要超越度的中心性指标。
- 第 4 章 Community Detection：本章 2.3 节是直接的生成模型仓库——SBM（Definition 2.6/2.7）、DC-SBM（Definition 2.8）、PABM（Definition 2.9）；似然式 (2.4)(2.5) 与 Poisson 版 (2.8) 将被用于谱方法与似然方法的分析；Thm 2.1/2.2 的相变语言升级为"可检测性阈值"（Further Notes 指的 Abbe 2018 综述配套阅读）。Ch1 前瞻句 F1（karate club）与 F2（modularity 过拟合）在此兑现。
- 第 5 章 Semi-supervised Learning：2.2.3 的空间嵌入视角（几何邻近 ⇒ 边）与 Ch1 高斯核/KNN 图构造合流，成为图半监督学习的输入图来源。
- 第 6 章 Temporal Networks：优先连接（2.2.2）是本章唯一的增长/时序模型；时序网络章把"边何时出现"从生成机制升级为数据形态。
- 第 7 章 Sampling：本章模型（尤其 ER 与 SBM）将作为抽样方法的零模型与仿真基准。
- 术语表维护：本章译文落盘后，术语表中 邻接矩阵（占位
#sec-2-notations）与 巨分量（占位#sec-2-1-3-phase-transitions）等第 2 章条目的"首次系统引入"锚点需要回链到译文实际小节（由 glossary 工人执行）。