PageRank 2020-04-27 PageRank GoogleRationale
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 出链的数目。简化版的 PageRank 值 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 为正则化常数,使得整体值收敛。该公式形式化了我们之前对 PageRank 算法的概括:页面 p p p 的 PageRank 值为其入链贡献之和。这里注意到,每个入链 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 是 PageRank 值的向量表示
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 。阻尼系数基于这样一个假设:在用户随机地点击页面链接进行浏览的过程中,如果用户进入了一个 rank sink,他并不会在这组网页中无限循环,而是很有可能停止点击,随机开启另一个新的页面重新开始浏览。这样,经过修改的完整 PageRank 算法 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 次迭代,PageRank 值基本收敛;在一半规模的数据集上,则经过 45 45 45 次迭代后收敛。
在 PageRank 的计算过程中,我们并没有考虑到用户查询的影响。事实上,PageRank 是一个与用户查询无关的静态算法,其可以预先离线计算并存储,从而大大减少用户进行在线查询时实时的计算量。