PageRank

PageRank算法

想要知道一个网页 $W_i$的排序， 不仅要知道有多少网页链接了它， 而且还得知道那些网页各自的排序——因为来自排序靠前网页的链接更有分量。 但作为互联网大家庭的一员， $W_i$ 本身对其它网页的排序也是有贡献的， 而且基于来自排序靠前网页的链接更有分量的原则， 这种贡献与 $W_i$ 本身的排序也有关。 这样一来， 我们就陷入了一个 “先有鸡还是先有蛋” 的循环： 要想知道 $W_i$ 的排序， 就得知道与它链接的其它网页的排序， 而要想知道那些网页的排序， 却又首先得知道 $W_i$ 的排序。这就陷入了先有鸡还是先有蛋的循环。

为了打破这个循环， 佩奇和布林采用了一个很巧妙的思路， 即分析一个虚拟用户在互联网上的漫游过程。 他们假定： 虚拟用户一旦访问了一个网页后， 下一步将有相同的几率访问被该网页所链接的任何一个其它网页。

如果网页 $W_i$ 有 $N_i$ 个对外链接， 则虚拟用户在访问了 $W_i$ 之后， 下一步点击那些链接当中的任何一个的几率均为 $1/N_i$。
我们用 $p_i(n)$ 表示虚拟用户在进行第 $ n $ 次浏览时访问网页 $W_i$ 的几率

$$p_i(n+1)=\sum_{j} p_j(n)p_{j->i}/N_{j}$$

我们将虚拟用户第 n 次浏览时访问各网页的几率合并为一个列向量 $p_n$， 它的第 i 个分量为 $p_i$(n)， 并引进一个只与互联网结构有关的矩阵 H， 它的第 i 行 j 列的矩阵元为 $H_{ij} = p_{j->i}/N_{j}$

$$p_{n+1} = Hp_n$$

上述公式描述的是一种马尔可夫过程 (Markov process)， 而且是其中最简单的一类， 即所谓的平稳马尔可夫过程 (stationary Markov process),而 H 则是描述马尔可夫过程中的转移概率分布的所谓转移矩阵 (transition matrix)。

$$p_n = H^np_0$$

其中 $p_0$ 为虚拟读者初次浏览时访问各网页的几率分布 (在佩奇和布林的原始论文中， 这一几率分布被假定为是均匀分布)。

第一次修正：悬挂网页-随机性修正

无论真实用户还是虚拟用户， 当他们访问到 “悬挂网页” 时， 都不应该，也不会 “在一棵树上吊死”， 而是会自行访问其它网页。 对于真实用户来说， 自行访问的网页显然与各人的兴趣有关， 但对于在平均意义上代表真实用户的虚拟用户来说， 佩奇假定它将会在整个互联网上随机选取一个网页进行访问。 用数学语言来说， 这相当于是把 H 的列向量中所有的零向量都换成 e/N (其中 e 是所有分量都为 1 的列向量， N 为互联网上的网页总数)。 如果我们引进一个描述 “悬挂网页” 的指标向量 (indicator vector) a， 它的第 i 个分量的取值视 $W_i$ 是否为 “悬挂网页” 而定——如果是 “悬挂网页”， 取值为 1， 否则为 0——并用 S 表示修正后的矩阵， 则：

$$S = H+ea^{T}/N$$

显然， 这样定义的 S 矩阵的每一列的矩阵元之和都是 1， 从而是一个不折不扣的随机矩阵。 这一修正因此而被称为随机性修正 (stochasticity adjustment)。

第二次修正：直接跳转-素性修正

他们假定， 虚拟用户虽然是虚拟的， 但多少也有一些 “性格”， 不会完全受当前网页所限， 死板地只访问其所提供的链接。 具体地说， 他们假定虚拟用户在每一步都有一个小于 1 的几率 $\alpha$访问当前网页所提供的链接， 同时却也有一个几率 $1-\alpha$ 不受那些链接所限， 随机访问互联网上的任何一个网站。（比如直接从书签栏访问网页）
于是把上述 S 矩阵变成了一个新的矩阵

$$G = \alpha S + (1-\alpha)ee^T/N$$

这个矩阵不仅是一个随机矩阵， 而且由于第二项的加盟， 它有了一个新的特点， 即所有矩阵元都为正。 这样的矩阵是所谓的素矩阵 (primitive matrix)。 这一修正因此而被称为素性修正 (primitivity adjustment)。

$G^np_0$ 收敛速度的快慢是关系到算法是否实用的重要因素， 而这个因素恰恰与 $\alpha$ 有关。 可以证明， $\alpha$ 越小， $G^np_0$ 的收敛速度就越快。 但 $\alpha$ 也不能太小， 因为太小的话， “佩奇排序” 中最精华的部分， 即以网页间的彼此链接为基础的排序思路就被弱化了 (因为这部分的贡献正比于 $\alpha$)， 这显然是得不偿失的。 因此， 在 $\alpha$ 的选取上有很多折衷的考虑要做， 佩奇最终选择的数值是 $\alpha$ = 0.85。

p 其实是矩阵 G 的特征值为 1 的本征向量， 而利用虚拟用户确定网页排序的思路其实是在用迭代法解决上述特征值问题。 在数学上可以证明， 上述特征向量是唯一的， 而且 G 的其它特征值 $\lambda$ 全都满足 |$\lambda$|<1 (更准确地说， 是 |$\lambda|≤ \alpha$——这也正是 $G^np_0$ 的收敛速度与 $\alpha$ 有关的原因)。

这个算法就是谷歌排序的数学基础， 而其中的矩阵 G 则被称为谷歌矩阵 (Google matrix)。