1707611760
1707611761
谷歌作为一个搜索引擎，它的核心功能顾名思义，就是网页搜索。说到搜索，我们都不陌生，因为那是凡地球人都会的技能。我们在字典里查个生字，在图书馆里找本图书，甚至在商店里寻一种商品，等等，都是搜索。只要稍稍推究一下，我们就会发现那些搜索之所以可能，并且人人都会，在很大程度上得益于以下三条：
1707611762
1707611763
（1）搜索对象的数量较小——比如一本字典收录的字通常只有一两万个，一家图书馆收录的不重复图书通常不超过几十万种，一家商店的商品通常不超过几万种，等等。
1707611764
1707611765
（2）搜索对象具有良好的分类或排序——比如字典里的字按拼音排序，图书馆里的图书按主题分类，商店里的商品按品种或用途分类，等等。
1707611766
1707611767
（3）搜索结果的重复度较低——比如字典里的同音字通常不超过几十个，图书馆里的同名图书和商店里的同种商品通常也不超过几十种，等等。
1707611768
1707611769
但互联网的鲜明特点却是以上三条无一满足。事实上，即便在谷歌问世之前，互联网上的网页总数就已超过了诸如图书馆藏书数量之类传统搜索对象的数目。而且这还只是冰山一角，因为与搜索图书时单纯的书名搜索不同，互联网上的搜索往往是对网页内容的直接搜索，这相当于将图书里的每一个字都变成了搜索对象，由此导致的数量才是真正惊人的，它不仅直接破坏了上述第一条，而且连带破坏了二、三两条。在互联网发展的早期，像雅虎（Yahoo）那样的门户网站曾试图为网页建立分类系统，但随着网页数量的激增，这种做法很快就“挂一漏万”了。而搜索结果的重复度更是以快得不能再快的速度走向失控。这其实是可以预料的，因为几乎所有网页都离不开几千个常用词，因此除非搜索生僻词，否则出现几十万、几百万、甚至几千万条搜索结果都是不足为奇的。
1707611770
1707611771
互联网的这些“不良特点”给搜索引擎的设计带来了极大的挑战。而在这些挑战之中，相对来说，对一、二两条的破坏是比较容易解决的，因为那主要是对搜索引擎的存储空间和计算能力提出了较高要求，只要有足够多的钱来买“装备”，这些都还能算是容易解决的——套用电视连续剧《蜗居》中某贪官的台词来说，“能用钱解决的问题就不是大问题”。但对第三条的破坏却要了命了，因为无论搜索引擎的硬件如何强大，速度如何快捷，要是搜索结果有几百万条，那么任何用户想从其中“海选”出自己真正想要的东西都是几乎不可能的。这一点对早期搜索引擎来说可谓是致命伤，而且它不是用钱就能解决的问题。
1707611772
1707611773
这致命伤该如何治疗呢？药方其实很简单，那就是对搜索结果进行排序，把用户最有可能需要的网页排在最前面，以确保用户能很方便地找到它们。但问题是：网页的水平千差万别，用户的喜好更是万别千差，互联网上有一句流行语叫做：“在互联网上，没人知道你是一条狗（On the Internet, nobody knows you’re a dog）。”连用户是人是狗都“没人知道”，搜索引擎又怎能知道哪些搜索结果是用户最有可能需要的，并对它们进行排序呢？
1707611774
1707611775
在谷歌主导互联网搜索之前，多数搜索引擎采用的排序方法，是以被搜索词语在网页中的出现次数来决定排序——出现次数越多的网页排在越前面。这个判据不能说毫无道理，因为用户搜索一个词语，通常表明对该词语感兴趣。既然如此，那该词语在网页中的出现次数越多，就越有可能表示该网页是用户所需要的。可惜的是，这个貌似合理的方法实际上却行不大通。因为按照这种方法，任何一个像祥林嫂一样翻来覆去倒腾某些关键词的网页，无论水平多烂，一旦被搜索到，都立刻会“金榜题名”，这简直就是广告及垃圾网页制造者的天堂。事实上，当时几乎没有一个搜索引擎不被“祥林嫂”们所困扰，其中最具讽刺意味的是：在谷歌诞生之前的1997年11月，堪称早期互联网巨子的当时四大搜索引擎在搜索自己公司的名字时，居然只有一个能使之出现在搜索结果的前十名内，其余全被“祥林嫂”们挤跑了。
1707611776
1707611777
1707611778
1707611779
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