第 07 章学习笔记：网络中的抽样
配套译文：
translations/07-sampling.md。本章研究在只能访问网络一部分节点或边时，如何估计节点函数的平均值，并沿“均匀抽样 → 链式推荐 / 随机游走 → 偏差修正 → 跳跃与超节点 → 基于往返游程的网络模体计数”逐步扩展可用的观测机制。全章有 12 个编号公式、1 个定理（Theorem 7.1）、5 组图（10 个子图），没有原书 Exercises；Theorem 7.1、RDS 的一致性 / 中心极限定理和任意网络模体的推广都不是书内已闭合证明的结果。
在网络数据中，“怎样找到下一个节点”本身就是抽样设计。先写清总体目标，再由访问概率决定是修改转移核、修改估计权重，还是改变网络访问方式。
- 观测
- 相关的节点访问序列
- 抽样机制
- 均匀、随机游走、MH、跳跃
- 目标
- 节点均值、边数或网络模体数
- 失败模式
- 按度过度抽样、局部困陷与高方差
- 01写清估计目标
区分节点平均值、总体总和、边数和网络模体数，并检查归一化尺度。
- 02解释访问偏倚
从随机游走平稳分布推出按度过度抽样，并预测朴素均值的偏差方向。
- 03比较修正路线
说明 MH 修改转移核、RDS 修改估计权重、跳跃与超节点修改访问结构。
- 04判断证据等级
区分无偏性验证、渐近定理、外引结果与尚未闭合的网络模体推广。
逐页精读 · 按需展开原书顺序、详细导读与卡点索引第一次学习先算星形图，再看访问机制总图。
1. 一句话定位
本章回答：“当网络太大、无法完整观测时，怎样从有限的节点访问中估计 $\bar f=n^{-1}\sum_{v\in V}f(v)$，并控制均匀抽样困难、随机游走的度偏倚、子网络困陷和网络模体计数的额外复杂度？”
2. 本章导读
- 问题形式化（印刷页 171）：把“网络有多年轻”“平均有多少朋友”“某个子群体占比”等问题都写成节点函数平均值 (7.1)。这一步决定了后面所有估计量必须对准“平均值”，而不是不加归一化的总和。
- 两种基本抽样（页 172）：独立均匀抽样最直接但难以实施，且难以获得稀有子群体；滚雪球抽样利用被访者的邻居列表，却继承随机游走的度偏倚（degree bias，即高度节点被过度抽样）。
- 两条偏差修正路线（页 173–176）：MH 通过改造转移概率，使目标平稳分布变成均匀分布；RDS 保留标准随机游走，只在估计量中按 $1/d(v)$ 加权。RDS 的比率式 (7.6) 不需要知道 $m$，更适合实际使用。
- 让游走离开局部区域（页 174–177）：在邻接矩阵中加入均匀跳跃，得到加权平稳分布 (7.7) 和比率式 (7.8)；如果均匀查询过于昂贵，则只连接少量远处节点并把它们合并成超节点，用 Ratio with Tours 估计量（基于往返游程的比率估计量）处理。
- 从节点函数到网络模体（页 177–178）：返回同一节点的往返游程长度可估计边数；再给边按三角形参与次数加权，可构造三角形估计量。书中只写出三角形例子，并以一句“可直接推广”结束，任意网络模体的一般证明不在本章内。
- 数值比较与选择（页 178–180）：SBM 实验说明随机游走会放大高连接小社区的比例，超节点可降低难触达子群体估计的方差；DBLP 实验显示 MH 在两个目标函数上方差较大，而 RDS 与均匀抽样更稳定。章末 Further Notes 把视野扩展到社交抽样（social sampling）、多条并行游走、跳过样本以及边函数 / 网络模体函数。
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 数值实验读法。
快速掌握
围绕研究问题、贯穿例子和方法选择建立第一遍认知地图。
按任务读完本章
先建立本章的选择框架，再补公式与证明；最后用主动回忆和跨章连接检查是否真正掌握。
- 第一遍（主线，约 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) 的预算停止规则。
- 第四遍（实验复现视角）
对每个图写出“网络模型—目标函数—真实值—预算—方法—箱线图所显示的偏差/方差”，再看 §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)。
按原书页序阅读需要逐页精读时，再打开章节停靠点主题学习无需展开；并排阅读时可把它当作页序索引。
贯穿例子：星形图上的度偏倚与 RDS 修正
考虑 5 个节点的星形图：中心节点 $c$ 与 4 个叶节点相连。因此 $d(c)=4$，每个叶节点的度为 $1$。目标是估计“中心节点在总体中的比例”，即令 $$f(v)=\mathbf 1\{v=c\},\qquad \bar f=\frac15.$$
标准随机游走的平稳分布与度成正比： $$\pi(c)=\frac4{2m}=\frac12,\qquad \pi(\text{每个叶节点})=\frac1{8}.$$ 所以直接对长游走中的 $f(V_s)$ 求平均，极限不是 $1/5$，而是 $1/2$。这就是度偏倚（degree bias，即按度过度抽样）：中心节点只占总体的 20%，却占长期访问的 50%。原书在 MH 小节写作 bias with respect to node degrees，并未把 size bias 用作本章的命名术语。
RDS 不改变这条游走，而用逆度比率修正： $$ \frac{\mathbb E_\pi[f(V)/d(V)]}{\mathbb E_\pi[1/d(V)]} =\frac{(1/2)(1/4)}{(1/2)(1/4)+4(1/8)(1)} =\frac{1/8}{5/8}=\frac15. $$
同一例子也说明 MH 与 RDS 的根本区别：MH 修改转移概率，使节点长期访问趋于均匀；RDS 接受按度访问已经发生，再在估计阶段用 $1/d(v)$ 抵消它。两者都不让相邻样本自动独立，因此实际精度还取决于混合速度、自相关和给定预算下的方差。
本章决策地图：抽样与估计选择器
先读上半部的“为什么转向”，再按下半部任务卡选读；不必把两层信息重复背一遍。
无法均匀访问全网时，样本分布怎样进入估计量？
先识别访问机制诱导的偏差，再选择改转移核、改权重或改采样结构。
这张图表达的是因果关系，不是方法名的并列清单：访问机制决定样本分布，样本分布决定偏差，偏差决定修正方式；当目标从节点函数扩展到网络模体时，还要改变游走的权重和返回时间统计。
$\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\})$ → 新平稳分布 → 三角形估计
从节点函数到网络模体需要新的权重设计，不能只换一个符号。
抽样与估计选择器
先确定访问机制诱导的样本分布，再选择偏差修正与方差控制方法。
① 节点平均值
网络整体不可见时，目标究竟是什么？
统一写成 $\bar f=n^{-1}\sum_v f(v)$；$f$ 可表示年龄、度或子群体指示函数
所有估计量的归一化基准
② 均匀抽样
理论上最干净的估计如何实现？
独立均匀样本的样本均值无偏，但均匀查询和稀有群体收集都困难
作为偏差与方差的基线
③ 链式推荐/随机游走
只能通过受访者找邻居时会发生什么？
单邻居链式推荐变成随机游走，平稳分布与 $d(v)$ 成正比，因而大度节点过采样
需要 MH 或 RDS 修正
④ 偏差修正
如何恢复节点均匀目标？
MH 改转移核；RDS 改估计量；前者会重复采样，后者需要度信息与外引极限定理
形成 (7.4)–(7.8) 的方法梯
⑤ 逃离局部区域
随机游走如何避免困在弱连接子网络？
在 $A$ 中加入均匀跳跃，或用少量跨区域人工边形成超节点；往返游程把返回事件变成可计数对象
RT 估计量、边数和网络模体估计
⑥ 经验比较
方法差异如何在数据上显现？
高度小社区造成 RW 高估；超节点降低稀有组比例的方差；MH 在 DBLP 上波动更大
依据访问成本、目标稀有度和方差选择方法
先选最接近当前任务的一张卡；第一遍只追踪“问题 → 转折”，第二遍再沿“后续用途”进入公式、证明与跨章连接。
易混点与校勘备忘
把最容易混用的对象并排拆开
每张卡只处理一个边界：先说清差别，再回到公式、假设或例子验证。
平均值与总和
先拆开相近概念，再核对条件与结论。
$\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；它是三角形构造的计数常数，不是任意网络模体的通用常数。
“increase the mixing time”
先拆开相近概念，再核对条件与结论。
PDF 的字面与“连接远处节点以离开子网络”的通常直觉相冲突。译文保留字面并加校勘；学习时按“提高混合效率/降低混合时间”的机制理解，同时保留这一原书疑点。
图 7.2–7.5 的中心与宽度
先拆开相近概念，再核对条件与结论。
中心接近真实值说明偏差小，箱体/须较窄才说明方差小；MH 可能中心正确但波动更大。
主动回忆（本章无原书习题）
本章 没有原书 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$ 的信息。
- 说明为什么“任意网络模体的推广”需要重新指定权重与归一化，不能仅把三角形符号 $t$ 换成另一个网络模体名称。
核对资料 · 按需展开核对最短答案（先独立作答）先独立阅读或作答；需要核对时再展开。
- 对任意访问分布 $\pi$，$\mathbb E[f(V)/\pi(V)]=\sum_v f(v)$；若目标是平均值还须除以 $n$。均匀分布与按度分布只改变每个样本的权重形状。
- 对称加权图满足详细平衡，平稳概率正比于加权度；加入均匀权重后 $\widetilde d(v)=d(v)+\alpha$，再按总加权度归一化。
- 标准随机游走下 $\pi(v)\propto d(v)$，分子和分母中的共同常数 $1/(2m)$ 相消；渐近解释仍需不可约、适当非周期与遍历定理等条件。
- 小社区内部更稠密使其节点度更高，随机游走按度过度访问该社区，朴素样本比例因此系统性高于真实比例。
- $\widetilde f$ 在 $S$ 上置零是把超节点内部贡献移到显式补偿项，不是删除信息；$n/d_S$ 校准总体尺度。
- 不同网络模体在一条边或一个节点上的重复计数次数不同，必须重新推导局部权重、平稳分布、总体计数倍数与估计量归一化。
若主动回忆题能够用自己的语言回答，可以先暂停；需要复现推导或核查证明时，再进入第二遍。
深入理解
把背景工具、符号、定理和证明链放回同一逻辑结构中。
初学者背景补充
预备知识 · 按需展开只补当前章节真正需要的前置工具已经熟悉时可直接跳过；遇到符号或证明卡点再回来。
以下是学习层补充，目的是让第一次读网络抽样的读者能够跟上本章；它们不是原书新增正文。
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$，而是与度成正比。高度节点更容易被访问，这种现象称为度偏倚（按度过度抽样；degree 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$ 的一段轨迹称为一次往返游程（tour），其长度记为 $\xi_j$。Kac 返回时间公式给出
$$ \mathbb E_s[\xi_j]=\frac{1}{\pi_s}. $$
在普通无向图中 $\pi_s=d_s/(2m)$，于是得到 $2m/d_s$。对满足适当再生与遍历条件的往返游程取平均，就得到边数估计式 (7.12) 的直觉来源。这里“满足适当条件”很重要：本章给出的是估计量构造，不是完整的有限样本误差分析。
7.6 网络模体加权的想法
若一条边参与的三角形越多，就把它的随机游走权重设得越大，则节点 $v$ 的加权度包含 $\sum_{u\in N(v)}t(\{v,u\})$；对所有节点求和时，每个三角形在三个顶点、每个顶点的两条相关边上贡献，总计为 6，因此分母出现 $2m+6t(G)$。这是三角形公式的局部计数解释；它不自动给出任意网络模体的通用构造。
核心对象与符号表
把本章会反复调用的记号集中在一处；读证明时从这里核对输入、输出与跨章角色。
| 符号 | 含义 | 在本章中的角色 |
|---|---|---|
| $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$ | 造成随机游走的度偏倚（degree 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)$ | 一条边参与的三角形数、全图三角形数 | 网络模体加权和平稳分布 |
| $\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。
关键定理卡片
本章只有一个编号定理类对象：Theorem 7.1。其他核心结果是估计量构造和数值比较，不应被包装成没有来源的定理。
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）。详见 外引依赖卡。
关键方法卡片
独立均匀抽样
#- 访问分布：$\pi(v)=1/n$。
- 估计量：式 (7.2)，直接平均 $f(v_{i_s})$。
- 优点：无偏、样本独立、解释简单。
- 代价：均匀访问本身可能很昂贵；稀有子群体需要很大的样本预算。
朴素滚雪球抽样 / 标准随机游走
#- 访问分布：无向图上 $\pi(v)=d(v)/(2m)$。
- 问题：大度节点更常被访问；若大度与研究目标相关，就会产生系统偏差。
- 用途：作为 RDS、MH 和跳跃方法的基线，不应把它的样本均值直接当作均匀节点平均值。
MH 抽样
#- 修正位置：改变转移矩阵 (7.4)，目标平稳分布设为 $1/n$。
- 代价：为保持目标分布，可能频繁留在原节点或重复访问节点。
- 理论状态：Theorem 7.1 的渐近结论由书中外引；有限预算下的方差仍需从 $\sigma_{\mathrm{MH}}^2$ 和实验判断。
RDS
#- 修正位置：保留标准随机游走，估计时除以访问节点的度。
- 两种形式：知道 $m$ 时用 (7.5)；不知道 $m$ 时用不需要总体常数的比率式 (7.6)。
- 理论状态：一致性与 CLT 指向 Avrachenkov et al.（2018b）；本章只给构造和引用。
均匀跳跃与超节点
#- 均匀跳跃：在每对节点间加权，使平稳度由 $d(v)$ 变成 $d(v)+\alpha$。
- 超节点：把少量已知、跨区域的节点合并，利用从超节点出发并首次返回的往返游程。
- 选择逻辑：均匀查询贵但稀有群体重要时，少量“锚点”可能比完全均匀抽样更有效；图 7.3 展示的是一个具体实验场景，不是普遍保证。
公式校勘与补验证
快速阅读可只看证明卡标题与状态；需要严格掌握时，再逐段核验每个等式和外引依赖。
本节是学习层补充。它只闭合可以由定义和基本平稳分布直接检查的短步骤；对书中外引定理和网络模体泛化，不把“知道应当成立”写成证明。
目标：验证式 (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 复核；“定理成立”是原书引用外部结果的陈述，不是本页新完成的证明。
书中原句：三角形估计量之后，原书说“把这一方法用于计数任意网络模体是直接的”，并在 Further Notes 将边函数 / 网络模体函数指向 Avrachenkov et al.（2016c）。
为什么不能直接写成证明：一般网络模体需要逐一指定边或局部结构的权重、相应的加权平稳分布、往返游程观测量、归一化和可能的重叠修正；还需要给出一致性、偏差或方差条件。三角形的“每个三角形贡献 6”不能自动替换成任意网络模体的常数。
当前结论：本章给出三角形的一个具体构造，任意网络模体的一般化在本笔记中保持未闭合；若要补全，应外读 Cooper et al.（2016）及 Avrachenkov et al.（2016c），并逐种网络模体核对假设。
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) 的集合写法）均在译文局部校勘提示中显式登记；没有静默吞掉。
正文隐藏验证与证明状态
先确认原书给到哪里，再检查补充证明使用的条件、证据等级与闭合边界。
| 原文位置 | 触发句/任务 | 分类 | 本笔记处理 |
|---|---|---|---|
| 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” 推广到任意网络模体 | 未闭合推广 | 网络模体未闭合卡 |
| 7.3 | “why uniform sampling might not always perform best” | 设问后由实验回答 | 用 Figure 7.3 的稀有群体/超节点设计解释，不生成额外实验结论 |
| 7.3 | “We observe …” 图读法 | 说明性观察 | 按真实值、中心位置、箱体宽度和方法机制拆读，见 §16 |
巩固迁移
确认术语无歧义、易混点能解释，并知道结论在后续哪里复用。
公式卡片总览
下面逐号列出库存中的 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\}$ 保证估计结果不为负。
数值实验读法
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$ 后三者都靠近真实值。该图再次说明，目标函数是稀有事件指示函数时，方差会成为主要的实践约束。
学习检查表：完成标准
- [ ] 我能从 (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 是书内外引依赖，而不是本章已给证明。
- [ ] 我知道网络模体泛化在本笔记中保持未闭合，没有把“straightforward”当作证明。
- [ ] 我能按真实值、中心位置、箱体宽度和预算读 Figure 7.2–7.5。
进一步阅读（Further Notes 的学习定位）
不必机械按章号前进，选择真正需要解决的问题
每张出口卡说明连接对象及其用途；需要回看时，仍可沿卡内链接返回精确位置。
章末四条 Further Notes 的共同主题是：网络抽样的“访问机制”还可以继续改变。
一次访问同时暴露邻居信息，介于节点均匀抽样与随机游走之间；它减少查询次数，但依赖具体平台是否能提供邻居信息。
并行化可能提高效率，但游走之间的依赖设计、连续时间转移率和方差分析不能被“并行”二字自动解决。
链式推荐中跳过部分访问可降低相邻样本相关性，但会减少可用样本，需要新的预算/方差权衡。
从节点函数推广到边或网络模体，需要新的局部观测和权重设计；本章三角形公式是具体示例，不是通用证明。