random walk · PageRank 与图的谱

图论小类里的其余系列讲的都是确定性的算法与结构定理:最短路怎么算、拓扑序怎么排、Menger 定理断言了什么。本系列换一条线——在图上随机走。规则简单到一句话:站在某个点上,在邻居里等概率挑一个走过去,重复。难的是它的极限行为:走得足够久之后停在各点的概率分布是什么、要走多久才够久、图的哪一处结构在拖慢它。

两页分别从有向与无向两侧切入。PageRank 一页把「重要性」定义成 random walk 的 stationary distribution, 用 power iteration 逐轮算出来, 并处理 dangling node 与 spider trap 这两处会让极限不存在或不唯一的结构。random walk 一页回到无向图, 从 $\pi_v \propto \deg(v)$ 这条一行可验的结论出发, 走到 hitting time、cover time、graph Laplacian 的谱 (第二小的特征值即 algebraic connectivity), 以及 random walk 与电阻网络的严格对应。

pagerank · 网页排序

PageRank：网页图上的 power iteration

把网页的重要性定义成 random surfer 的极限分布：反复左乘同一个矩阵即可算出，dangling node 会漏掉概率质量，damping factor 保证极限存在且唯一。

walks · 度数与谱

random walk：从度数到 graph Laplacian

无向连通图上 random walk 的极限分布正比于度数，一行即可验证；hitting time 与 cover time 量走多久，graph Laplacian 的 $\lambda_2$ 量图有多难切开。

演示为什么不用真随机

站内 lab 的每一帧都要可复现: 同一组参数, 今天与明天、这台机器与那台机器必须给出同一串画面。所以本系列的演示分两类。主线演示的是分布的确定性演化——power iteration 与转移矩阵相乘本来就不需要任何随机, 一轮就是一次向量乘矩阵。只有展示单条轨迹时才引入随机, 而那里用的是自带种子的 LCG (见 core/linalg.ts), 种子做成控件, 换一个种子即换一条轨迹, 同一种子永远给同一条。全系列不出现 Math.random。

相关链接

• 随机图 · 概率方法与阈值现象 本站 「图 + 概率」的另一个方向: 随机的是边本身而不是走法。G(n,p) 里许多性质在某个阈函数处从几乎必不骤变为几乎必然。
• 概率 · 条件、独立与后验更新 本站 本系列用到的概率语言 (条件概率、独立、期望) 的来处; random walk 的每一步都是一次条件分布的更新。
• 连通性 · 分隔集与 Menger 定理 本站 连通性的组合刻画 (删几个点才能拆开图), 与本系列的 algebraic connectivity 是同一件事的两种量法。
• 图论 · graph 算法合集 本站 同一类图上的确定性算法: 最短路、最小生成树、拓扑排序。与本系列共用图模型与单步播放引擎。
• Random walk en.wikipedia.org random walk 的总览: 一维格点、图上、连续极限 (Brown 运动) 三条线索与各自的经典结论。
• PageRank en.wikipedia.org PageRank 的定义、矩阵形式、damping factor 的来历, 以及后续变体 (personalized / topic-sensitive) 的索引。