21 PageRank
PageRank 是图的链接分析（link analysis）的代表性算法，属于图数据上的无监督学习方法。它最初由 Page 和 Brin 于 1996 年提出，用于谷歌搜索引擎的网页排序。
- 核心思想：在有向图上定义一个随机游走模型（一阶马尔可夫链
） ，描述随机游走者沿着有向图随机访问各个结点的行为。 - 重要度度量：当随机游走达到极限情况（平稳分布）时，访问每个结点的概率值即为该结点的 PageRank 值，表示结点的相对重要度 ,。
基础模型：有向图与随机游走 ¶
PageRank 的计算基于对互联网结构的抽象：
- 有向图 \(G = (V, E)\)：网页是结点，超链接是有向边。
- 基本随机游走：假设浏览者在每个网页依照连接出去的超链接，以等概率跳转到下一个网页 ,。
- 转移矩阵 \(M\)：是一个随机矩阵，其元素 \(m_{ij}\) 表示从结点 \(j\) 跳转到结点 \(i\) 的概率。如果结点 \(j\) 有 \(k\) 条出边，则 \(m_{ij} = 1/k\)；否则 \(m_{ij} = 0\)。
- 理想状态下的 PageRank：若有向图是强连通且非周期的，则存在唯一的平稳分布 \(R\)，满足 \(MR = R\),。
一般定义：引入阻尼因子 ¶
在现实中，许多网页没有出链（终止点
- 行为逻辑：用户以概率 \(d\) 按照超链接随机跳转，以概率 \(1-d\) 完全随机地跳转到网络中任意一个网页 ,。
- 核心公式： $\(R = dMR + \frac{1-d}{n}\mathbf{1}\)$ 其中 \(\mathbf{1}\) 是所有分量均为 1 的 \(n\) 维向量 ,。这个定义保证了在任何结构的图上都能得到唯一的平稳分布 \(R\)。
PageRank 的计算方法 ¶
主要有三种计算方式，其中幂法最为常用：
- 迭代算法（Iterative Algorithm）：按照一般定义公式不断迭代 \(R_{t+1} = dMR_t + \frac{1-d}{n}\mathbf{1}\)，直至向量收敛。
- 幂法（Power Method）：将 PageRank 的计算视为求一般转移矩阵 \(A = dM + \frac{1-d}{n}E\) 的主特征向量（对应特征值为 1）,。
- 选择初始向量 \(x_0\)。
- 迭代计算 \(y_{t+1} = Ax_t\)。
- 规范化 \(x_{t+1} = \frac{y_{t+1}}{|y_{t+1}|}\)，直到满足精度要求。
- 代数算法：通过求解线性方程组 \((I - dM)R = \frac{1-d}{n}\mathbf{1}\) 来直接获取 \(R\) 的精确值。
特性总结 ¶
- 递归定义：一个结点的 PageRank 值取决于指向它的所有结点的 PageRank 值。
- 独立于查询：PageRank 值仅依赖于网络的拓扑结构，与用户的搜索词无关，可以离线预先计算 ,。
- 平滑性：由于导入了完全随机跳转项（平滑项
） ，所有结点的 PageRank 值均大于 0。