谷歌背后的数学( 二 ) _小知识

就是在这种情况下， 1996 年初，谷歌公司的创始人，当时还是美国斯坦福大学 (Stanford University) 研究生的佩奇 (Larry Page) 和布林 (Sergey Brin) 开始了对网页排序问题的研究。这两位小伙子之所以研究网页排序问题，一来是导师的建议 (佩奇后来称该建议为 “我有生以来得到过的最好建议”)，二来则是因为他们对这一问题背后的数学产生了兴趣。
网页排序问题的背后有什么样的数学呢? 这得从佩奇和布林看待这一问题的思路说起。在佩奇和布林看来，网页的排序是不能靠每个网页自己来标榜的，无论把关键词重复多少次，垃圾网页依然是垃圾网页。那么，究竟什么才是网页排序的可靠依据呢? 出生于书香门第的佩奇和布林 (两人的父亲都是大学教授) 想到了学术界评判学术论文重要性的通用方法，那就是看论文的引用次数。在互联网上，与论文引用相类似的是显然是网页链接。因此，佩奇和布林萌生了一个网页排序的思路，那就是通过研究网页间的相互链接来确定排序。具体地说，一个网页被其它网页链接得越多，它的排序就越靠前。不仅如此，佩奇和布林还进一步提出，一个网页越是被排序靠前的网页所链接，它的排序就也应该越靠前。这一条的意义也是不言而喻的，就好比一篇论文被诺贝尔奖得主所引用，显然要比被普通研究者所引用更说明其价值。依照这个思路，网页排序问题就跟整个互联网的链接结构产生了关系，正是这一关系使它成为了一个不折不扣的数学问题。
思路虽然有了，具体计算却并非易事，因为按照这种思路，想要知道一个网页 Wi 的排序，不仅要知道有多少网页链接了它，而且还得知道那些网页各自的排序——因为来自排序靠前网页的链接更 “值钱” 。但作为互联网大家庭的一员， Wi 本身对其它网页的排序也是有贡献的，而且基于来自排序靠前网页的链接更 “值钱” 的原则，这种贡献与 Wi 的排序有关。这样一来，我们就陷入了一个 “先有鸡还是先有蛋” 的循环之中：想要知道 Wi 的排序，就得知道与它链接的其它网页的排序，而想要知道那些网页的排序，却又首先得知道 Wi 的排序。
为了打破这个循环，佩奇和布林采用了一个很巧妙的思路，即分析一个虚拟用户在互联网上的漫游过程。他们假定：虚拟用户一旦访问了一个网页后，下一步将有相同的几率访问被该网页所链接的任何一个其它网页。换句话说，如果网页 Wi 有 Ni 个对外链接，则虚拟用户在访问了 Wi 之后，下一步点击这些链接中任何一个的几率均为 1/Ni 。初看起来，这一假设并不合理，因为任何用户都有偏好，怎么可能以相同的几率访问一个网页的所有链接呢? 但如果我们考虑到佩奇和布林的虚拟用户实际上是对互联网上全体用户的一种平均意义上的代表，这条假设就不象初看起来那么不合理了。那么网页的排序由什么来决定呢? 是由该用户在漫游了很长时间 (理论上为无穷长时间) 后访问各网页的几率分布来决定，访问几率越大的网页排序就越靠前。
为了将这一分析数学化，我们用 pi(n) 表示虚拟用户在进行第 n 次浏览时访问网页 Wi 的几率。显然，上述假设可以表述为 (请读者自行证明)：
pi(n+1) = Σj pj(n)pj→i/Nj
这里 pj→i 是一个描述互联网链接结构的指标函数 (indicator function)，其定义是：如果网页 Wj 有链接指向网页 Wi，则 pj→i 取值为 1，反之则为 0 。显然，这条假设所体现的正是前面提到的佩奇和布林的排序原则，因为右端求和式的存在表明与 Wi 有链接的所有网页 Wj 都对 Wi 的排名有贡献，而求和式中的每一项都正比于 pj，则表明来自那些网页的贡献与它们的自身排序有关，自身排序越靠前 (即 pj 越大)，贡献就越大。
为符号简洁起见，我们将虚拟用户第 n 次浏览时访问各网页的几率合并为一个列向量 pn，它的第 i 个分量为 pi(n)，并引进一个只与互联网结构有关的矩阵 H，它的第 i 行 j 列的矩阵元为 Hij = pj→i/Nj，则上述公式可以改写为：
pn+1 = Hpn
这就是计算网页排序的公式。
熟悉随机过程理论的读者想必看出来了，上述公式描述的是一种马尔可夫过程 (Markov process)，而且是其中最简单的一类，即所谓的平稳马尔可夫过程 (stationary Markov process)[注一]，而 H 则是描述转移概率的所谓转移矩阵 (transition matrix) 。不过普通马尔可夫过程中的转移矩阵通常是随机矩阵 (stochastic matrix)，即每一列的矩阵元之和都为 1 的矩阵 (请读者想一想，这一特点的 “物理意义” 是什么?)[注二] 。而我们的矩阵 H 却可能有一些列是零向量，从而矩阵元之和为 0，它们对应于那些没有对外链接的网页，即所谓的 “悬挂网页” (dangling page)[注三] 。