PageRank 2020-04-27 PageRank Google Rationale
PageRank 算法基于以下两个假设 ：
数量假设: 某页面接受到的入链数量越多 ，则该页面越重要；质量假设: 某页面接受到的入链质量越高 ，则该页面越重要。
假设 2 事实上为每个页面都赋予了一个权重。PageRank 算法基于上述假设，利用入链的数量与质量，来估算该页面的重要性。
PageRank Algorithm
PageRank 算法可概括为：如果某页面入链等级之和越高，则该页面的等级也越高 。
首先，我们从一个简化版的 PageRank 算法出发。令 p p p F p F_p F p p p p B p B_p B p p p p N p = ∣ F p ∣ N_p = |F_p| N p = ∣ F p ∣ p p p R R R
R t + 1 ( p ) = c ∑ q ∈ B p R t ( q ) N q R_{t + 1}(p) = c\sum_{q \in B_p}\frac{R_{t}(q)}{N_q} R t + 1 ( p ) = c q ∈ B p ∑ N q R t ( q ) 其中，c c c p p p q q q R R R N q N_q N q q q q R R R
这个公式事实上是递归迭代的。不过在完整的 PageRank 算法下，对于任意的初值，以该公式经过迭代计算，最终总能收敛到一组稳定值。 实践中，常取初值 R 0 ( p i ) = 1 / n R_0(p_i) = 1 / n R 0 ( p i ) = 1/ n
该公式也可以采用矩阵形式表述。设 A A A p p p q q q A p , q = 1 / N p A_{p, q} = {1}/{N_p} A p , q = 1 / N p A p , q = 0 A_{p, q} = 0 A p , q = 0
R t + 1 = c A R t \mathbf{R}_{t + 1} = cA\mathbf{R}_{t} R t + 1 = c A R t 其中 R \mathbf{R} R
R = [ R ( p 1 ) R ( p 2 ) ⋮ R ( p n ) ] \begin{aligned}
\mathbf{R} &= \begin{bmatrix}
R(p_1) \\
R(p_2) \\
\vdots \\
R(p_n)
\end{bmatrix}
\end{aligned} R = R ( p 1 ) R ( p 2 ) ⋮ R ( p n ) 这样，PageRank 向量 R \mathbf{R} R A A A
该简化版本的 PageRank 事实上有一些缺陷：如果一组网页相互成环且没有出链，且有一些其他页面指向这组页面，那么在迭代计算时，这个局部会不断积累 R R R rank sink 。
Random Surfer Model
为了解决 rank sink 的问题，PageRank 引入了阻尼系数 (decay factor) 的概念1 R ′ R' R ′
R t + 1 ′ ( p ) = 1 − d n + d ∑ q ∈ B p R t ′ ( q ) N q , where d ∈ ( 0 , 1 ) R'_{t + 1}(p) = \frac{1 - d}{n} + d\sum_{q \in B_p}\frac{R'_{t}(q)}{N_q}, \text{where } d \in (0, 1) R t + 1 ′ ( p ) = n 1 − d + d q ∈ B p ∑ N q R t ′ ( q ) , where d ∈ ( 0 , 1 ) 这里，d d d 0.85 0.85 0.85 2
使用矩阵形式重写如下：
R ′ t + 1 = 1 − d n 1 + d A R ′ t \mathbf{R'}_{t + 1} = \frac{1 - d}{n}\mathbf{1} + dA\mathbf{R'}_{t} R ′ t + 1 = n 1 − d 1 + d A R ′ t 其中，1 \mathbf{1} 1 1 1 1
Rank Leak
Page Rank 的另一个问题是所谓悬空链接 (dangling links) ，指没有出链的独立网页。解决方法很简单：将这些节点先从图中去除，待计算完成后在加入进去。这些节点不会对整体的结果造成太大的影响。
Properties of PageRank Algorithm
Property 1. 对于任意 t > 0 t > 0 t > 0
∑ i = 1 n R t ′ ( p i ) ≤ 1 \sum_{i = 1}^{n} R'_t(p_i) \leq 1 i = 1 ∑ n R t ′ ( p i ) ≤ 1 Property 2. 进一步地，若对任意 1 ≤ j ≤ n 1 \leq j \leq n 1 ≤ j ≤ n N j ≥ 1 N_j \geq 1 N j ≥ 1 t > 0 t > 0 t > 0 { R t ′ ( p i ) } 1 ≤ i ≤ n \{R'_t(p_i)\}_{1 \leq i \leq n} { R t ′ ( p i ) } 1 ≤ i ≤ n t > 0 t > 0 t > 0
∑ i = 1 n R t ′ ( p i ) = 1 \sum_{i = 1}^{n} R'_t(p_i) = 1 i = 1 ∑ n R t ′ ( p i ) = 1 Proof. 我们知道 ∑ i = 1 n R 0 ′ ( p i ) = 1 \sum_{i = 1}^{n} R'_0(p_i) = 1 ∑ i = 1 n R 0 ′ ( p i ) = 1 R 0 ′ ( p i ) = 1 / n R'_0(p_i) = 1 / n R 0 ′ ( p i ) = 1/ n t ≥ 0 t \geq 0 t ≥ 0 1 ≤ j ≤ n 1 \leq j \leq n 1 ≤ j ≤ n N j ≥ 1 N_j \geq 1 N j ≥ 1
∑ i = 1 n R t + 1 ′ ( p i ) = ( 1 − d ) + d ∑ i = 1 n ∑ q ∈ B p i R t ′ ( q ) N q = ( 1 − d ) + d ∑ i = 1 n ∑ j = 1 n R t ′ ( p j ) N p j I { p j ∈ B p i } = ( 1 − d ) + d ∑ j = 1 n ( ∑ i = 1 n I { p j ∈ B p i } ) R t ′ ( p j ) N p j = ( 1 − d ) + d ∑ j = 1 n N p j R t ′ ( p j ) N p j = 1 \begin{aligned}
\sum_{i = 1}^{n} R'_{t + 1}(p_i) &= (1 - d) + d\sum_{i = 1}^{n}\sum_{q \in B_{p_i}}\frac{R'_{t}(q)}{N_q} \\
&= (1 - d) + d\sum_{i = 1}^{n}\sum_{j = 1}^{n}\frac{R'_{t}(p_j)}{N_{p_j}}\mathbb{I}_{\{p_j \in B_{p_i}\}}\\
&= (1 - d) + d\sum_{j = 1}^{n}(\sum_{i = 1}^{n}\mathbb{I}_{\{p_j \in B_{p_i}\}})\frac{R'_{t}(p_j)}{N_{p_j}}\\
&= (1 - d) + d\sum_{j = 1}^{n}N_{p_j}\frac{R'_{t}(p_j)}{N_{p_j}}\\
& = 1
\end{aligned} i = 1 ∑ n R t + 1 ′ ( p i ) = ( 1 − d ) + d i = 1 ∑ n q ∈ B p i ∑ N q R t ′ ( q ) = ( 1 − d ) + d i = 1 ∑ n j = 1 ∑ n N p j R t ′ ( p j ) I { p j ∈ B p i } = ( 1 − d ) + d j = 1 ∑ n ( i = 1 ∑ n I { p j ∈ B p i } ) N p j R t ′ ( p j ) = ( 1 − d ) + d j = 1 ∑ n N p j N p j R t ′ ( p j ) = 1 从而由归纳法知，命题对 ∀ t ≥ 0 \forall t \geq 0 ∀ t ≥ 0
Computing PageRank
我们知道 PageRank 的迭代公式为
R ′ t + 1 = 1 − d n 1 + d A R ′ t \mathbf{R'}_{t + 1} = \frac{1 - d}{n}\mathbf{1} + dA\mathbf{R'}_{t} R ′ t + 1 = n 1 − d 1 + d A R ′ t 通过迭代法来计算 PageRank 值，在以下任一条件终止
对于某极小值 ϵ > 0 \epsilon > 0 ϵ > 0 ∣ R ′ t + 1 − R ′ t < ϵ ∣ |\mathbf{R'}_{t + 1} - \mathbf{R'}_{t} < \epsilon| ∣ R ′ t + 1 − R ′ t < ϵ ∣
迭代次数 t > K t > K t > K K K K
原文中，在规模约 322 , 000 , 000 322,000,000 322 , 000 , 000 52 52 52 45 45 45
在 PageRank 的计算过程中，我们并没有考虑到用户查询的影响。事实上，PageRank 是一个与用户查询无关的静态算法，其可以预先离线计算并存储，从而大大减少用户进行在线查询时实时的计算量。