概率、线性代数与图论背景工具包

学习层补充。 本页是为阅读本书新增的解释与记号速查，不是原书附录 A 的翻译， 也不增加原书的定理或假设。原书表述、公式和证明以 PDF 为准；附录 A 的独立译文 尚待落地。

怎么用这页

遇到“看懂定义但不会用”的障碍时，只补对应小节，然后回到章节。建议不要把 所有背景一次性背完：第 2 章先需要随机变量和矩阵期望，第 3–5 章再补谱与拉普拉斯， 第 6–7 章再补马尔可夫链、浓缩和抽样估计。

概率工具

期望、方差与条件化

对随机变量 $X$，$\mathbb E[X]$ 是长期平均， $\operatorname{Var}(X)=\mathbb E[(X-\mathbb E X)^2]$ 衡量波动。条件期望 $\mathbb E[X\mid Y]$ 把 $Y$ 已知时的平均写出来。网络模型中，邻接矩阵的每个 元素、节点度和边数都可能是随机变量；写出“给定块标签”还是“对块标签取平均” 会得到不同的量。

总期望和全方差公式是跨层切换的常用接口：

$$ \mathbb E[X]=\mathbb E[\mathbb E[X\mid Y]],\qquad \operatorname{Var}(X)=\mathbb E[\operatorname{Var}(X\mid Y)] \quad +\operatorname{Var}(\mathbb E[X\mid Y]). $$

这里的展示是帮助阅读的记号提醒，不是对原书公式的重新编号。

三个概率界

• Markov 不等式：若 $X\ge 0$，则 $\Pr(X\ge t)\le \mathbb E[X]/t$。它只需要非负性，通常较粗。
• Chebyshev 不等式：若方差有限，则 $\Pr(|X-\mathbb E X|\ge t)\le \operatorname{Var}(X)/t^2$。
• Hoeffding 型浓缩：独立且有界的和偏离其均值的概率按指数下降；使用时必须检查独立性、界和归一化方式。

这些界常被用来把“平均度/边数接近期望”转成高概率陈述。高概率不是确定性 等式，且随着 $n$ 改变的失败概率需要看清楚。

一阶与二阶矩方法

对非负整数值随机变量 $X$，$\mathbb E[X]$ 控制“是否出现至少一个对象”的粗略可能性； 二阶矩 $\mathbb E[X^2]$ 还记录对象之间的相关性。随机图中的孤立点、特定子图或 社区间边数常按一阶/二阶矩估计。若事件之间高度相关，只看期望通常不够。

大数与中心极限定理的阅读姿势

大数定律说明样本均值在适当条件下趋近总体均值；中心极限定理（CLT）说明中心化、 适当缩放后的和在极限上近似正态。第 7 章的游走估计量涉及相关样本，不能直接把 独立同分布样本的 CLT 套上去；其 Theorem 7.1 的假设和引用需单独核对。

图论工具

图、邻接矩阵与度

无向简单图写作 $G=(V,E)$，邻接矩阵 $A$ 满足 $A_{ij}=1$ 当且仅当 $\{i,j\}\in E$； 加权图把 1 换成非负权重。度矩阵 $D$ 是对角矩阵，$D_{ii}=d_i$，因此常见的 随机游走转移矩阵是 $P=D^{-1}A$（存在零度节点时要先处理定义域）。

路径长度、连通分量和最短距离把“网络上相近”变成离散量。断开图时，无穷距离、 零度和多个平稳分布会影响中心性和抽样估计，不能用连通图公式无条件替换。

拉普拉斯与能量

组合拉普拉斯为 $L=D-A$。对向量 $f$，无向图上有

$$ f^{\mathsf T}Lf=\frac12\sum_{i,j}A_{ij}(f_i-f_j)^2, $$

所以 $L$ 衡量相邻节点取值的粗糙程度；常数向量在每个连通分量上产生零能量。 归一化拉普拉斯会引入 $D^{-1/2}$，随机游走和谱聚类中使用的归一化形式不必相同， 应以章节自己的定义为准。

指示向量与切割

一个社区 $S\subseteq V$ 可用指示向量 $1_S$ 表示。把 $1_S$ 与 $L$、归一化矩阵或 模块度矩阵相乘，可把边界大小、体积和社区间连接写成二次型。谱松弛的核心是 先放宽“向量必须是离散指示向量”的约束，再用特征向量恢复离散划分；松弛解不是 自动等于原组合优化问题的最优解。

线性代数工具

对称、半正定与特征值

实对称矩阵可正交对角化：$M=U\Lambda U^{\mathsf T}$。若所有特征值非负，则 $M$ 半正定（PSD），即 $x^{\mathsf T}Mx\ge0$；若所有特征值严格为正，则为正定。 图拉普拉斯是 PSD，因此它的最小特征值和零空间编码连通分量；这一事实是谱方法 与图上能量解释的共同支点。

范数与扰动

常见的矩阵范数包括谱/算子范数 $\|M\|_{\mathrm{op}}$（最大奇异值）和 Frobenius 范数 $\|M\|_F=(\sum_{ij}M_{ij}^2)^{1/2}$。它们衡量的误差不同：谱范数控制 对任意单位向量的最大作用，Frobenius 范数累积所有元素误差。

当矩阵被低秩项扰动时，特征值和特征向量可能移动；小范数扰动并不意味着所有 特征向量都稳定，稳定性还依赖谱间隙。附录 B 的 rank-2 perturbation 与第 5 章 证明正是在更具体的约束下使用这类工具。

Courant–Fisher 视角

对实对称矩阵，按升序排列的特征值可以通过 Rayleigh 商在子空间上的极值刻画。 这把“找特征向量”转成“最小化/最大化二次型”，也是谱聚类、拉普拉斯正则化和 半监督估计之间的共同语言。使用 min-max 表述时要确认特征值排序、约束子空间和 是否已归一化。

图上微积分的最低记号

把每条有向边看成从一个端点到另一个端点，可用一个 incidence/梯度算子把节点 函数 $f$ 变成边差值；其伴随算子把边流汇总回节点，得到散度。梯度与散度的组合 给出图拉普拉斯。不同章节可能在边定向、权重和内积上采用不同约定，所以这里 只提供关系图，不替代章节的符号定义。

与各单元的最低先修

待落地边界

本页有意只做最低工具包。附录 A 的章节结构包括概率、图论、线性代数和图上微积分， 但其正式翻译、对象级证明核查和稳定章节锚点尚待落地。若本页和未来附录 A 在符号 或细节上出现差异，以 PDF 版面和附录 A 的正式译文为准，并在此页保留“学习层补充”标记。