第 03 章学习笔记：网络中心性指标
第 03 章学习笔记：网络中心性指标
配套译文：
内部译文（已落盘；术语表 sec-3- 锚点与译文一致）。 本章是应用导向章节，证明负担全书最轻：编号语义对象只有 Theorem 3.1 与 Corollary 3.1，且原书均不证；真正的密度在定义——26 个编号公式、五族指标、四幅同图对比。因此本笔记的重心不是证明，而是两件事：一张"什么数据结构 / 什么问题选什么指标"的五族选择地图（§5），以及公理化比较的逐格复核*（§11——Table 3.1 的格子原书默认读者默会）。Theorem 3.1 的补证只有两步线性代数（§10），不要跳过。
1. 一句话定位
本章回答第 1 章 1.3.2 提出的问题——"网络中哪些节点最重要？"：答案取决于你把"重要"翻译成哪种数学语义，于是 3.1 节按语义把指标分成五族（离大家近 / 被重要者背书 / 随机游走容易到达 / 流量咽喉 / 对联盟的边际贡献），3.2 节用 Boldi–Vigna 三条公理做横向淘汰测试（常用指标中只有调和中心性全过），3.3 节落到应用——其中 Personalized PageRank 的半监督分类用法（3.3.2）是第 5 章的直接先导，边介数删边法（3.3.3）指向第 4 章社区检测。
2. 本章导读
本章按"五族定义（同图对比）→ 公理比较 → 应用"三步推进：
- 章首（印刷页 45）：中心性指标 = 定义在节点上的实值函数，用于排序；不同的重要性判据必然导出不同的指标，所以本章是"地图"而非"圣经"。脚注 1 区分 index 与 measure 的术语用法。
- 3.1.1 距离类（印刷页 46–47）：度、接近中心性 (3.1)、调和中心性。关键动作：closeness 在不连通图因距离为 $\infty$ 而失效，交换"求和"与"取倒数"的顺序即得 harmonic——这个"换序"思想在本章反复出现。Figure 3.1 同图对比：度只看局部、closeness 抬高两簇交界处的节点、harmonic 两者兼顾。
- 3.1.2 谱类（印刷页 47–53，本章最长节）：统一于特征值问题 $xM=\lambda x$ (3.2)。五个成员：邻接谱中心性（Landau 1895 年用于国际象棋评分，最古老）、Seeley 指数 $\sigma=\sigma P$ (3.3)（无向图上退化为与度成正比）、PageRank (3.4)(3.5) 及其对多强连通分量的 Seeley 推广 (3.6)(3.7)、节点相关重启的 OT/LR-PPR (3.11)(3.12) 与 direct–reverse 对偶（Theorem 3.1、Corollary 3.1）、Katz 指数 (3.17)(3.18)、HITS（$A^{T}A$ 主特征向量）。本节是全书 PageRank / 随机游走语言的系统发源地，第 4、5 章都在引用这里的记号。
- 3.1.3 首中时间类（印刷页 53–56）：信息不只沿最短路传播时，"近"用期望首中时间 $E_i[T_j]$ (3.19) 度量。关键动作：$E_i[T_j]\ne E_j[T_i]$ 不对称，于是有 (3.20) 与 (3.21) 两个版本；用通勤时间 / 有效电阻 $r_{ij}$ 对称化得 (3.22)，附带好处是有效电阻本身是图上的度量；带重启版本 (3.23) 处理不连通图并改善条件数。
- 3.1.4 介数类（印刷页 56–59）："瓶颈型"重要性。最短路介数（Freeman 1977）假设信息只走最短路；最大流介数 (3.24) 与电流介数 (3.25)(3.26) 把它放宽到全部路径——后者把图当电网络，解 Poisson 方程 $L\phi=b$。边介数（对边而非点计数）是 3.3.3 Girvan–Newman 社区检测的弹药。
- 3.1.5 博弈类（印刷页 59–60）：用合作博弈公理化"贡献"：Myerson 值由分量效率与加删边公平两条公理唯一刻画；取路径折扣特征函数（长度 $k$ 简单路径贡献 $\delta^k$）可得可计算显式，兼有介数特征与 PageRank/Katz 式路径折扣。
- 3.2 公理化比较（印刷页 60–62）：Boldi–Vigna 三公理（size / density / score-monotonicity）+ Table 3.1。结论醒目：只有调和中心性三公理全过；但原书明确告诫"不满足某公理的指标在该公理未刻画的情形下仍然有用"——公理是否决性测试，不是排名。
- 3.3 应用（印刷页 62–65）：3.3.1 文献计量（引用数 = 入度；PageRank 能挖出被引少但影响大的 "scientific gems"）；3.3.2 半监督学习（以 PPR 作点–类相似度，argmax 分类）；3.3.3 社区检测（反复删除边介数最大的边 = Girvan–Newman；PageRank 找社区代表点 + PPR 归属）；3.3.4 体育评分、网络鲁棒性、推荐系统、NLP。
- Further Notes（印刷页 65）：5 条文献指引，无习题。解读见本页 §16。
3. 本页使用方式
按你在正文中最可能卡住的位置直接跳转：
- 26 个编号公式看不过来，先抓哪几个？ → §15 公式卡片 F1–F8 按用途归并展示 18 式（(3.14)(3.15) 在定理卡 T1 内，(3.2)(3.3)(3.9)(3.10)(3.18) 见译文对应处）；§4 主线表 给出读序。
- 面对一个真实数据集，不知道该用哪个指标 → 这就是本章的"真实考点"。§5 概念地图 是一张选择地图：先定重要性语义，再查图的条件（有向？连通？），最后落在具体指标；§14 易混点 第 1、7 条是速查版。
- 邻接谱 / Seeley / PageRank / Katz 四个"谱"指标分不清 → §14 第 2 条：区别只在矩阵 $M$ 的选择和"背书是否被出度摊薄"。
- Theorem 3.1 的式 (3.13) 一堆 $K_i(C)$ 不知所云 → 先读 §9 卡片 T1 的"用途"行（它说：无向图上"从 $i$ 看 $j$"与"从 $j$ 看 $i$"的 PPR 只差一个度数因子），再读 §10 proof-theorem-3-1——补证只有两步：把 (3.13) 归约为一个矩阵的对称性，再验证该矩阵对称。
- Table 3.1 的格子（为什么 closeness 三公理全不过、为什么 harmonic 全过）原书不解释 → §11 proof-check-table-3-1-axiom-cells 逐格补验 7 个代表性格子，每格都是几行计算。
- 只想知道本章在全书的位置 → §4 的"后续用途"列 + §18 后续衔接。
4. 本章主线
| 推进层 | 要解决的问题 | 关键转折 | 后续用途 |
|---|---|---|---|
| 3.1.1 距离类 | 最朴素的"重要 = 连接多 / 离大家近" | closeness 在不连通图失效（$\sum d=\infty$）⇒ 换序得 harmonic（$\infty^{-1}=0$） | harmonic 是 3.2 公理测试唯一全胜者（Table 3.1 基准行）；不连通图的"换序修法"在 3.1.3 复用 |
| 3.1.2 谱类 | "被重要者指向"的递归背书如何定义与计算 | Seeley/PageRank 把背书按出度摊薄，Katz 给全额背书——这是谱类内部的第一条分界线；PageRank 的重启既修复不连通又防"沉陷"；节点相关重启引出 direct–reverse 对偶（Thm 3.1） | 全书 PageRank/PPR 语言发源地：3.3.2 SSL 相似度、Ch4 谱聚类共用特征向量语言、Ch5 Generalized Laplacian 的 $\sigma=0$ 端即 PPR 闭式 |
| 3.1.3 首中时间类 | 信息沿所有路径传播时"近"怎么定义 | $E_i[T_j]\ne E_j[T_i]$ 不对称 ⇒ 用通勤时间/有效电阻对称化 (3.22)，附带得到图上的度量 | Ch5 Label Propagation 的 hitting-time 解释（Ch5 笔记 §7 第 2 条）的工具箱；带重启版 (3.23) 与 PageRank 正则化同源 |
| 3.1.4 介数类 | "瓶颈 / 桥梁"型重要性 | 最短路假设太强 ⇒ 最大流（容量视角）与电流（电网络，$L\phi=b$）两种全路径推广；对边计数得边介数 | 3.3.3 Girvan–Newman 社区检测（反复删边介数最大的边）→ Ch4 |
| 3.1.5 博弈类 | 用合作博弈公理化"贡献" | Myerson 值两公理唯一刻画 + 路径折扣特征函数 ⇒ 可算显式，兼具介数与路径折扣特征 | Further Notes 群中心性的方法论入口 |
| 3.2–3.3 比较与应用 | 指标太多怎么选 | 三公理淘汰测试：只有 harmonic 全过；但公理是否决测试不是排名——按任务选指标 | Table 3.1 是选指标的否决清单；3.3.2 / 3.3.3 分别对接 Ch5 / Ch4 |
5. 本章学习路线 / 概念地图（五族选择地图）
读法：这是一个决策流程，不是分类树。自上而下：先回答"什么算重要"（语义），再核对"图满足什么条件"（可行性），最后落到具体指标；底部两行是所有指标共用的"质检"与"出口"。
起点：你的"重要性"是什么意思？图是什么样？
五种语义 = 五族；每族先查适用条件（连通性 / 有向性 / 加权），再选成员。
五种语义 = 五族；每族先查适用条件（连通性 / 有向性 / 加权），再选成员。
① 距离类
重要 = 离所有人近
度 / closeness (3.1) / harmonic
条件：closeness 需（强）连通；harmonic 任意图
计算：最短路
重要 = 离所有人近
度 / closeness (3.1) / harmonic
条件：closeness 需（强）连通；harmonic 任意图
计算：最短路
② 谱类
重要 = 被重要者指向
邻接谱 / Seeley (3.3) / PageRank (3.4) / Katz (3.17) / HITS
条件：强连通，或 PageRank 式重启；Katz 需 $\beta \lt \lambda(A)^{-1}$
计算：特征向量 / 线性系统
重要 = 被重要者指向
邻接谱 / Seeley (3.3) / PageRank (3.4) / Katz (3.17) / HITS
条件：强连通，或 PageRank 式重启；Katz 需 $\beta \lt \lambda(A)^{-1}$
计算：特征向量 / 线性系统
③ 首中时间类
重要 = 随机游走从各处容易到达
(3.20) / (3.21) / 对称化 (3.22) / 带重启 (3.23)
条件：连通，或用带重启版
计算：$n$ 个 Taboo 线性系统
重要 = 随机游走从各处容易到达
(3.20) / (3.21) / 对称化 (3.22) / 带重启 (3.23)
条件：连通，或用带重启版
计算：$n$ 个 Taboo 线性系统
④ 介数类
重要 = 流量咽喉
最短路 / 最大流 (3.24) / 电流 (3.25)(3.26)；边介数
条件：（强）连通；电流仅无向
计算：最短路计数 / LP / $L\phi=b$
重要 = 流量咽喉
最短路 / 最大流 (3.24) / 电流 (3.25)(3.26)；边介数
条件：（强）连通；电流仅无向
计算：最短路计数 / LP / $L\phi=b$
⑤ 博弈类
重要 = 对联盟的边际贡献
Shapley / Myerson 值 + 路径折扣特征函数
计算：简单路径计数 $a_k^{(i)}(G)$
重要 = 对联盟的边际贡献
Shapley / Myerson 值 + 路径折扣特征函数
计算：简单路径计数 $a_k^{(i)}(G)$
质检（3.2）：Boldi–Vigna 三公理（size / density / score-monotonicity）是否决测试
Table 3.1：只有 harmonic 全过；不满足公理 ≠ 无用（PageRank 不过 size，仍是 Web 标配）
Table 3.1：只有 harmonic 全过；不满足公理 ≠ 无用（PageRank 不过 size，仍是 Web 标配）
出口（3.3）：文献计量（入度 → PageRank 找 gems）· SSL（3.3.2，PPR 相似度 → Ch5） · 社区检测（3.3.3，边介数 / PPR → Ch4） · 鲁棒性 / 推荐 / NLP
6. 分层阅读路线
- 第一遍（主线，约 60 分钟）：章首 → 3.1.1 全节（配 Figure 3.1）→ 3.1.2 只读 PageRank 段（式 (3.4)(3.5) 与"谱形式改写"那一段）→ 3.1.4 最短路介数一段 → 3.2 三公理 + Table 3.1 → 3.3.2。目标：能独立画出 §5 的选择地图，并能用一句话说清每族的"重要性语义"。
- 第二遍（精读，约 2 小时）：3.1.2 全节——多分量 Seeley 推广 (3.6)(3.7)、节点相关重启 (3.8)、OT/LR-PPR (3.11)(3.12)、Theorem 3.1 / Corollary 3.1（配本页 §10）；然后 3.1.3（重点是有效电阻对称化 (3.22)）与 3.1.5（Myerson 值两公理 + 路径折扣）；最后配 §11 逐格复核 Table 3.1。
- 第三遍（与应用挂钩）：3.3 全节 + 逐图回看四个 Comparison 段（Figure 3.1–3.4）：每张图回答"这个指标在同一图上把谁抬高了、为什么"；再想一个你熟悉的数据集，用 §5 地图走一遍决策流程。
- 专题回看：学 Ch5 Label Propagation 时回看 3.1.3 与 3.3.2（Ch5 笔记 §7 第 2 条已预留对接）；学 Ch4 谱聚类时回看 3.1.2 的特征值语言；读 Gleich (2015) PageRank 综述时以 §15 F2/F4 为入口。
7. 初学者背景补充
本章默认读者熟悉以下四件工具；它们不出现在原书正文，但每一个都被反复调用：
- Neumann 级数与次随机矩阵：$c<1$ 且 $P$ 行随机时 $\lVert cP\rVert<1$，故 $$[I-cP]^{-1}=\sum_{t\ge0}c^{t}P^{t}.$$ 这是本章一切显式矩阵公式的代数引擎：(3.5)(3.11)(3.12)(3.19)(3.23) 全是 $[I-\cdot]^{-1}$ 形。读这些公式时心里展开成级数，"所有路径按 $c^t$ 折扣求和"的图景就自动出现。同一事实在 Ch5 笔记 §7 第 2 条以"次随机矩阵"语言再次出现。
- 马尔可夫链平稳分布与返回时间：不可约非周期有限链有唯一平稳分布 $\sigma=\sigma P$；Kac 公式 $E_i[T_i]=1/\sigma_i$（Seeley 指数的第二种解释）；遍历定理保证长期访问频率收敛到 $\sigma$——OT-PPR 的定义 (3.9) 合法靠的就是它。
- Perron–Frobenius 定理：非负不可约矩阵有唯一最大正特征值，对应分量全正的特征向量（PF 特征向量）。它是"取最大特征值对应特征向量作为中心性"这一操作的全部合法性来源；Katz 指数的参数限制 $\beta<\lambda(A)^{-1}$（保证 (3.17) 的级数收敛）也直接来自它。
- 图拉普拉斯与电网络：$L=D-A$ 满足 $L\underline 1=0$，故 Poisson 方程 $L\phi=b$ (3.25) 的解只定到加性常数（"接地"一个节点后唯一）；Kirchhoff 电流定律 + Ohm 定律逐节点写出就是 $L\phi=b$。有效电阻 $r_{ij}=(E_i[T_j]+E_j[T_i])/(2m)$ 是图上的度量（三角不等式成立），这是 (3.22) "附带好处"的严格内容。博弈类一节需要的合作博弈背景只有一句：Shapley 值 = 按节点加入联盟的边际贡献对所有加入顺序取平均。
8. 核心对象与符号表
| 符号 | 含义 | 本章出处 | 在后续章节的角色 |
|---|---|---|---|
| $A$，$D$，$P=D^{-1}A$ | 邻接矩阵、度对角阵、随机游走转移矩阵 | 3.1.2 | 与 Ch2 矩阵记号一致；Ch4 谱聚类、Ch5 全部方法的公共记号 |
| $d(v,u)$ | $v$ 到 $u$ 的最短路长度 | 3.1.1 | closeness / harmonic 的输入 |
| $\pi$，$\nu$，$c$ | PageRank 平稳分布、重启（个性化）分布、续走概率 | (3.4)(3.5) | Ch5 GL 方法 $\sigma=0$ 端；PPR 相似度（3.3.2） |
| $C=\mathrm{diag}(c(i))$ | 节点相关续走概率对角阵 | (3.8) | Theorem 3.1 的条件与 $K_i(C)$ 的定义 (3.14) |
| $\sigma$ | Seeley 指数（随机游走平稳分布） | (3.3) | 无向图上 $\sigma_i\propto d_i$；多分量推广 (3.7) |
| $\kappa$，$\beta$，$\lambda(A)$ | Katz 指数、几何折扣参数、PF 特征值 | (3.17)(3.18) | 参数限制 $\beta<\lambda(A)^{-1}$；Estrada 变体的母公式 |
| $E_i[T_j]$，$P_{-j}$ | $i$ 到 $j$ 的期望首中时间、Taboo 矩阵（删第 $j$ 行第 $j$ 列） | (3.19) | Ch5 LP 失效分析（首中时间 vs 混合时间） |
| $r_{ij}$，$m$ | 有效电阻（通勤时间 $/(2m)$）、边数（总权） | (3.22) | 对称化的首中时间中心性；图上的度量 |
| $\sigma_{st}$，$\sigma_{st}(v)$ | $s$–$t$ 最短路数、其中过 $v$ 者 | 3.1.4 | 最短路介数与边介数（→ Ch4 Girvan–Newman） |
| $m_{st}$，$m_{st}(v)$ | $s$–$t$ 最大流及过 $v$ 部分 | (3.24) | 加权网络介数 |
| $L$，$\phi$，$\tau_{st}(v)$ | 图拉普拉斯、电位向量、节点吞吐量 | (3.25)(3.26) | $L$ 与 Ch4 谱方法、Ch5 拉普拉斯方法是同一矩阵 |
| $v(\cdot)$，$Y_i(v,G)$，$\delta$ | 特征函数、Myerson 分配、路径折扣因子 | 3.1.5 | 群中心性（Further Notes）的方法入口 |
9. 关键定理卡片
本章只有 2 个编号对象 + 3 条命名公理。定理卡片按 条件 / 结论 / 用途 / 证明入口 组织；公理卡片附带"淘汰谁"。
卡片 T1：Theorem 3.1（direct–reverse OT-PPR 对偶，Avrachenkov et al., 2014a）
- 条件：无向图（$A^{T}=A$）、$C=\mathrm{diag}(c(i))$ 各分量非零（且 $[I-CP]$ 可逆，如 $0<c(i)<1$ 时自动成立）；$\pi_j(i)$ 为以 $i$ 为个性化节点的 OT-PPR (3.11)。
- 结论： $$\frac{d_i}{c_iK_i(C)}\,\pi_j(i)=\frac{d_j}{c_jK_j(C)}\,\pi_i(j),\qquad K_i(C)=\frac{1}{e_i^{T}[I-CP]^{-1}\underline 1},\tag{3.13,3.14}$$ 其中 $K_i(C)^{-1}=E_i[\text{两次重启之间的期望步数}]$ (3.15)。
- 用途：无向图上 PPR 的双向不对称性被完全归约为度数与重启强度——"$i$ 眼中的 $j$"和"$j$ 眼中的 $i$"只差一个可算因子；它是 3.3.2 用 PPR 做相似度时的理论锚点，也给出 (3.11) 的更新方程（renewal）解释。
- 证明入口：proof-theorem-3-1（原书不证，引 Avrachenkov et al., 2014a；本笔记补证，两步线性代数）。
卡片 T2：Corollary 3.1（标准 PageRank 的对偶）
- 条件：$A^{T}=A$ 且 $c_i=c\ \forall i$（标准 PageRank）。
- 结论：$d_i\pi_j(i)=d_j\pi_i(j)$ (3.16)——双向 PPR 之比恰等于度数之比。
- 用途：PPR 相似度的"对称化依据"：无向图上 $\pi_j(i)$ 与 $\pi_i(j)$ 的偏离完全由度解释，做归一化 $\pi_j(i)/d_j$ 即得对称相似度。
- 证明入口：proof-corollary-3-1（原书仅称"由 (3.13) 直接化简"，本笔记补全该一步）。
公理卡片 A1：Size axiom（规模公理）
- 内容（Boldi & Vigna, 2014）：在 $G_{k,p}$（一个 $k$-团 + 一个有向 $p$-环，互不相连）上，固定 $k$ 时环足够大则环节点应比团节点更重要；固定 $p$ 时团足够大则团节点应更重要。直觉：大而稀疏的社区成员最终应胜过小而密的社区成员，反之亦然。
- 淘汰谁：closeness、Seeley、PageRank 两方向全失败（"no"）；degree、Katz、HITS 只满足团方向（"only k"）；betweenness 只满足环方向（"only p"）。逐格验证见 §11。
公理卡片 A2：Density axiom（密度公理）
- 内容：在 $D_{k,p}$（$G_{k,p}$ 加一条双向桥 $x$–$y$，$x$ 在团、$y$ 在环）上取 $k=p$，桥两端中密侧端点 $x$ 的中心性应严格大于 $y$。直觉：同等规模下，更密社区的成员更重要。
- 淘汰谁：closeness（桥两端严格平局，见 §11 第 (c) 格）与 betweenness。
公理卡片 A3：Score-monotonicity axiom（得分单调性公理）
- 内容：任意图上加一条新有向边 $x\to y$，$y$ 的中心性必上升。直觉：被多指一次永远不吃亏。
- 淘汰谁：closeness、Seeley、betweenness、HITS。注意 harmonic 满足它只有两行证明（§11 第 (e) 格）——这正是"换序"带来的稳健性。
10. 关键定理完整证明
本章原书不给任何证明：Theorem 3.1 外引出处、Corollary 3.1 只称"由 (3.13) 直接化简"。前者补证为短线性代数（可独立核验，非外引资料的搬运），后者补全化简步骤。
完整证明（原书不证，笔记补证）Theorem 3.1（direct–reverse OT-PPR 对偶，式 (3.13)）
状态：完整证明已按当前笔记标准给出闭合推导。
**原书态度**：定理署名 (Avrachenkov et al., 2014a)，原书未给证明。以下证明是本笔记补证（纯线性代数，可独立核验）；外部参考：Avrachenkov, Litvak, Nemirovsky, Smirnova & Sokol (2014a)，该文同时给出 LR-PPR 版本的讨论。
**证明目标**：设 $A^{T}=A$，$C=\mathrm{diag}(c(i))$ 满足 $c(i)>0$ 且 $[I-CP]$ 可逆（$0<c(i)<1$ 时 $\lVert CP\rVert_\infty<1$，可逆自动成立）。记 $\pi(i)=K_i(C)\,e_i^{T}[I-CP]^{-1}$（即 (3.11) 取 $\nu=e_i^{T}$），则
$$\frac{d_i}{c_iK_i(C)}\,\pi_j(i)=\frac{d_j}{c_jK_j(C)}\,\pi_i(j).$$
**依赖工具**：OT-PPR 显式 (3.11) 与 $K_i(C)$ 定义 (3.14)；$P=D^{-1}A$；对角矩阵两两可交换；$A^{T}=A$。
**证明思路**：把 $\pi_j(i)=K_i(C)\,e_i^{T}[I-CP]^{-1}e_j$ 代入后，$K_i(C)$ 恰好消去——(3.13) 等价于矩阵 $DC^{-1}[I-CP]^{-1}$ 的**对称性**。对称性不好直接看，就取逆：对称可逆矩阵的逆仍对称，而逆矩阵 $CD^{-1}-CD^{-1}ACD^{-1}$ 的对称性只是"对角阵可交换 + $A^{T}=A$"的两行推论。
**完整证明**：
**第 1 步（消去 $K_i(C)$）**：由 (3.11) 取 $\nu=e_i^{T}$，
$$\pi_j(i)=\frac{e_i^{T}[I-CP]^{-1}e_j}{e_i^{T}[I-CP]^{-1}\underline 1}=K_i(C)\,e_i^{T}[I-CP]^{-1}e_j,$$
其中第二个等号即 (3.14)。代入 (3.13) 左侧：
$$\frac{d_i}{c_iK_i(C)}\,\pi_j(i)=\frac{d_i}{c_i}\,e_i^{T}[I-CP]^{-1}e_j=e_i^{T}\,DC^{-1}[I-CP]^{-1}e_j.$$
同理右侧等于 $e_j^{T}DC^{-1}[I-CP]^{-1}e_i$。记 $M:=DC^{-1}[I-CP]^{-1}$，则 (3.13) $\Longleftrightarrow$ $e_i^{T}Me_j=e_j^{T}Me_i$ 对所有 $i,j$ 成立 $\Longleftrightarrow$ **$M$ 对称**。
**第 2 步（$M$ 对称）**：$D,C$ 为对角阵且 $c(i)>0$，故 $DC^{-1}$ 可逆，于是
$$M=DC^{-1}[I-CP]^{-1}=\big[(I-CP)\,CD^{-1}\big]^{-1}=:N^{-1},\qquad N=CD^{-1}-CP\,CD^{-1}.$$
代入 $P=D^{-1}A$：
$$N=CD^{-1}-CD^{-1}A\,CD^{-1}.$$
计算转置（对角阵自转置且两两可交换，$A^{T}=A$）：
$$N^{T}=D^{-1}C-D^{-1}C\,A^{T}CD^{-1}=CD^{-1}-CD^{-1}ACD^{-1}=N.$$
故 $N$ 对称；$N$ 可逆（题设 $[I-CP]$ 可逆），对称可逆矩阵的逆仍对称，故 $M=N^{-1}$ 对称。由第 1 步，(3.13) 成立。∎
**闭合检查**：结论用到的假设逐一对账——$A^{T}=A$ 用在 $N^{T}=N$（有向图上 $M$ 一般不对称，对偶失效，与定理所设条件一致）；$C>0$ 保证 $C^{-1}$ 存在；$[I-CP]$ 可逆保证 (3.11) 与取逆合法。最后一行确实回到 (3.13) 原式，无遗漏因子。
**直觉注记**（帮助记忆，非证明的一部分）：$K_i(C)^{-1}=e_i^{T}[I-CP]^{-1}\underline 1=\sum_{t\ge0}P_i(\text{前 }t\text{ 步未重启})=E_i[\text{重启前的期望步数}]$（即 (3.15)），因为 $(CP)^t$ 的 $(i,j)$ 元正是"从 $i$ 出发 $t$ 步内未重启且位于 $j$"的概率。于是 (3.13) 读作：双向 PPR 之比 = 度数之比经"重启节奏"修正。
> 校勘提示：①原书本节行文 "let the random walk restart with probability $c(i)$" 与式 (3.8) $\tilde P=CD^{-1}A+(I-C)\underline 1\nu$ 的代数结构不一致——按公式，$c(i)$ 是**继续沿图走**的概率（重启概率为 $1-c(i)$）；此读法与 Corollary 3.1 "$c_i=c\ \forall i$ 即标准 PageRank"（续走概率 $c$）以及 (3.15) 的期望步数 $1/(1-c)$ 均一致，阅读时以公式为准。②原书 (3.15) 把 $K_i(C)$ 排为 $K_i(A)$，系排版错误，应为 $K_i(C)^{-1}=E_i[\#\text{steps before restart}]$。
完整证明Corollary 3.1（标准 PageRank 的 direct–reverse 对偶，式 (3.16)）
状态：完整证明已按当前笔记标准给出闭合推导。
**证明目标**：$A^{T}=A$ 且 $c_i=c\ \forall i$ 时，(3.13) 化简为 $d_i\pi_j(i)=d_j\pi_i(j)$。
**依赖工具**：Theorem 3.1（[本页证明](#proof-theorem-3-1)）；$P\underline 1=\underline 1$（行随机性）。
**完整证明**：$c_i=c$ 时 $C=cI$。由 $P\underline 1=\underline 1$，
$$(I-cP)\underline 1=(1-c)\underline 1\quad\Longrightarrow\quad[I-cP]^{-1}\underline 1=\frac{1}{1-c}\underline 1,$$
故对每个 $i$，
$$e_i^{T}[I-cP]^{-1}\underline 1=\frac{1}{1-c}\quad\Longrightarrow\quad K_i(cI)=1-c,$$
与 $i$ 无关。代入 (3.13)：两边分母同为 $c(1-c)$，约去即得 $d_i\pi_j(i)=d_j\pi_i(j)$。∎
**闭合检查**：化简只用"K_i 与 i 无关"，而该事实完全来自行随机性——这正是标准 PageRank（各点续走概率相同）比节点相关版本简洁的原因；(3.16) 与 (3.13) 的量纲一致（两侧均为"度 × PPR"），无遗漏常数。
11. 正文隐藏验证补全
清单 §6 扫描结论：本章没有"留给读者证明"的真正留白；12 处触发句中 11 处为修辞性或图注引导，唯一实质半任务是 Table 3.1 的逐格验证（原书给了结论表，把"为什么"留给读者默会）。登记如下：
| # | 原句（意译） | 文件页 | 判断 | 处理 |
|---|---|---|---|---|
| 1 | "closeness 向有向网络的形式推广相当直接，但缺乏（强）连通性带来问题" | 55 | 修辞性（轻量提示） | §14 第 4 条一句话说明 |
| 2 | "Table 3.1 汇总了上述公理对最常用中心性指标的验证" | 71 | 半任务：逐格验证留给读者 | proof-check-table-3-1-axiom-cells |
| 3 | "有趣的是……只有调和中心性满足全部三条公理" | 71 | 修辞性（结论句） | 同上卡的副产物 |
| 4–12 | "We try to overview…"、"We observe that…"（图 3.1–3.4 观察引导）、脚注 2 等 | 55–72 | 修辞性 / 图读法引导 | 不设卡；图读法已并入 §6 第三遍路线 |
隐藏验证补全Table 3.1 公理验证：7 个代表性格子逐格补验
状态：证明骨架保留主要推导链，后续可补常数、边界或技术细节。
**任务**：Table 3.1（Boldi & Vigna, 2014）给出 8 指标 × 3 公理的结论表，原书未逐格论证。下面补验 7 个代表性格子，覆盖三条公理与 "only k" / "only p" 两种部分满足标注。记号：$G_{k,p}$ = $k$-团（双向边）与有向 $p$-环的不相交并；$D_{k,p}$ = $G_{k,p}$ 加双向桥 $x$–$y$（$x$ 在团、$y$ 在环）；$n=k+p$；团内点记 $u$，环上点记 $v$。
**Size 公理四格**
**(a) Degree × size = "only k"**：团内点度 $=k-1$（双向口径入度、出度各 $k-1$）；有向环上每点入度、出度恒为 $1$（总度恒为 $2$），与 $p$ 无关。团方向：固定 $p$，取 $k\ge3$ 则团节点度 $k-1\ge2>1$（任一计数口径下均严格大于环节点度），满足；环方向：固定 $k\ge3$ 时环节点度恒小于 $k-1$，无论 $p$ 多大都不可能反超——**环方向结构性失败**，故 "only k"。
**(b) Closeness × size = "no"**：$G_{k,p}$ 不连通，任意节点到另一分量节点的距离为 $\infty$，故 (3.1) 的分母 $\sum_v d(v,u)$ 对**每个**节点发散，closeness 全为 $0$——任何严格不等式都无从谈起，两方向同时失败。（本格同时说明：closeness 的公理化讨论实质上限定在强连通图上，见 §14 第 4 条。）
**(g) Harmonic × size = "yes"（两个方向）**：约定 $\infty^{-1}=0$ 后跨分量项全消失。团内点：$h(u)=\frac1{n-1}\sum_{w\ne u}1/d(w,u)=\frac{k-1}{n-1}$（团内 $k-1$ 个距离为 1 的项）。环上点：有向环上到 $v$ 距离为 $d$ 的节点恰有一个（$d=1,\dots,p-1$），故
$$h(v)=\frac1{n-1}\sum_{d=1}^{p-1}\frac1d=\frac{H_{p-1}}{n-1},\qquad H_{p-1}=\text{调和数}.$$
比较归结为 $k-1$ 对 $H_{p-1}$：固定 $k$ 令 $p\to\infty$，$H_{p-1}\to\infty$ ⇒ 环方向成立；固定 $p$ 令 $k\to\infty$ ⇒ 团方向成立。两方向全过。
**(f) Betweenness × size = "only p"**：团内任意两节点有直达边，最短路不经过任何中间点 ⇒ 团内点介数恒为 $0$。有向 $p$-环（$p\ge3$）上取 $v$ 的前驱 $s$ 与后继 $t$：$s$ 到 $t$ 的唯一有向路径为 $s\to v\to t$，即最短路径经过 $v$，贡献 $\sigma_{st}(v)/\sigma_{st}=1$ ⇒ 环节点介数 $>0$。于是环方向（固定 $k$，取 $p\ge3$ 即反超 $0$）恒成立；团方向要求团节点介数严格大于环节点，但团节点介数永远是 $0$——结构性失败，故 "only p"。（归一化因子 $1/((n-1)(n-2))$ 对所有点相同，不影响比较。）
**Density 公理两格（$k=p$）**
**(c) Closeness × density = "no"**：$D_{k,p}$ 强连通，closeness 有定义。记 $S_x=\sum_v d(v,x)$、$S_y=\sum_v d(v,y)$。团内非 $x$ 点到 $x$ 距离 $1$、到 $y$ 距离 $2$（经桥）；环节点 $z$ 到 $y$ 距离 $d(z,y)$、到 $x$ 距离 $d(z,y)+1$。逐项作差：
$$S_x-S_y=\big[(k-1)+1+(p-1)\big]-\big[2(k-1)+1\big]=p-k.$$
$k=p$ 时 $S_x=S_y$——桥两端**严格平局**，"严格大于"永不成立，故密度公理失败（对所有 $k=p$ 同时失败，不只是个别参数）。
**(d) Harmonic × density = "yes"**：同样逐项计算（桥两侧距离同上），
$$(n-1)\big(h(x)-h(y)\big)=\underbrace{(k-1)-\tfrac{k-1}2}_{\text{团侧}}+\underbrace{\sum_{d=1}^{p-1}\Big(\tfrac1{d+1}-\tfrac1d\Big)}_{\text{环侧，望远镜}}=\frac{k-1}2-\Big(1-\frac1p\Big).$$
$k=p$ 时右端 $=\frac{k-1}2-1+\frac1k$：$k\ge3$ 时严格为正（$k=3$ 时 $=1/3$）；$k=p=2$ 的退化情形（"团"为单边、环长为 2）恰为平局，公理的非退化范围 $k=p\ge3$ 内严格成立。
**Score-monotonicity 公理一格**
**(e) Harmonic × score-monotonicity = "yes"**：在任意图上加新边 $x\to y$。对任意 $v$，$d(v,y)$ 只能减小或不变，故每项 $1/d(v,y)$ 弱增（$\infty^{-1}=0$ 的项若变有限则严格增）；特别地 $d(x,y)$ 由 $\ge2$（或 $\infty$）降为 $1$，对应项严格增。总和严格增 ⇒ $h(y)$ 严格上升。两行证毕——注意同一论证对 closeness **不适用**：(3.1) 先求和，不连通时分母中的 $\infty$ 项使指标恒 $0$，加边前后的比较在退化情形下失去意义，这正是 closeness 在该公理上记 "no" 的根源之一。
**闭合检查**：7 格结果与 Table 3.1 原文（Degree "only k"；Closeness 三 "no"；Harmonic 三 "yes"；Betweenness "only p"）逐一吻合；size 公理的 "only" 标注语义（只满足团方向 / 只满足环方向）由 (a)(f) 两格坐实。未验证的格子（如 PageRank × size "no"、Katz × size "only k"）可按同一套路在小图上代入定义复核，留作第二遍阅读的练习。
12. 术语与跨章链接
本章首次系统引入、已入全书术语表的术语（点击跳转定义）：
- 距离类：接近中心性、调和中心性、入度/出度
- 谱类：谱中心性、随机游走中心性 / Seeley 指数、PageRank、个性化 PageRank（本章首次系统引入，Ch5 Further Notes 提到但未展开）、Katz 指数、HITS、随机游走
- 其余三族：首中时间、介数中心性、Shapley 值 / Myerson 值
- 比较框架：Boldi–Vigna 公理
跨章链接：
- → Ch5：3.3.2 的 PPR 相似度分类规则 $\pi_u(k)=(1-c)\nu_k[I-cP]^{-1}e_u$ 是 Ch5 Label Propagation 的直接先声；LP 解的 hitting-time 解释用的正是 3.1.3 的工具（Ch5 笔记 §7 第 2 条、proof-lemma-5-2）；Generalized Laplacian 的 $\sigma=0$ 端即 PPR 闭式（Ch5 笔记定理卡片）。Ch5 笔记 §12 已预留"Ch3 落盘后回填双向链接"。
- → Ch4：3.3.3 的边介数删边法（Girvan–Newman）与 PPR 社区归属指向社区检测全章；谱中心性与谱聚类共用特征向量语言（Ch4 笔记）。
- ← Ch2：$P=D^{-1}A$、邻接矩阵与度对角阵记号与 Ch2 章首 Notations 一致（Ch2 笔记 §8）；Katz/Bonacich 的矩阵形式沿用同一套记号，无冲突。
校勘备忘（OCR 层，译文与本笔记统一按此处理）：式 (3.18) 求和下标 $t$ 被误识为 $0$；HITS 段 "the index a is the left dominant eigenvector" 的 $a$ 被吞成上标；Theorem 3.1 陈述中 "and" 误入数学模式；3.1.4 流量守恒与 3.1.5 公理列表有 <sup> 残留（应还原为 $\forall$、$v(\cdot)$）；式 (3.5)–(3.7) 区域 OCR 把一段连贯推导拆成 4 个独立公式块，阅读时应还原为"显式 (3.5) → 分块对角展开 → Laurent 展开 (3.6) → 极限与推广 (3.7)"一条链。
13. 章节阅读路径
| 顺序 | 小节（印刷页） | 读法 |
|---|---|---|
| 1 | 章首引言（p.45） | 精读：中心性 = 节点实值排序函数；"判据不同 ⇒ 指标不同"是本章元规则 |
| 2 | 3.1.1（p.46–47） | 精读；Figure 3.1 是"语义不同 ⇒ 排名不同"的第一个证据 |
| 3 | 3.1.2 PageRank 段（p.47–49） | 精读 (3.4)(3.5) 与谱形式改写；多分量推广 (3.6)(3.7) 第一遍可快读 |
| 4 | 3.1.2 节点相关重启 + Thm 3.1 / Cor 3.1（p.49–52） | 配本页 §10 两卡 |
| 5 | 3.1.2 Katz / HITS（p.52–53） | 快读；记住"全额背书 vs 摊薄"与 $A^{T}A$ 即可 |
| 6 | 3.1.3（p.53–56） | 精读 (3.19)(3.22)；Figure 3.3 的三个版本差异对应对称化与否 |
| 7 | 3.1.4（p.56–59） | 最短路介数精读；最大流 / 电流与两种正则化快读；Figure 3.4 |
| 8 | 3.1.5（p.59–60） | 快读：两公理 + 路径折扣特征函数的显式 |
| 9 | 3.2（p.60–62） | 本章考点，三公理逐字精读；Table 3.1 配 §11 |
| 10 | 3.3（p.62–65） | 3.3.2 精读（Ch5 先导）；3.3.1 / 3.3.3 / 3.3.4 快读 |
| 11 | Further Notes（p.65） | 见 §16 |
14. 易混点
- "重要"不是一个概念：五族对应五种语义——距离类（离大家近）、谱类（被重要者指向）、首中时间类（随机游走易达）、介数类（流量咽喉）、博弈类（对联盟的边际贡献）。同一节点可以在一族里登顶、在另一族里垫底（Figure 3.1–3.4 的全部信息）；问"哪个指标最好"之前先问"哪个语义对"。
- 谱类内部的分界线是 $M$ 与"摊薄"：邻接谱取 $M=A$；Seeley 取 $M=P=D^{-1}A$——节点声誉按出度摊薄给后继（无向图上退化为 $\sigma_i\propto d_i$）；PageRank 在 Seeley 上加重启；Katz 对每个出边邻居给全额背书（不除以出度），故须 $\beta<\lambda(A)^{-1}$ 压制发散；HITS 用 $A^{T}A$ 产出 authority/hub 双指标。五个指标不是"一个比一个好"，而是五种不同的背书机制。
- 三条公理各自淘汰谁（按公理读 Table 3.1，不要按指标读）：size 淘汰 closeness / Seeley / PageRank（两方向全败），degree / Katz / HITS 只剩团方向，betweenness 只剩环方向；density 淘汰 closeness（桥两端平局，§11 第 (c) 格）与 betweenness；score-monotonicity 淘汰 closeness / Seeley / betweenness / HITS。只有 harmonic 全过——但公理是否决测试：PageRank 不过 size 公理，仍是 Web 与文献计量的标配（3.3.1）。
- closeness vs harmonic：区别只在运算顺序——"先求和再取倒数" vs "先取倒数再求和"。原书说有向推广 "quite straightforward" 但未展开：确实只是把 $d(v,u)$ 换成有向最短路，代价是要求强连通，否则分母中的 $\infty$ 使指标失效——这正是 harmonic 存在的理由，也是 §11 第 (b) 格的实质。
- $E_i[T_j]\ne E_j[T_i]$：首中时间天然不对称，所以 (3.20)（大家到 $j$ 的难易）与 (3.21)（$j$ 到大家的难易）是两个不同指标，Figure 3.3 前两 panel 的差异全在于此；(3.22) 用通勤时间对称化，顺带得到度量性质。
- $c$ 与 $C$ 的口径：式 (3.8) 中 $c(i)$ 是续走概率（重启概率 $1-c(i)$），原书行文有歧义，以公式与 Corollary 3.1 为准（校勘见 proof-theorem-3-1）；$K_i(C)$ 在原书 (3.15) 误排为 $K_i(A)$。
- "图不连通怎么办"的三种修法在全章复现：调和换序（3.1.1 → harmonic；3.1.3 第一种推广）、PageRank 式重启正则化（(3.7) 多分量 Seeley、(3.23) 带重启首中时间、3.1.4 拉普拉斯接地正则化 $[D-aA]\phi=b$ 与 $[D-A+\beta I]\phi=b$）。认出这条主线，三族的"推广"段就不用分别硬记。
15. 公式卡片
26 个编号公式按用途归为 8 组（卡内展示 18 式，(3.14)(3.15) 见 定理卡 T1，其余散见译文）；每组给出 输入 → 输出 → 用途。
F1 距离类二式（3.1.1）： $$\text{closeness}(u)=\frac{n-1}{\sum_v d(v,u)}\tag{3.1},\qquad \text{harmonic}(u)=\frac1{n-1}\sum_{v\ne u}\frac1{d(v,u)}.$$ 输入最短路距离矩阵；输出节点得分。用途：harmonic 是 closeness 的"换序"稳健版（$\infty^{-1}=0$），Table 3.1 唯一三公理全过者。
F2 PageRank 定义与显式（3.1.2 核心）： $$\pi=c\pi P+(1-c)\nu\tag{3.4}\quad\Longleftrightarrow\quad\pi=(1-c)\nu[I-cP]^{-1}.\tag{3.5}$$ 输入 $P=D^{-1}A$、续走概率 $c$、重启分布 $\nu$；输出平稳分布。用途：$\nu$ 取均匀即经典 PageRank，集中于节点集即 PPR；谱形式 $\pi=\pi(cP+(1-c)\underline1\nu)$ 说明它属于谱类；(3.5) 是 3.3.2 相似度与 Ch5 闭式解的母式。
F3 多分量 Seeley 推广： $$[I-cP]^{-1}=\frac1{1-c}\Pi+\mathcal D+\mathrm{o}(1-c)\tag{3.6}\quad\Longrightarrow\quad\sigma=\Big[\tfrac{n_1}n\sigma^{(1)}\ \cdots\ \tfrac{n_m}n\sigma^{(m)}\Big].\tag{3.7}$$ （$\Pi$ 为遍历投影、$\mathcal D$ 为偏差矩阵——原书与译文记作 $D$，本卡改花体以免与度对角阵混淆，马尔可夫链 Laurent 展开；$\sigma^{(i)}$ 为第 $i$ 个强连通分量的平稳分布。）输入各分量转移矩阵 $P^{(i)}$；输出全图排名，分量重要性按大小加权。用途：$c\to1$ 极限把 Seeley 指数合法地推广到非强连通图；"大分量里的大节点更值"的定量依据。
F4 节点相关重启与两种 PPR： $$\tilde P=CD^{-1}A+(I-C)\underline1\nu,\tag{3.8}\qquad \pi(\nu)=\frac{\nu[I-CP]^{-1}}{\nu[I-CP]^{-1}\underline1},\tag{3.11}\qquad \rho(\nu)=\nu[I-CP]^{-1}[I-C].\tag{3.12}$$ OT-PPR 数"访问"，LR-PPR 数"重启前一刻所在"。用途：Theorem 3.1 的主角；个性化排名的最一般形式。
F5 direct–reverse 对偶（本章定理组）： $$\frac{d_i}{c_iK_i(C)}\pi_j(i)=\frac{d_j}{c_jK_j(C)}\pi_i(j)\tag{3.13}\quad\overset{c_i=c}{\Longrightarrow}\quad d_i\pi_j(i)=d_j\pi_i(j).\tag{3.16}$$ 用途：无向图 PPR 不对称性的完全刻画；证明见 §10。
F6 Katz 指数： $$\kappa=\underline1^{T}\sum_{t\ge1}\beta^tA^t=\underline1^{T}\big([I-\beta A]^{-1}-I\big),\qquad\beta<\lambda(A)^{-1}.\tag{3.17}$$ 输入邻接矩阵与折扣 $\beta$；输出对所有路径几何折扣求和的得分。用途：与 PageRank 的分界线是"全额背书"；换 Poisson/阶乘折扣得 Estrada communicability，换 $A\to P$ 得 heat kernel PageRank（Further Notes）；Brauer 定理把它写成特征值问题，故归入谱类。
F7 首中时间族（3.1.3）： $$E_i[T_j]=e_i^{T}[I-P_{-j}]^{-1}\underline1,\tag{3.19}\qquad h_j=\frac{n}{\underline1^{T}[I-P_{-j}]^{-1}\underline1},\tag{3.20}\qquad \tilde h_j=\frac{n}{\underline1^{T}[I-(P^{T})_{-j}]^{-1}\underline1},\tag{3.21}\qquad \bar h_j=\frac{2m}{\sum_i(E_i[T_j]+E_j[T_i])},\tag{3.22}\qquad h_j^{c}=\frac{n}{\underline1^{T}[I-cP_{-j}]^{-1}\underline1}.\tag{3.23}$$ 输入转移矩阵（与 Taboo 子矩阵）；输出"随机游走可达性"得分。用途：(3.22) 经有效电阻对称化且满足度量性质；(3.23) 处理不连通并改善条件数——同一 $[I-c\,\cdot\,]^{-1}$ 引擎（§7 第 1 条）。（校勘：本卡符号原沿用 OCR 误识的 $b$ 系列，已按原书统一为 $h/\tilde h/\bar h/h^c$ 系列，并补展示 (3.21)。）
F8 介数族（3.1.4）： $$\text{流介数}=\frac{\sum_{s,t}m_{st}(v)}{\sum_{s,t}m_{st}},\tag{3.24}\qquad L\phi=b,\ b=\mathbf 1_s-\mathbf 1_t,\tag{3.25}\qquad \text{电流介数}=\frac1{(n-1)(n-2)}\sum_{s,t}\tau_{st}(v).\tag{3.26}$$ 输入（加权）图；输出"瓶颈"得分。用途：最短路介数的最自然两种全路径推广；$L\phi=b$ 与 Ch4 谱方法、Ch5 拉普拉斯方法共用同一个 $L$。
16. Further Notes 导读
本章无习题；Further Notes（印刷页 65）5 条文献指引的读法如下：
- 公理化刻画的其他工作（Sabidussi, 1966；Altman & Tennenholtz, 2005；Wąs & Skibski, 2018；Skibski & Sosnowska, 2018）：3.2 的三公理只做了"测试"，这批文献做的是"刻画"——找一组公理唯一确定某个指标（如 PageRank 的公理化）。读什么：如果 §11 让你好奇"harmonic 全过是否意味着它是唯一'正确'的指标"，这条线给出严格答案（不是——不同公理体系刻画不同指标）。与后续章关系：本书后文不再展开，属离书进文献的出口。
- 群中心性（Everett & Borgatti, 1999 起；Michalak et al., 2013）：度量一组节点（部门、社群）而非单点的重要性。关键提醒（原书强调）：不能简单把单点中心性求和——这正是 3.1.5 博弈论方法（Shapley/Myerson 按边际贡献分配）自然适用于群中心性的原因。读法：先吃透 3.1.5，再读这批文献。
- Top-k 中心节点选取（Avrachenkov et al., 2011, 2014c；Yoshida, 2014；Borassi & Natale, 2019 等）：大图上只要前 $k$ 名时的快速算法（近似介数等）。这是"中心性如何规模化计算"的入口，与 Ch7 抽样精神相通（拿不到全网时的估计）。
- 折扣换元族（Estrada & Rodriguez-Velazquez, 2005；Estrada & Hatano, 2008；Chung, 2007）：Katz 的几何折扣 $\beta^t$ 换成 Poisson/阶乘折扣得 Estrada communicability（$\sum_t (\beta A)^t/t!$，指数型），再把 $A$ 换成 $P$ 得 heat kernel PageRank。读法：把它们都看成 §15 F6 的"换折扣函数 / 换矩阵"两次换元，公式族谱立刻清晰。
- Gleich (2015) PageRank 综述：PageRank 各种变体与应用的全景图。3.1.2 读完想深入时的首选；与后续章关系：Ch5 的 PPR 用法在本综述中有更系统的展开。
17. 学习检查表
学完本章后自查：
- [ ] 能复述：五族指标各自的"重要性语义"一句话版本，以及每族一个代表指标的定义（§5 地图不看书画出）。
- [ ] 能写出：(3.1)、(3.4)(3.5)、(3.17) 三组公式，说明每个符号的含义与参数范围（$c\in(0,1)$、$\beta<\lambda(A)^{-1}$）。
- [ ] 能解释：为什么 PageRank 属于谱类指标（谱形式改写 $\pi=\pi(cP+(1-c)\underline1\nu)$）；为什么 Seeley 指数在无向图上退化为度排名。
- [ ] 能证明：Corollary 3.1（由 $P\underline1=\underline1$ 推出 $K_i=1-c$ 与 $i$ 无关）；Theorem 3.1 的第 2 步（$N=CD^{-1}-CD^{-1}ACD^{-1}$ 对称 ⇒ $M=N^{-1}$ 对称）。
- [ ] 能陈述：Boldi–Vigna 三公理的内容，并各说出一个被该公理淘汰的指标（能复算 §11 的格子更佳，至少会做 (g) harmonic × size 的 $k-1$ vs $H_{p-1}$ 比较）。
- [ ] 能判别：给定数据条件（不连通 / 有向弱连通 / 需要瓶颈语义 / 需要相对某组节点的相似度），选出合适的指标族与正则化手段（§14 第 7 条的三种修法）。
- [ ] 能定位：3.3.2 的 PPR 分类规则与 Ch5 Label Propagation 的关系；边介数删边法与 Ch4 Girvan–Newman 的关系。
18. 后续衔接
- 第 4 章 Community Detection：3.3.3 埋了两条引线——边介数反复删边即 Girvan–Newman 式社区检测（介数中心性词条已挂钩）；PageRank 找社区代表点 + PPR 归属节点是"中心性 → 聚类"范式的前奏。谱中心性与谱聚类共用"取某矩阵前几个特征向量"的语言，但注意分工：谱聚类用拉普拉斯的小特征向量切分图，谱中心性用邻接/转移矩阵的主特征向量排序节点。
- 第 5 章 Graph-based Semi-supervised Learning：3.3.2 是本章最重要的前瞻——以 PPR 作点–类相似度、argmax 归属的规则在 Ch5 升级为系统的 LP / LS / GL 方法族；Label Propagation 解的 hitting-time 解释直接调用 3.1.3 的工具（首中时间超过混合时间 ⇒ "忘记起点"，见 Ch5 笔记 §7）；GL 的 $\sigma=0$ 端即 (3.5) 的 PPR 闭式。
- 第 7 章 Sampling：本章指标都假设能拿到全图；Top-k 选取（Further Notes 第 3 条）与抽样估计是"大图 / 残缺图上的中心性"的两条补救线，后者在 Ch7 方法化。
- 回看第 2 章：$A$、$D$、$P=D^{-1}A$ 与 Ch2 记号完全一致；Katz/Bonacich 的矩阵写法未引入任何新约定——若对 $[I-\beta A]^{-1}$ 的存在性存疑，回 §7 第 1、3 条。