第 03 章学习笔记：网络中心性指标

原书态度：定理署名 (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}]$。

证明目标：$A^{T}=A$ 且 $c_i=c\ \forall i$ 时，(3.13) 化简为 $d_i\pi_j(i)=d_j\pi_i(j)$。

依赖工具：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"），无遗漏常数。

任务：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 的公理化讨论实质上限定在强连通图上，见“易混点”第 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"）可按同一套路在小图上代入定义复核，留作第二遍阅读的练习。