1707611814
1707611815
1707611816
1707611817
因为星星在那里：科学殿堂的砖与瓦 [:1707611258]
1707611818
因为星星在那里：科学殿堂的砖与瓦 三、问题及解决
1707611819
1707611820
1707611821
如前所述，佩奇和布林是用虚拟用户在经过很长——理论上为无穷长——时间的漫游后访问各网页的几率分布，即，来确定网页排序的。这个定义要想管用，显然要解决三个问题：
1707611822
1707611823
1707611824
（1）极限是否存在？
1707611825
1707611826
（2）如果极限存在，它是否与p0的选取无关？
1707611827
1707611828
（3）如果极限存在，并且与p0的选取无关，它作为网页排序的依据是否真的合理？
1707611829
1707611830
如果这三个问题的答案都是肯定的，那么网页排序问题就算解决了。反之，哪怕只有一个问题的答案是否定的，网页排序问题也就不能算是得到了满意解决。那么实际答案如何呢？很遗憾，是后一种，而且是其中最糟糕的情形，即三个问题的答案全都是否定的。这可以由一些简单的例子看出。比方说，在只包含两个相互链接网页的迷你型互联网上，如果p0=（1，0）T，极限就不存在（因为几率分布将在（1，0）T和（0，1）T之间无穷振荡）。而存在几个互不连通（即互不链接）区域的互联网则会使极限——即便存在——与p0的选取有关（因为把p0选在不同区域内显然会导致不同极限）。至于极限存在，并且与p0的选取无关时它作为网页排序的依据是否真的合理的问题，虽然不是数学问题，答案却也是否定的，因为任何一个“悬挂网页”都能像黑洞一样，把其他网页的几率“吸收”到自己身上（因为虚拟用户一旦进入那样的网页，就会由于没有对外链接而永远停留在那里），这显然是不合理的。这种不合理效应是如此显著，以至于在一个连通性良好的互联网上，哪怕只有一个“悬挂网页”，也足以使整个互联网的网页排序失效，可谓是“一粒老鼠屎坏了一锅粥”。
1707611831
1707611832
为了解决这些问题，佩奇和布林对虚拟用户的行为进行了修正。首先，他们意识到无论真实用户还是虚拟用户，当他们访问到“悬挂网页”时，都不应该也不会“在一棵树上吊死”，而是会自行访问其他网页。对于真实用户来说，自行访问的网页显然与个人的兴趣有关，但对于在平均意义上代表真实用户的虚拟用户来说，佩奇和布林假定它将会在整个互联网上随机选取一个网页进行访问。用数学语言来说，这相当于是把H的列向量中所有的零向量都换成e/N（其中e是所有分量都为1的列向量，N为互联网上的网页总数）。如果我们引进一个描述“悬挂网页”的指标向量（indicator vector）a，它的第i个分量的取值视Wi是否为“悬挂网页”而定——如果是“悬挂网页”，取值为1，否则为0——并用S表示修正后的矩阵，则
1707611833
1707611834
1707611835
1707611836
1707611837
显然，这样定义的S矩阵的每一列的矩阵元之和都是1，从而是一个不折不扣的随机矩阵。这一修正因此而被称为随机性修正（stochasticity adjustment）。这一修正相当于剔除了“悬挂网页”，从而可以给上述第三个问题带来肯定回答（当然，这一回答没有绝对标准，可以不断改进）。不过，这一修正解决不了前两个问题。为了解决那两个问题，佩奇和布林引进了第二个修正。他们假定，虚拟用户虽然是虚拟的，但多少也有一些“性格”，不会完全受当前网页所限，死板地只访问其所提供的链接。具体地说，他们假定虚拟用户在每一步都有一个小于1的几率α访问当前网页所提供的链接，同时却也有一个几率1-α不受那些链接所限，随机访问互联网上的任何一个网站。用数学语言来说（请读者自行证明），这相当于是把上述S矩阵变成了一个新的矩阵G：
1707611838
1707611839
1707611840
1707611841
1707611842
这个矩阵不仅是一个随机矩阵，而且由于第二项的加盟，它有了一个新的特点，即所有矩阵元都为正，（请读者想一想，这一特点的“物理意义”是什么？）这样的矩阵是所谓的素矩阵（primitive matrix）[5]。这一修正因此而被称为素性修正（primitivity adjustment）。
1707611843
1707611844
经过这两类修正，网页排序的计算方法就变成了
1707611845
1707611846
pn = Gnp0
1707611847
1707611848
这个算法能给上述问题提供肯定答案吗？是的，它能。因为随机过程理论中有一个所谓的马尔可夫链基本定理（fundamental theorem of Markov chains），它表明在一个马尔可夫过程中，如果转移矩阵是素矩阵，那么上述前两个问题的答案就是肯定的。而随机性修正已经解决了上述第三个问题，因此所有问题就都解决了。如果我们用p表示pn的极限[6]，则p给出的就是整个互联网的网页排序——它的每一个分量就是相应网页的访问几率，几率越大，排序就越靠前。
1707611849
1707611850
这样，佩奇和布林就找到了一个不仅含义合理，而且数学上严谨的网页排序算法，他们把这个算法称为PageRank，不过要注意的是，虽然这个名称的直译恰好是“网页排序”，但它实际上指的是“佩奇排序”，因为其中的“Page”不是指网页，而是佩奇的名字。这个算法就是谷歌排序的数学基础，而其中的矩阵G则被称为谷歌矩阵（Google matrix）。
1707611851
1707611852
细心的读者可能注意到了，我们还遗漏了一样东西，那就是谷歌矩阵中描述虚拟用户“性格”的那个α参数。那个参数的数值是多少呢？从理论上讲，它应该来自于对真实用户平均行为的分析，不过实际上另有一个因素对它的选取产生了很大影响，那就是Gnp0收敛于p的快慢程度。由于G是一个NXN矩阵，而N为互联网上——确切地说是被谷歌所收录的——网页的总数，在谷歌成立之初为几千万，目前为几百亿（并且还在持续增加），是一个极其巨大的数字。因此G是一个超大型矩阵，甚至很可能是人类有史以来处理过的最庞大的矩阵。对于这样的矩阵，Gnp0收敛速度的快慢是关系到算法是否实用的重要因素，而这个因素恰恰与α有关。可以证明，α越小，Gnp0的收敛速度就越快。但α也不能太小，因为太小的话，“佩奇排序”中最精华的部分，即以网页间的彼此链接为基础的排序思路就被弱化了（因为这部分的贡献正比于α），这显然是得不偿失的。因此，在α的选取上有很多折中的考虑要做，佩奇和布林最终选择的数值是α=0.85。
1707611853
1707611854
以上就是谷歌背后最重要的数学奥秘。与以往那种凭借关键词出现次数所作的排序不同，这种由所有网页的相互链接所确定的排序是不那么容易做假的，因为作假者再是把自己的网页吹得天花乱坠，如果没有真正吸引人的内容，别人不链接它，一切就还是枉然[7]。而且“佩奇排序”还有一个重要特点，那就是它只与互联网的结构有关，而与用户具体搜索的东西无关。这意味着排序计算可以单独进行，而无需在用户键入搜索指令后才临时进行。谷歌搜索的速度之所以快捷，在很大程度上得益于此。
1707611855
1707611856
1707611857
1707611858
1707611859
因为星星在那里：科学殿堂的砖与瓦 [:1707611259]
1707611860
因为星星在那里：科学殿堂的砖与瓦 四、结语
1707611861
1707611862
在本文的最后，我们顺便介绍一点谷歌公司的历史。佩奇和布林对谷歌算法的研究由于需要收集和分析大量网页间的相互链接，从而离不开硬件支持。为此，早在研究阶段，他们就四处奔走，为自己的研究筹集资金和硬件。1998年9月，他们为自己的试验系统注册了公司——即如今大名鼎鼎的谷歌公司。但这些行为虽然近乎于创业，他们两人当时却并无长期从商的兴趣。1999年，当他们觉得打理公司干扰了自己的研究时，甚至萌生了卖掉公司的想法。
1707611863