PageRank 是早期 Google 搜索的核心算法，决定了搜索结果中的网页展示顺序
PageRank 核心思想：
- 根据网站的外部链接和内部链接的数量和质量衡量网站的价值
- 如果重要性为 $PR(i)$ 的页面 $i$ 有 $l_i$ 个外链（出度），则每个链接的价值为 $PR(i)/l_i$
- 因此，页面 $j$ 的重要性（表示为 $PR(j)$ ）是其链接上的价值总和
$$PR(j) = \sum_{i \rightarrow j} \frac{PR(i)}{l_i}$$
上式最大的问题在于忽略了"不存在外链的特殊页面"
因此 PageRank 算法引入了阻尼系数 $d$ （damping factor）
PageRank 算法细节：
- PageRank 输出一个概率分布，来表示浏览者点击链接到达任意页面的可能性
- 在每个时间步，浏览者有两个选择：（1）以概率 $d$ 随机点击页面上的任一链接（2）以概率 $1-d$ 随机跳转到全局内的任意页面。因此页面 $j$ 的重要性计算公式如下：
$$PR(j) = (1 - d) \frac{1}{N} + \sum_{i \rightarrow j} d \frac{PR(i)}{d_i}$$
- 假设所有页面的数量为 $N$，将上式的随机游走策略转化为矩阵形式：
$$ \begin{bmatrix}PR(1) \\PR(2) \\\vdots \\PR(N)\end{bmatrix}=\begin{bmatrix}(1-d)/N \\(1-d)/N \\\vdots \\(1-d)/N\end{bmatrix}+d\begin{bmatrix}\ell(1,1)&\ell(1,2)&\cdots&\ell(1,N) \\\ell(2,1)&\ddots&& \\\vdots&&\ell(i,j)& \\\ell(N,1)&&&\ell(N,N)\end{bmatrix}\begin{bmatrix}PR(1) \\PR(2) \\\vdots \\PR(N)\end{bmatrix} $$
$\ell(1,2)$ 描述了页面 2 指向页面 1 的连接数/页面 2 的总外链数（转移矩阵的元素）
- 初始化所有页面的 $PR$ 值为 $1/N$，经上式迭代后页面的最终 $PR$ 值将逐步收敛
PageRank 算法分析：
- 收敛速度快，计算效率高，常用于网页排序和引文网络分析
- 缺点在于旧的页面的 PageRank 排名往往会比新页面高
- 有的页面内容质量很高，但可能没有很多外链（结合其他算法来改善结果）