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