walks · 度数与谱

random walk：从度数到 graph Laplacian

在图上走路的规则简单到近乎无趣：站在某个点上，看一眼邻居，等概率挑一个走过去，重复。可这条规则同时是 PageRank 的底座、spectral clustering 的底座、一大批采样算法的底座，还与一张由电阻拼成的网络严格对应。原因在于它把「图的结构」压成了一个可以反复相乘的矩阵，而矩阵的谱把结构里的连通程度、瓶颈位置、走遍全图要多久，全都编码成了几个数。

本页从最容易验证的一条结论开始（极限分布正比于度数），再看它什么时候不成立（bipartite 图上的振荡），然后量两个「要走多久」的指标，最后把矩阵换成 graph Laplacian，看它的第二特征值如何指出图的瓶颈。PageRank 是同一套东西在有向图上的版本，见 PageRank：网页图上的 power iteration。概率工具本身见概率 · 条件、独立与后验更新。

1 · 图上的 random walk

定义 1.1（random walk） 给定无向连通图 $G = (V, E)$ ， $|E| = m$ 。walk 从某个起点出发，每一步在当前点 $u$ 的 $\deg(u)$ 个邻居中等概率选一个走过去。转移矩阵是 $P(u, v) = 1/\deg(u)$ 若 $u \sim v$ ，否则为 0；它每行之和为 1。

分布的演化不含任何随机：记 $x_t$ 为第 $t$ 步所在位置的概率分布（行向量），则 $x_{t+1} = x_t P$ 。单条轨迹与分布演化是同一件事的两种看法：前者是一次抽样，后者是全部抽样的加权汇总。本页的演示凡涉及分布都直接乘矩阵，只有展示单条轨迹时才用带固定种子的伪随机，以保证同一参数下每次得到同一条路径。

图 1-1 · 单条轨迹的落脚点与累计访问频率。可切换图与种子，观察高度数的点被踩得更勤，以及走多少步才把六个点都访问一遍。

2 · 度数与 stationary distribution

有向图上求 stationary distribution 一般要解线性方程组。无向图上不必：答案能直接写出来。

定理 2.1 无向连通图上 random walk 的 stationary distribution 是 $\pi(v) = \deg(v) / 2m$ 。

验证只要一行。 $\pi P$ 在 $v$ 处的分量是

(\pi P)(v) = \sum_{u \sim v} \pi(u)\,P(u, v) = \sum_{u \sim v} \frac{\deg(u)}{2m} \cdot \frac{1}{\deg(u)} = \frac{\deg(v)}{2m} = \pi(v)

关键在于 $P(u, v) = 1/\deg(u)$ 里的 $\deg(u)$ 与 $\pi(u)$ 里的 $\deg(u)$ 相消，求和退化成数一遍 $v$ 有多少个邻居。换个说法：把质量摊在边上而不是点上，每条边分到 $1/2m$ ，点 $v$ 得到的就是它所连边的份额之和。

风筝那张图的度数是 1 到 4， $2m = 14$ ，于是 $\pi = (2, 2, 4, 2, 3, 1)/14$ 。星形图更极端：中心一个点独占 $5/10 = 0.5$ ，五个叶子各 $0.1$ 。高度数的点不是「更重要」，只是被更多条边指着，路过的次数按比例更多。

图 2-1 · 分布的逐轮演化。可切换图、起点与 lazy 开关，观察柱子如何压向虚线标出的

\deg(v)/2m

。

3 · 周期性与 bipartite 图上的振荡

定理 2.1 说 $\pi$ 是不动点，没说 $x_t$ 一定收敛到它。星形图上从中心出发就不收敛：第 1 步全部质量在五个叶子上，第 2 步全部回到中心，此后严格周期为 2，与 $\pi$ 的 L1 距离恒等于 1.0，走一万步也不下降。六圈图同样如此，只是振荡的形状复杂些。

原因是 bipartite 图上任何闭合回路的长度都是偶数，从一侧出发的 walk 在偶数步必在同侧、奇数步必在另一侧。分布的「相位」永远对不上 $\pi$ 。

有意思的是振荡的中心仍是 $\pi$ ：相邻两轮取平均，星形图上得到的正好是 $(0.5,\ 0.1,\ 0.1,\ 0.1,\ 0.1,\ 0.1)$ ，与 $\pi$ 的 L1 差是 0。长期访问频率也照样收敛到 $\pi$ ——图 1-1 里频率柱贴虚线，与分布是否收敛无关。不收敛的是逐轮的分布本身。

修法是 lazy random walk：每步先抛一枚均匀硬币，正面才走，反面原地不动，即把 $P$ 换成 $(I + P)/2$ 。对角线一进来周期就变成 1，而 $\pi$ 分毫未变（ $\pi(I+P)/2 = (\pi + \pi P)/2 = \pi$ ）。星形图从中心出发做 lazy walk，第 1 步就精确落在 $\pi$ 上： $0.5$ 留在原地， $0.5$ 平摊给五个叶子，各得 $0.1$ 。

代价是变慢。风筝那张图上，普通 walk 的误差每轮乘 0.717，lazy 版乘 0.813，达到同样精度所需的轮数多出约六成。一半的步数花在原地不动上，这个折扣躲不掉。

4 · hitting time 与 cover time

两个自然的时间尺度。hitting time $H(u, v)$ 是从 $u$ 出发首次抵达 $v$ 的期望步数；cover time 是从 $u$ 出发访问遍全部点的期望步数。前者可以精确算：对固定的目标 $v$ ，诸 $h_u = H(u, v)$ 满足 $h_v = 0$ 与

h_u = 1 + \sum_{w \sim u} \frac{1}{\deg(u)}\,h_w \qquad (u \neq v)

这是一个 $n - 1$ 元线性方程组，解一次就得到整列。 $H$ 一般不对称：风筝图上 $H(A, F) = 21.00$ 而 $H(F, A) = 11.67$ 。F 是挂在 E 上的悬挂点，从它出发只有一条路可走，回到主体很快；反过来要撞进这条死胡同则需要运气。

图 4-1 · hitting time 矩阵与两个衍生量。可切换图与两个端点，对照

C(u,v)

与

2m

乘 effective resistance 两张卡片的数值。

cover time 没有同样简洁的闭式解。Matthews 给了一个只用 hitting time 的上界 [3]：cover time 不超过 $H_{n-1} \cdot \max_{u \neq v} H(u, v)$ ，其中 $H_{n-1} = \sum_{k=1}^{n-1} 1/k$ 是调和数。本页用 400 个固定种子抽样估计实际值：风筝图从 A 出发均值 22.6，上界 47.9；星形图均值 22.4，上界 22.8。星形图上这个界几乎是紧的，因为覆盖它的瓶颈就是「最后一个没访问过的叶子」，而各叶子彼此对称，Matthews 的耦合论证在星形图上几乎无损。

注 · 从最偏僻的点出发，反而覆盖得最快。风筝图上从悬挂点 F 出发的抽样均值是 15.8 步，从度数最高的 C 出发是 24.2 步，差出五成还多。原以为「从中心出发更划算」，实测正好反过来。解释也简单：这张图的覆盖瓶颈是 F 本身（任意点到 F 的 hitting time 都在 17 到 21 之间），从 F 起步等于把最贵的那一项白送。这也提醒 cover time 是依赖起点的量，报数时必须写清从哪里出发。

5 · graph Laplacian 与 algebraic connectivity

把 $P = D^{-1}A$ 里的归一化去掉，换成一个对称矩阵：graph Laplacian $L = D - A$ ，其中 $D$ 是度数对角阵、 $A$ 是邻接矩阵。它每行之和为 0，所以全 1 向量在核里，最小特征值恒为 $\lambda_1 = 0$ 。 $L$ 对称半正定，特征值可以排成 $0 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_n$ 。

$\lambda_2$ 叫 algebraic connectivity，也叫 Fiedler value [4]。它为 0 当且仅当图不连通（0 的重数等于连通分支数），而它有多接近 0，度量的是图有多容易被切开。对应的特征向量称作 Fiedler 向量，按分量符号把点分成两组，就是 spectral bisection。

哑铃图（两个三角形加一条桥）的 $\lambda_2 = 0.4384$ ，spectral bisection 切下来的正好只有那条桥，两侧各三个点。风筝图的 $\lambda_2 = 0.6314$ ，切口是两条边。六圈图的 $\lambda_2$ 有闭式解 $2 - 2\cos(2\pi/6) = 1$ ，切成两段各三个点。

图 5-1 · Laplacian 的谱与 Fiedler 向量。可切换图，对照

\lambda_2

的大小、切口的边数与两侧规模。

警示 · $\lambda_2$ 简并时 spectral bisection 给出的划分不是图的性质。星形图的谱是 $(0, 1, 1, 1, 1, 6)$ ， $\lambda_2 = 1$ 有四重简并， $\lambda_2$ 的特征子空间是四维的，Fiedler 向量在其中任取一个都合法。本页的 Jacobi 求解器给出的划分把中心和两个叶子分作一侧、另外三个叶子分作另一侧，切断三条边——这在图上毫无意义，纯粹是求解器破简并的方式。谱二分只有在 $\lambda_2$ 与 $\lambda_3$ 拉开差距时才谈得上是图的判断。

$\lambda_2$ 与 §3 的收敛速度说的是同一件事，只是严格的对应要换成正则化后的 Laplacian $\mathcal{L} = I - D^{-1/2} A D^{-1/2}$ ：它的特征值 $\nu$ 与 $P$ 的特征值 $\mu$ 满足 $\nu = 1 - \mu$ ，谱隙越大混合越快。 $L$ 与 $\mathcal{L}$ 在度数处处相等的图上只差一个常数倍，度数悬殊时则不然。它与组合意义上的 vertex connectivity（删几个点才能拆开图）也有一层关系，Fiedler 证明了 $\lambda_2$ 不超过 vertex connectivity，那一侧的故事见连通性：分隔集与 Menger 定理。

6 · effective resistance 与电阻网络

把每条边换成一个 1 欧姆电阻，整张图就成了一个电路。任取两点 $u$ 、 $v$ ，量出它们之间的等效电阻 $R(u, v)$ （可由 $L$ 的 Moore–Penrose 伪逆算出， $R(u,v) = L^{+}_{uu} + L^{+}_{vv} - 2L^{+}_{uv}$ ）。Chandra 等人证明了 [2]

C(u, v) = H(u, v) + H(v, u) = 2m \cdot R(u, v)

其中 $C$ 叫 commute time，是一来一回的期望步数。 $H$ 不对称， $C$ 对称，而对称正好是电阻该有的性质。

风筝图上这条等式逐位对得上： $C(A, F) = 21.00 + 11.67 = 32.67$ ，而 $2m \cdot R(A, F) = 14 \times 2.3333 = 32.67$ 。单条边上的电阻也符合直觉：三角形里的一条边并联着另外两条串起来的边， $R = 1 \parallel 2 = 2/3$ ；悬挂边 E–F 无并联路径， $R = 1$ 。core/walk.test.ts 对四张图的全部点对都做了这个对照，两条完全不同的算路（解线性方程组 vs 谱分解求伪逆）给出同一组数。

这个类比不只是好看。电阻网络有一整套现成的推理工具，最有用的是 Rayleigh 单调性：加一条边只会让任何两点间的电阻变小，删一条边只会变大。翻译成 walk 的语言就是「加边只会缩短 commute time」——这条结论直接证不算容易，借电阻则一句话。

7 · 参考文献

Lovász, L. (1993). Random walks on graphs: A survey. Combinatorics, Paul Erdős is Eighty, 2, 1–46.
Chandra, A. K., Raghavan, P., Ruzzo, W. L., Smolensky, R., & Tiwari, P. (1996). The electrical resistance of a graph captures its commute and cover times. Computational Complexity, 6(4), 312–340.
Matthews, P. (1988). Covering problems for Markov chains. The Annals of Probability, 16(3), 1215–1228.
Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298–305.
Doyle, P. G., & Snell, J. L. (1984). Random Walks and Electric Networks. Mathematical Association of America.