PageRank算法

You are here:

Home
随记
PageRank算法

2008-10-15 Leave a comment随记By nhuang

假设一个由4个页面组成的小团体：A，B， C 和 D。如果所有页面都链向A，那么A的PR（PageRank）值将是B，C 及 D的和。

P R (A) = P R (B) + P R (C) + P R (D)

继续假设B也有链接到C，并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的 PageRank 上。

$PR(A)= \frac{PR(B)}{2}+ \frac{PR(C)}{1}+ \frac{PR(D)}{3}$

换句话说，根据链处总数平分一个页面的PR值。

$PR(A)= \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}$

最后，所有这些被换算为一个百分比再乘上一个系数q。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值 $1 - q$ 。

$PR(A)=\left( \frac{PR(B)}{L(B)}+ \frac{PR(C)}{L(C)}+ \frac{PR(D)}{L(D)}+\,\cdots \right) q + 1 - q$

所以一个页面的 PageRank 是由其他页面的PageRank计算得到。Google 不断的重复计算每个页面的 PageRank。如果您给每个页面一个随机 PageRank 值（非0），那么经过不断的重复计算，这些页面的 PR 值会趋向于正常和稳定。这就是搜索引擎使用它的原因。

完整的

这个方程式引入了随机浏览的概念，即有人上网无聊随机打开一些页面，点一些链接。一个页面的PageRank值也影响了它被随机浏览的概率。为了便于理解，这里假设上网者不断点网页上的链接，最终到了一个没有任何链出页面的网页，这时候上网者会随机到另外的网页开始浏览。

为了对那些有链出的页面公平， $q = 0.15$ (q的意义见上文)的算法被用到了所有页面上, 估算页面可能被上网者放入书签的概率。

所以，这个等式如下:

${\rm PageRank}(p_i) = \frac{q}{N} + (1 -q) \sum_{p_j} \frac{{\rm PageRank} (p_j)}{L(p_j)}$

$p 1, p 2,\dots, p N$ 是被研究的页面， $M (p i)$ 是链入 $p i$ 页面的数量， $L (p j)$ 是 $p j$ 链出页面的数量，而N是所有页面的数量。

PageRank值是一个特殊矩阵中的特征向量。这个特征向量为

$\mathbf{R} = \begin{bmatrix} {\rm PageRank}(p_1) \\ {\rm PageRank}(p_2) \\ \vdots \\ {\rm PageRank}(p_N) \end{bmatrix}$

R是等式的答案

$\mathbf{R} = \begin{bmatrix} {q / N} \\ {q / N} \\ \vdots \\ {q / N} \end{bmatrix} + (1-q) \begin{bmatrix} \ell(p_1,p_1) & \ell(p_1,p_2) & \cdots & \ell(p_1,p_N) \\ \ell(p_2,p_1) & \ddots & & \\ \vdots & & \ell(p_i,p_j) & \\ \ell(p_N,p_1) & & & \ell(p_N,p_N) \end{bmatrix} \mathbf{R}$