第 07 章学习笔记：网络中的抽样
第 07 章学习笔记：网络中的抽样
配套译文：
内部译文（译文不在公开版）。本章研究在只能访问网络一部分节点或边时，如何估计节点函数的平均值，并沿“均匀抽样 → 链式推荐/随机游走 → 偏差修正 → 跳跃与超节点 → 基于巡游的 motif 计数”逐步扩展可用的观测机制。全章有 12 个编号公式、1 个定理（Theorem 7.1）、5 组图（10 个子图），没有原书 Exercises；Theorem 7.1、RDS 的一致性/CLT 和任意 motif 的推广都不是书内已闭合证明的结果。
1. 一句话定位
本章回答：“当网络太大、无法完整观测时，怎样从有限的节点访问中估计 $\bar f=n^{-1}\sum_{v\in V}f(v)$，并控制均匀抽样困难、随机游走的度偏差、子网络困陷和 motif 计数的额外复杂度？”
2. 本章导读
- 问题形式化（印刷页 171）：把“网络有多年轻”“平均有多少朋友”“某个子群体占比”等问题都写成节点函数平均值 (7.1)。这一步决定了后面所有估计量必须对准“平均值”，而不是不加归一化的总和。
- 两种基本抽样（页 172）：独立均匀抽样最直接但难以实施，且难以获得稀有子群体；雪球抽样利用受访者的邻居列表，却继承随机游走对大度节点的 size bias。
- 两条偏差修正路线（页 173–176）：MH 通过改造转移概率，使目标平稳分布变成均匀分布；RDS 保留标准随机游走，只在估计量中按 $1/d(v)$ 加权。RDS 的比率式 (7.6) 不需要知道 $m$，更适合实际使用。
- 让游走离开局部区域（页 174–177）：在邻接矩阵中加入均匀跳跃，得到加权平稳分布 (7.7) 和比率式 (7.8)；如果均匀查询过于昂贵，则只连接少量远处节点并把它们合并成超节点，用巡游比率估计量处理。
- 从节点函数到 motif（页 177–178）：返回同一节点的巡游长度可估计边数；再给边按三角形参与次数加权，可构造三角形估计量。书中只写出三角形例子，并以一句“可直接推广”结束，任意 motif 的一般证明不在本章内。
- 数值比较与选择（页 178–180）：SBM 实验说明随机游走会放大高连接小社区的比例，超节点可降低难触达子群体估计的方差；DBLP 实验显示 MH 在两个目标函数上方差较大，而 RDS 与均匀抽样更稳定。章末 Further Notes 把视野扩展到 social sampling、多条并行游走、跳过样本和边/motif 函数。
3. 本页使用方式
本页按“先抓机制、再查公式、最后看证据边界”的顺序使用：
- 第一次阅读先看 §4 主线、§5 概念地图 和 §6 分层路线，暂时不要被 (7.10) 的双重求和卡住。
- 看到“无偏”时，先看 式 (7.2) 的补验证，再区分“独立均匀抽样”和“随机游走抽样”。
- 看到 $p$、$p_{vu}$、$\widetilde p_{vu}$、$p_{11}$、$P$ 和 $\widetilde P$ 混在一起时，直接查 §8 符号表 和 §14 易混点。
- 不要把 Theorem 7.1 的陈述当成已证明结果；定理外引卡只说明书中引用了哪些依赖、还缺哪些条件检查。
- 对式 (7.5)、(7.7)、(7.11) 的归一化或最大值写法有疑问时，先看 §10 公式校勘与验证，那里明确区分 PDF 印刷形式与按目标量修正后的写法。
- 图 7.2–7.5 不只是“谁的箱线图更窄”：先复述目标函数、真实值、抽样预算和网络结构，再解释方差与度偏差的来源，见 §16 数值实验读法。
4. 本章主线
| 推进层 | 要解决的问题 | 关键转折 | 后续用途 |
|---|---|---|---|
| ① 节点平均值 | 网络整体不可见时，目标究竟是什么？ | 统一写成 $\bar f=n^{-1}\sum_v f(v)$；$f$ 可表示年龄、度或子群体指示函数 | 所有估计量的归一化基准 |
| ② 均匀抽样 | 理论上最干净的估计如何实现？ | 独立均匀样本的样本均值无偏，但均匀查询和稀有群体收集都困难 | 作为偏差与方差的基线 |
| ③ 链式推荐/随机游走 | 只能通过受访者找邻居时会发生什么？ | 单邻居链式推荐变成随机游走，平稳分布与 $d(v)$ 成正比，因而大度节点过采样 | 需要 MH 或 RDS 修正 |
| ④ 偏差修正 | 如何恢复节点均匀目标？ | MH 改转移核；RDS 改估计量；前者会重复采样，后者需要度信息与外引极限定理 | 形成 (7.4)–(7.8) 的方法梯 |
| ⑤ 逃离局部区域 | 随机游走如何避免困在弱连接子网络？ | 在 $A$ 中加入均匀跳跃，或用少量跨区域人工边形成超节点；巡游把返回事件变成可计数对象 | RT-estimator、边数和 motif 估计 |
| ⑥ 经验比较 | 方法差异如何在数据上显现？ | 高度小社区造成 RW 高估；超节点降低稀有组比例的方差；MH 在 DBLP 上波动更大 | 依据访问成本、目标稀有度和方差选择方法 |
5. 本章学习路线 / 概念地图
这张图表达的是因果关系，不是方法名的并列清单：访问机制决定样本分布，样本分布决定偏差，偏差决定修正方式；当目标从节点函数扩展到 motif 时，还要改变游走的权重和返回时间统计。
$\bar f=\frac1n\sum_{v\in V}f(v)$
节点属性、度、子群体比例都只是不同的 $f$。
独立均匀抽样 / 链式推荐 / 标准随机游走
均匀抽样难，随机游走可行但产生度偏差。
MH：改核；RDS：改权重；跳跃：改图
目标是把平稳分布的影响抵消掉，而不是让所有样本独立。
$\widetilde A=A+\frac{\alpha}{n}\mathbf1\mathbf1^T$
均匀跳跃控制游走的覆盖性，$\alpha$ 调节访问成本与跳跃频率。
跨区域节点 $S$ → tours → RT-estimator
返回超节点提供了可重复的时间尺度。
边权 $1+t(\{u,v\})$ → 新平稳分布 → 三角形估计
从节点函数到 motif 需要新的权重设计，不能只换一个符号。
6. 分层阅读路线
- 第一遍（主线，约 45–60 分钟）：读章首问题与 (7.1) → 7.1.1/7.1.2 的访问机制差异 → 7.1.3/7.1.4 的 MH 与 RDS 对照 → 7.1.5 的均匀跳跃 → 7.3 三组实验结论。目标是能解释“为什么 RW 高估小社区、为什么 RDS 要除以度、为什么超节点可能降低方差”。
- 第二遍（公式精读，约 90 分钟）：按 §13 公式卡片 逐式检查 (7.1)–(7.12)，重点是 (7.4) 的自环概率、(7.5)/(7.7) 的平均值归一化、(7.10) 的超节点贡献和 (7.11) 的预算停止规则。
- 第三遍（证明与边界，约 90 分钟）：完成 无偏性补验证、加权平稳分布补验证，再阅读三个外引/未闭合卡片。目标不是把外部定理伪装成已证，而是知道每个结论的证据等级。
- 第四遍（实验复现视角）：对每个图写出“网络模型—目标函数—真实值—预算—方法—箱线图所显示的偏差/方差”，再看 §16 的解释。
- 专题回看：复习第 3 章 PageRank 时回看 (7.9) 与节点相关重启；复习第 2 章 SBM 时回看 7.3.1 的 $p_{11},p_{12},p_{22}$；复习随机游走返回时间时回看 $\mathbb E_s[\xi_j]=1/\pi_s$ 与 (7.12)。
7. 初学者背景补充
以下是学习层补充，目的是让第一次读网络抽样的读者能够跟上本章；它们不是原书新增正文。
7.1 节点平均值与总和的区别
式 (7.1) 的目标是
$$ \bar f=\frac{1}{n}\sum_{v\in V}f(v), $$
所以任何基于节点访问概率 $\pi(v)$ 的 Horvitz–Thompson 型估计，都要把总和估计再除以 $n$：
$$ \widehat{\bar f}=\frac{1}{nk}\sum_{s=1}^{k}\frac{f(V_s)}{\pi(V_s)}. $$
这条尺度检查正是发现式 (7.5)、(7.7) PDF 归一化问题的最短方法。比率型估计量 (7.6)、(7.8) 则通过分母中的逆度权重自动消掉总体常数。
7.2 随机游走、平稳分布与度偏差
无向图上的标准随机游走从节点 $v$ 以概率 $1/d(v)$ 走向每个邻居。若图连通且满足通常的遍历条件，其平稳概率为
$$ \pi(v)=\frac{d(v)}{2m}. $$
因此，一个节点被访问的长期比例不是 $1/n$，而是与度成正比。大度节点更容易被访问，正是朴素雪球抽样的 size bias。RDS 的 $1/d(v)$ 权重和 MH 的转移核修改，都在处理这一差异。
7.3 详细平衡与加权图
若 $\widetilde A$ 是对称的加权邻接矩阵，节点 $v$ 的加权度为 $\widetilde d(v)=\sum_u\widetilde A_{vu}$，则随机游走转移概率为 $\widetilde P_{vu}=\widetilde A_{vu}/\widetilde d(v)$。令总权重为 $\sum_v\widetilde d(v)$，则
$$ \widetilde\pi(v)=\frac{\widetilde d(v)}{\sum_x\widetilde d(x)} $$
满足
$$ \widetilde\pi(v)\widetilde P_{vu} =\frac{\widetilde A_{vu}}{\sum_x\widetilde d(x)} =\widetilde\pi(u)\widetilde P_{uv}. $$
这是 加权平稳分布验证 的核心。把 $\widetilde A=A+\alpha\mathbf1\mathbf1^T/n$ 代入即可得到 $\widetilde d(v)=d(v)+\alpha$ 与式 (7.7) 前的 $\widetilde\pi(v)$。
7.4 PageRank 与均匀跳跃
式 (7.9) 是最熟悉的“以固定概率重启”写法：$P$ 的每一步与从均匀分布跳回的操作混合。由 $\widetilde A$ 产生的跳跃则把 $\alpha$ 加到每个节点的加权度，等价于节点相关的重启概率。两者都能帮助游走离开局部区域，但其平稳分布的显式形式不同：加权无向游走直接由加权度给出，PageRank 型 $\widetilde P$ 一般没有这么简单的表达式。
7.5 巡游长度与返回时间
从节点 $s$ 出发、返回 $s$ 的一次巡游长度记为 $\xi_j$。Kac 返回时间公式给出
$$ \mathbb E_s[\xi_j]=\frac{1}{\pi_s}. $$
在普通无向图中 $\pi_s=d_s/(2m)$，于是得到 $2m/d_s$。对独立或满足适当遍历条件的巡游取平均，就得到边数估计式 (7.12) 的直觉来源。这里“满足适当条件”很重要：本章给出的是估计量构造，不是完整的有限样本误差分析。
7.6 motif 加权的想法
若一条边参与的三角形越多，就把它的随机游走权重设得越大，则节点 $v$ 的加权度包含 $\sum_{u\in N(v)}t(\{v,u\})$；对所有节点求和时，每个三角形在三个顶点、每个顶点的两条相关边上贡献，总计为 6，因此分母出现 $2m+6t(G)$。这是三角形公式的局部计数解释；它不自动给出任意 motif 的通用构造。
8. 核心对象与符号表
| 符号 | 含义 | 在本章中的角色 |
|---|---|---|
| $G=(V,E)$ | 无向网络，$V$ 为节点集、$E$ 为边集 | 抽样的总体 |
| $n=|V|$、$m=|E|$ | 节点数、边数 | 平均值、平稳分布和返回时间的归一化 |
| $f(v)$、$\bar f$ | 节点函数、节点函数平均值 | 所有估计量的目标 |
| $v_{i_s}$ | 第 $s$ 次访问/联系到的节点 | 样本序列；在随机游走下有相关性 |
| $k$ | 样本数量或 MH/RDS 预算 | (7.2)–(7.9) 的样本规模 |
| $d(v)$、$\bar d$ | 节点度、平均度 $2m/n$ | 造成随机游走 size bias，也进入修正权重 |
| $p$ | 7.1.1 中的节点抽样概率；MH 推导中的提议转移概率记号 | 不要与 SBM 的 $p_{ab}$ 混淆 |
| $\pi(v)$、$\widetilde\pi(v)$ | 标准/加权随机游走的平稳概率 | 将访问频率转换成节点均匀目标 |
| $P$、$\widetilde P$ | 标准随机游走转移矩阵、PageRank/跳跃修正转移矩阵 | (7.9) 与 Theorem 7.1 的基本矩阵 |
| $\widetilde A$ | 加入均匀权重后的邻接矩阵 | $A+\alpha\mathbf1\mathbf1^T/n$ |
| $\alpha$ | 人工均匀边的权重 | 控制跳跃成本与重启频率 |
| $S$、$d_S$ | 被合并为超节点的节点集、超节点度 | RT-estimator 的起点/终点与超节点补偿项 |
| $\xi_j$ | 第 $j$ 次巡游长度 | 返回时间统计量 |
| $B$、$m(B)$ | 抽样预算、预算内完成的巡游次数 | (7.10)–(7.12) 的停止规则 |
| $\widetilde f(v)$ | 超节点构造中的分段函数 | 对 $v\in S$ 置零并由单独补偿项处理 |
| $t(\{u,v\})$、$t(G)$ | 一条边参与的三角形数、全图三角形数 | motif 加权和平稳分布 |
| $\widehat m$、$\widehat t$ | 边数和三角形数估计量 | (7.12) 与三角形估计式 |
| $p_{11},p_{12},p_{22}$ | 7.3.1 SBM 的块间连边概率 | 控制小/大社区结构；不是 MH 的 $p_{vu}$ |
| $Z$、$\sigma_{\mathrm{MH}}^2$ | MH 定理中的基本矩阵、渐近方差 | Theorem 7.1 的结论对象 |
术语入口： 抽样（sampling）、度（degree）、随机游走（random walk）、PageRank、聚类系数（clustering coefficient）、随机分块模型（SBM）。第 3 章的随机游走/PageRank 背景可回看 03-centrality-indices，第 2 章的 SBM 背景可回看 02-random-graph-models。
9. 关键定理卡片
本章只有一个编号定理类对象：Theorem 7.1。其他核心结果是估计量构造和数值比较，不应被包装成没有来源的定理。
卡片 T1：Theorem 7.1（MH 估计量的中心极限定理）
- 条件/输入：样本由式 (7.4) 的 MH 转移概率生成；目标分布设为节点均匀分布；$f^T=(f(1),\ldots,f(n))$，$Z=[I-\widetilde P+n^{-1}\mathbf1\mathbf1^T]^{-1}$。
- 结论：$\sqrt{k}(\widehat f^{(k)}-\bar f)$ 在 $k\to\infty$ 时依分布收敛到 $\mathcal N(0,\sigma_{\mathrm{MH}}^2)$，其中 $\sigma_{\mathrm{MH}}^2$ 由 $f$ 与基本矩阵 $Z$ 给出。
- 用途：它把 MH 的相关样本误差压缩到一个渐近方差常数中；因此“平稳分布无偏”不等于“有限样本方差小”。图 7.4–7.5 中 MH 的箱线图较宽，正好提醒读者关注方差而不只看中心位置。
- 证据状态：书内只陈述，不给证明；原文把马尔可夫链 CLT 归于 Brémaud（1999），把本估计量的一致性/方差结果归于 Avrachenkov et al.（2018b）。详见 外引依赖卡。
10. 公式校勘与补验证
本节是学习层补充。它只闭合可以由定义和基本平稳分布直接检查的短步骤；对书中外引定理和 motif 泛化，不把“知道应当成立”写成证明。
目标：验证式 (7.2) 的样本均值对 (7.1) 无偏。
依赖工具：每个 $V_s$ 独立且均匀分布在 $V$ 上，即 $\mathbb P(V_s=v)=1/n$。
计算：
$$ \mathbb E[\widehat f^{(k)}] =\frac1k\sum_{s=1}^k\mathbb E[f(V_s)] =\frac1k\sum_{s=1}^k\frac1n\sum_{v\in V}f(v) =\bar f. $$闭合检查：独立性并不是计算期望时的必要条件，但它影响方差；式 (7.2) 的“无偏”与“样本彼此独立”是两个不同性质。
目标：验证 $\widetilde A=A+\frac{\alpha}{n}\mathbf1\mathbf1^T$ 时，$\widetilde\pi(v)=\frac{d(v)+\alpha}{2m+\alpha n}$。
证明思路：$\widetilde A$ 对称；每个节点从人工边得到的额外加权度为 $\sum_{u=1}^{n}\alpha/n=\alpha$，所以 $\widetilde d(v)=d(v)+\alpha$，总加权度为 $2m+\alpha n$。
完整补验证：令 $\widetilde P_{vu}=\widetilde A_{vu}/\widetilde d(v)$，并令 $\widetilde\pi(v)=\widetilde d(v)/(2m+\alpha n)$。则对任意 $u,v$，
$$ \widetilde\pi(v)\widetilde P_{vu} =\frac{\widetilde d(v)}{2m+\alpha n}\frac{\widetilde A_{vu}}{\widetilde d(v)} =\frac{\widetilde A_{vu}}{2m+\alpha n} =\frac{\widetilde A_{uv}}{2m+\alpha n} =\widetilde\pi(u)\widetilde P_{uv}. $$详细平衡成立，因此 $\widetilde\pi$ 是平稳分布。再用 $2m=n\bar d$，便得到 (7.7) 前的第二个表达式。
书中陈述：式 (7.5) 和 (7.6) 渐近一致，相应中心极限定理见 Avrachenkov et al.（2018b）。
本笔记不补伪证：要完整闭合，需要明确随机游走的不可约/遍历条件、初始状态影响、$f$ 的可积性或有限状态条件，以及比率估计量分子分母的联合极限。原书在本章没有给出这些条件和推导；本卡只记录外引依赖。
可做的局部检查：在标准无向游走的平稳分布 $\pi(v)=d(v)/(2m)$ 下，$\mathbb E[f(V)/d(V)]=(2m)^{-1}\sum_v f(v)$，这解释了 (7.5) 的 $2m/n$ 归一化，但不等于已经证明有限样本 RDS 的一致性或 CLT。
书内状态：原书在陈述前写明使用马尔可夫链中心极限定理，引用 Brémaud（1999），并将本估计量的渐近一致性归于 Avrachenkov et al.（2018b）；没有书内 Proof。
未闭合点：若要形成完整证明，至少要从式 (7.4) 的有限状态马尔可夫链性质出发，验证适用的遍历/非周期条件，调用马尔可夫链 CLT，再计算相关和（或基本矩阵）给出的渐近方差。当前项目只拥有本书该章的 PDF 证据，未把外部论文的证明内容当作原文，也未伪造这些中间步骤。
证据等级：定理陈述与 $\sigma_{\mathrm{MH}}^2$ 公式已按 PDF 复核；“定理成立”是原书引用外部结果的陈述，不是本页新完成的证明。
书中原句：三角形估计量之后，原书说“把这一方法用于计数任意网络 motif 是直接的”，并在 Further Notes 将边/motif 函数指向 Avrachenkov et al.（2016c）。
为什么不能直接写成证明：一般 motif 需要逐一指定边或局部结构的权重、相应的加权平稳分布、巡游观测量、归一化和可能的重叠修正；还需要给出一致性、偏差或方差条件。三角形的“每个三角形贡献 6”不能自动替换成任意 motif 的常数。
当前结论：本章给出三角形的一个具体构造，任意 motif 的一般化在本笔记中保持未闭合；若要补全，应外读 Cooper et al.（2016）及 Avrachenkov et al.（2016c），并逐 motif 核对假设。
10.1 归一化校勘的最短推导
学习层补充如下：若 $V_s\sim\pi$，则
$$ \mathbb E\left[\frac{f(V_s)}{\pi(V_s)}\right]=\sum_{v\in V}f(v). $$
所以估计节点平均值必须使用 $1/(nk)$，而不是只使用 $1/k$。代入 $\pi(v)=d(v)/(2m)$ 得到 (7.5) 的 $2m/(nk)$；代入 $\widetilde\pi(v)=(d(v)+\alpha)/(n(\bar d+\alpha))$ 得到 (7.7) 的第二个表达式。这个推导只解释译文的校勘修正，不声称替作者完成 RDS 或 MH 的完整渐近理论。
10.2 PDF/版面与 OCR 异常对账
- OCR 把式 (7.2) 的 $p$ 识为 $\hbar$，把式 (7.4) 的 $\widetilde p$ 识为 $\widetilde{\jmath}$；PDF 版面已确认普通的 $p$ 与带 tilde 的 $p$。
- OCR 将 Theorem 7.1 的 $\xrightarrow{D}$、$k\to\infty$ 和 $Z$ 的基本矩阵表达式压成
array碎片；PDF 版面已按矩阵/渐近式恢复。 - OCR 将图 7.3 的 $p_{11},p_{12}$ 识为 $\phi_{11},\phi_{12}$，并把 $p_{22}$ 断开；PDF 图注确认 $p_{11}=0.8$、$p_{12}=p_{22}=0.0005$。
- OCR 的数字空格（$20000$、$500$、$2000$、$1000$、$10000$、$1{,}049{,}866$ 等）、
RDSestimator连字符、hard-to-reach连字符和式 (7.10) 的括号均已按文本层/版面核对。 - PDF 本身的文字/排版瑕疵（
questionary、are plot、affect、boxplot show、式 (7.4) 自环项的 $d(u)$、式 (7.5)/(7.7) 归一化、式 (7.11) 的集合写法）均在译文局部校勘提示中显式登记；没有静默吞掉。
11. 正文隐藏验证与证明状态
| 原文位置 | 触发句/任务 | 分类 | 本笔记处理 |
|---|---|---|---|
| 7.1.1 | “simplest unbiased estimator” | 可直接验证 | 无偏性补验证；不扩写成统计理论综述 |
| 7.1.2 | 单邻居链式推荐对应随机游走 | 说明性观察 | 用平稳分布解释度偏差，不另造定理 |
| 7.1.5 | 加权无向图的平稳分布与 $\widetilde\pi(v)$ | 练习级留白 | 详细平衡补验证 |
| 7.1.4 | RDS (7.5)/(7.6) 一致性与 CLT | 真正外引留白 | RDS 外引卡，不伪造证明 |
| 7.1.3 | Theorem 7.1 | 真正外引留白 | MH CLT 外引卡，不伪造证明 |
| 7.1.5 | “To see this” 的矩阵变换 | 作者现场给出 | 译文完整保留两行变换，笔记只解释 $C$ 与 $\nu$ 的角色 |
| 7.2 | “straightforward” 推广到任意 motif | 未闭合推广 | motif 未闭合卡 |
| 7.3 | “why uniform sampling might not always perform best” | 设问后由实验回答 | 用 Figure 7.3 的稀有群体/超节点设计解释，不生成额外实验结论 |
| 7.3 | “We observe …” 图读法 | 说明性观察 | 按真实值、中心位置、箱体宽度和方法机制拆读，见 §16 |
12. 关键方法卡片
卡片 M1：独立均匀抽样
- 访问分布：$\pi(v)=1/n$。
- 估计量：式 (7.2)，直接平均 $f(v_{i_s})$。
- 优点：无偏、样本独立、解释简单。
- 代价：均匀访问本身可能很昂贵；稀有子群体需要很大的样本预算。
卡片 M2：朴素雪球 / 标准随机游走
- 访问分布：无向图上 $\pi(v)=d(v)/(2m)$。
- 问题：大度节点更常被访问；若大度与研究目标相关，就会产生系统偏差。
- 用途：作为 RDS、MH 和跳跃方法的基线，不应把它的样本均值直接当作均匀节点平均值。
卡片 M3：MH 抽样
- 修正位置：改变转移矩阵 (7.4)，目标平稳分布设为 $1/n$。
- 代价：为保持目标分布，可能频繁留在原节点或重复访问节点。
- 理论状态：Theorem 7.1 的渐近结论由书中外引；有限预算下的方差仍需从 $\sigma_{\mathrm{MH}}^2$ 和实验判断。
卡片 M4：RDS
- 修正位置：保留标准随机游走，估计时除以访问节点的度。
- 两种形式：知道 $m$ 时用 (7.5)；不知道 $m$ 时用不需要总体常数的比率式 (7.6)。
- 理论状态：一致性与 CLT 指向 Avrachenkov et al.（2018b）；本章只给构造和引用。
卡片 M5：均匀跳跃与超节点
- 均匀跳跃：在每对节点间加权，使平稳度由 $d(v)$ 变成 $d(v)+\alpha$。
- 超节点：把少量已知、跨区域的节点合并，利用从超节点出发并返回的巡游。
- 选择逻辑：均匀查询贵但稀有群体重要时，少量“锚点”可能比完全均匀抽样更有效；图 7.3 展示的是一个具体实验场景，不是普遍保证。
13. 公式卡片总览
下面逐号列出库存中的 12 个编号公式。每一行给出“记住什么”，不是用一句话替代原公式；原公式已完整保留在译文中。
| 公式 | 核心形式/对象 | 读法与校勘 |
|---|---|---|
| (7.1) | $\bar f=n^{-1}\sum_{v\in V}f(v)$ | 目标是平均值；检查后续是否多/少一个 $n$ |
| (7.2) | $k^{-1}\sum_s f(v_{i_s})$ | 独立均匀样本的样本均值；无偏性见补验证卡 |
| (7.3) | 同一形式的雪球估计量 | 形式相同不代表分布相同；联系机制已改变 |
| (7.4) | MH 的分段转移概率 $\widetilde p_{vu}$ | 邻居项为 $1/\max\{d(v),d(u)\}$；自环求和按 $d(s)$ 校勘 |
| (7.5) | $\frac{2m}{nk}\sum_s f(v_{i_s})/d(v_{i_s})$ | PDF 漏印平均值所需的 $1/n$；推导见 §10.1 |
| (7.6) | $\frac{\sum_s f(v_{i_s})/d(v_{i_s})}{\sum_s1/d(v_{i_s})}$ | 比率式，不需要已知 $m$，但渐近性质外引 |
| (7.7) | $\frac1{nk}\sum_s f(v_{i_s})/\widetilde\pi(v_{i_s})$ | 代入 $\widetilde\pi$ 后为 $(\bar d+\alpha)k^{-1}\sum_s f/(d+\alpha)$；PDF 的 $n$ 位置已校勘 |
| (7.8) | 以 $d(v)+\alpha$ 为逆权重的比率式 | 平均度和节点数未知时使用 |
| (7.9) | $\widetilde P=(1-\varepsilon)P+\varepsilon n^{-1}\mathbf1\mathbf1^T$ | 固定重启概率的 PageRank 风格候选 |
| (7.10) | 巡游内节点贡献 + 超节点补偿的比率 | 分子用 $\sum_{v\in S}f(v)/d_S$，分母用 $n/d_S$ |
| (7.11) | $m(B)=\max\{k:\sum_{j\le k}\xi_j\le B\}$ | 表示预算内巡游次数；PDF 集合写法已校勘 |
| (7.12) | $\widehat m=\frac{d_s}{2m(B)}\sum_k\xi_k$ | 由返回时间 $\mathbb E_s\xi=2m/d_s$ 得到边数估计 |
13.1 不编号但必须保留的公式组
- MH 接受率的三行化简：$\frac1{d(v)}\min\{1,d(v)/d(u)\}=1/\max\{d(v),d(u)\}$。
- 均匀跳跃的加权邻接矩阵与平稳分布：$\widetilde A=A+\alpha\mathbf1\mathbf1^T/n$、$\widetilde\pi(v)=(d(v)+\alpha)/(2m+\alpha n)$。
- PageRank 等价分解、$C=(D+\alpha I)^{-1}D$ 和均匀个性化分布 $\nu=n^{-1}\mathbf1^T$。
- 连续重启间隔期望：$(2m+\alpha n)/(n\alpha)=(\bar d+\alpha)/\alpha$。
- 返回时间 $\mathbb E_s[\xi_j]=1/\pi_s=2m/d_s$。
- 三角形加权平稳分布与 $\widehat t$；后者的 $\max\{0,\cdot\}$ 保证估计结果不为负。
14. 易混点与校勘备忘
- 平均值与总和：$\sum_v f(v)$、$n^{-1}\sum_v f(v)$ 和 $k^{-1}\sum f(V_s)/\pi(V_s)$ 不是同一个目标。先写出目标，再检查 $n$ 的位置。
- $p$ 的三种角色：7.1.1 的 $p$ 是抽样概率/提议概率；MH 的 $p_{vu}$ 是转移记号；7.3 的 $p_{ab}$ 是 SBM 的连边概率。它们不能互相替换。
- $P$ 与 $\widetilde P$：$P$ 是标准随机游走转移矩阵，(7.9) 的 $\widetilde P$ 是 PageRank 风格修正；Theorem 7.1 中 $Z$ 用的是 MH 修正后的转移矩阵。
- RDS 与 MH 的修正位置不同：MH 改“怎么走”，RDS 改“如何加权”；两者都可以修正度偏差，但相关性、重复访问和方差行为不同。
- 均匀跳跃与完全均匀抽样不同：加入人工权重并不等于每一步独立均匀抽节点；它改变的是加权随机游走的平稳分布与局部困陷行为。
- 超节点不是把 $S$ 删除：$\widetilde f(v)$ 在 $S$ 上取 0，但 (7.10) 的分子另有 $\sum_{v\in S}f(v)/d_S$ 补偿项；忽略补偿会改变目标。
- $m(B)$ 不是任意可行 $k$ 的集合：正文把它称为巡游数量，故按最大可行 $k$ 读取；这是式 (7.11) 的校勘点。
- 三角形中的 6：每个三角形有 3 条边，每条边的权重统计会从两个端点贡献，因此总计 6；它是三角形构造的计数常数，不是任意 motif 的通用常数。
- “increase the mixing time”：PDF 的字面与“连接远处节点以离开子网络”的通常直觉相冲突。译文保留字面并加校勘；学习时按“提高混合效率/降低混合时间”的机制理解，同时保留这一原书疑点。
- 图 7.2–7.5 的中心与宽度：中心接近真实值说明偏差小，箱体/须较窄才说明方差小；MH 可能中心正确但波动更大。
15. 章节阅读路径
建议按以下路径在译文与笔记间来回切换：
- 译文章首与 (7.1) → 笔记 §4 主线。
- 译文 7.1.1–7.1.2 → §10.1 归一化检查 与 §12 方法卡片。
- 译文 7.1.3 Theorem 7.1 → T1 定理卡 与 外引状态卡。
- 译文 7.1.4–7.1.5 → RDS 外引卡 与 加权平稳补验证。
- 译文 7.1.6–7.2 → §13 公式卡片 与 motif 未闭合卡。
- 译文 7.3 → §16 数值实验读法，最后回到 §18 学习检查表。
16. 数值实验读法
Figure 7.2：小社区比例
网络是 $n=20000$ 的两社区 SBM，小社区只有 200 个节点，真实比例为 $0.01$。$p_{11}=0.3$ 使小社区内部更稠密，因而其中节点平均度更大。标准随机游走按度访问，所以 RW 箱线图明显在 0.01 之上；MH、RDS 和均匀抽样把中心拉回真实值附近。增加预算从 $k=500$ 到 $k=2000$ 会减小波动，但不会自动消除 RW 的结构性偏差。
Figure 7.3：难触达子群体与超节点
小社区大小为 500，并分成 Group-A/Group-B；研究目标是小社区内部 Group-A 的比例，真实值为 $0.5$。完全均匀抽样在大网络中很难频繁命中这个小社区；已知的 10 个 Group-A 节点被合并成超节点后，RDS 获得了更稳定的入口，箱体比均匀抽样窄。这是“利用少量结构先验降低方差”的例子，不意味着超节点在所有网络上都优于均匀抽样。
Figure 7.4：平均度
DBLP 的真实平均度为 6.6。MH、RDS 和均匀抽样的中心大体都围绕 6.6，但 $k=1000$ 时 MH 的离散程度最大；$k=10000$ 时三种方法都收紧。这里应把“无偏/一致”与“给定预算下的方差”分开阅读。
Figure 7.5：大度节点比例
目标是 $\mathbb P(d(v)>50)$，真实比例为 0.01。$k=1000$ 时 MH 的离群点和箱体更明显，RDS 与均匀抽样更紧；预算增大到 $10000$ 后三者都靠近真实值。该图再次说明，目标函数是稀有事件指示函数时，方差会成为主要的实践约束。
17. 原书习题与学习层自测
本章 没有原书 Exercises。以下是学习层新增自测，不属于原书题目：
- 设 $f(v)=d(v)$，分别用 $\pi(v)=1/n$ 和 $\pi(v)=d(v)/(2m)$ 计算 $\mathbb E[f(V)/\pi(V)]$，说明为什么逆平稳概率会产生总和估计。
- 从详细平衡关系出发，重新推出 $\widetilde A=A+\alpha\mathbf1\mathbf1^T/n$ 时的 $\widetilde\pi(v)$。
- 解释为什么 (7.6) 的分母可以消去未知 $m$，并指出这一步需要什么样的长链/遍历假设才可能转化为渐近结论。
- 对 Figure 7.2 写出“网络结构 → 度偏差 → 箱线图中心偏移”的三步因果链。
- 检查式 (7.10) 中超节点分子补偿项和分母 $n/d_S$ 的角色；不要把 $\widetilde f$ 在 $S$ 上取零理解为删除 $S$ 的信息。
- 说明为什么“任意 motif 的推广”需要重新指定权重与归一化，不能仅把三角形符号 $t$ 换成另一个 motif 名称。
18. 学习检查表
- [ ] 我能从 (7.1) 说清楚本章的目标是节点函数平均值，而不是总和。
- [ ] 我能解释独立均匀抽样为什么无偏，以及它为什么在现实网络中难实施。
- [ ] 我能用 $\pi(v)=d(v)/(2m)$ 解释朴素雪球抽样的大度偏差。
- [ ] 我能区分 MH（改转移核）和 RDS（改估计权重）。
- [ ] 我能检查式 (7.5) 和 (7.7) 中平均值归一化的 $1/n$。
- [ ] 我能从 $\widetilde A$ 的加权度推出 $\widetilde\pi(v)$，并理解 $\alpha$ 对跳跃频率的作用。
- [ ] 我能说明超节点、巡游长度和返回时间如何连接到 (7.10)–(7.12)。
- [ ] 我能解释三角形公式中的 $2m+6t(G)$ 与 $\max\{0,\cdot\}$。
- [ ] 我知道 Theorem 7.1 和 RDS 的 CLT 是书内外引依赖，而不是本章已给证明。
- [ ] 我知道 motif 泛化在本笔记中保持未闭合，没有把“straightforward”当作证明。
- [ ] 我能按真实值、中心位置、箱体宽度和预算读 Figure 7.2–7.5。
19. 进一步阅读（Further Notes 的学习定位）
章末四条 Further Notes 的共同主题是：网络抽样的“访问机制”还可以继续改变。
- Social sampling：一次访问同时暴露邻居信息，介于节点均匀抽样与随机游走之间；它减少查询次数，但依赖具体平台是否能提供邻居信息。
- 多条并行随机游走：并行化可能提高效率，但游走之间的依赖设计、连续时间转移率和方差分析不能被“并行”二字自动解决。
- 跳过样本：链式推荐中跳过部分访问可降低相邻样本相关性，但会减少可用样本，需要新的预算/方差权衡。
- 边与 motif 函数：从节点函数推广到边或 motif，需要新的局部观测和权重设计；本章三角形公式是具体示例，不是通用证明。