它成为了一个不折不扣的数学问题。
思路虽然有了,具体计算却并非易事,因为按照这种思路,想要知道一个网页 wi 的排序,不仅要知道有多少网页链接了它,而且还得知道那些网页各自的排序——因为来自排序靠前网页的链接更“值钱”。但作为互联网大家庭的一员, wi 本身对其它网页的排序也是有贡献的,而且基于来自排序靠前网页的链接更“值钱”的原则,这种贡献与 wi 的排序有关。这样一来,我们就陷入了一个“先有鸡还是先有蛋”的循环之中:想要知道 wi 的排序,就得知道与它链接的其它网页的排序,而想要知道那些网页的排序,却又首先得知道 wi 的排序。
为了打破这个循环,佩奇和布林采用了一个很巧妙的思路,即分析一个虚拟用户在互联网上的漫游过程。他们假定:虚拟用户一旦访问了一个网页后,下一步将有相同的几率访问被该网页所链接的任何一个其它网页。换句话说,如果网页 wi 有 ni 个对外链接,则虚拟用户在访问了 wi 之后,下一步点击这些链接中任何一个的几率均为 1/ni。初看起来,这一假设并不合理,因为任何用户都有偏好,怎么可能以相同的几率访问一个网页的所有链接呢?但如果我们考虑到佩奇和布林的虚拟用户实际上是对互联网上全体用户的一种平均意义上的代表,这条假设就不象初看起来那么不合理了。那么网页的排序由什么来决定呢?是由该用户在漫游了很长时间(理论上为无穷长时间)后访问各网页的几率分布来决定,访问几率越大的网页排序就越靠前。
为了将这一分析数学化,我们用 pi(n)表示虚拟用户在进行第 n 次浏览时访问网页 wi 的几率。显然,上述假设可以表述为(请读者自行证明):pi(n+1)=Σj pj(n)pji/nj
这里 pji 是一个描述互联网链接结构的指标函数(indicator function),其定义是:如果网页 wj 有链接指向网页 wi,则 pji 取值为 1,反之则为 0。显然,这条假设所体现的正是前面提到的佩奇和布林的排序原则,因为右端求和式的存在表明与 wi 有链接的所有网页 wj 都对 wi 的排名有贡献,而求和式中的每一项都正比于 pj,则表明来自那些网页的贡献与它们的自身排序有关,自身排序越靠前(即 pj 越大),贡献就越大。
为符号简洁起见,我们将虚拟用户第 n 次浏览时访问各网页的几率合并为一个列向量 pn,它的第 i 个分量为 pi(n),并引进一个只与互联网结构有关的矩阵 h,它的第 i 行 j 列的矩阵元为 hij = pji/nj,则上述公式可以改写为:pn+1 = hpn
这就是计算网页排序的公式。
熟悉随机过程理论的读者想必看出来了,上述公式描述的是一种马尔可夫过程(markov process),而且是其中最