题目
实现图算法的PageRank，分布式幂迭代优化。
完整讲解
- PageRank：将网页（或节点）的重要性定义为「被重要节点指向则自己重要」的均衡。设 $r_i$ 为节点 $i$ 的 rank，$r = \alpha P^\top r + (1-\alpha) \frac{\mathbf{1}}{n}$，其中 $P$ 为行随机转移矩阵（出链均匀），$\alpha$ 为阻尼系数；或等价地 $r$ 为 $P$ 的主特征向量（最大特征值 1）的平稳分布。
二、幂迭代
- 幂迭代：求主特征向量时，迭代 $r^{(k+1)} = P^\top r^{(k)}$（或带阻尼与 teleport），直至收敛。即 $r$ 不断被 $P^\top$ 左乘，收敛到主特征向量。每步复杂度 $O(E)$（边数），稀疏图可行。
- 实现：用邻接表或稀疏矩阵存图；每轮对每个节点 $i$，$r_i^{\text{new}} = \alpha \sum_{j: j\to i} r_j / \text{out}_j + (1-\alpha)/n$；归一化 $r$ 或保持 $|r|_1=1$。迭代直到 $|r^{\text{new}} - r| < \epsilon$。
三、分布式与优化
- 分布式：图按节点分片，每片存该片节点的出边与 $r$；每轮各片算本片节点的 $r^{\text{new}}$（需收集入边来自哪些片、对应 $r_j$），再同步 $r$ 或用 AllGather；多轮迭代直至收敛。可 Pregel、Spark GraphX 等。
- 优化：稀疏矩阵向量乘；早停（变化小于阈值）；阻尼与 teleport 避免悬挂节点与死胡同；大图可分区与 checkpoint。
面试要点
- 能写出 PageRank 的方程（$r = \alpha P^\top r + (1-\alpha)\mathbf{1}/n$）与幂迭代形式。
- 能说明幂迭代每步做什么、复杂度；能简述分布式思路（图分片、每轮同步 $r$）。
记忆要点
- PageRank：$r$ 为转移矩阵主特征向量；幂迭代 $r \leftarrow P^\top r$（带阻尼）直至收敛。
- 分布式：图分片、每轮局部算新 $r$ 再同步；复杂度 O(E) 每轮。