World of Mathematics数学烟云 oogle 谷歌背后的数学 卢昌海 在如今这个互联网时代,有一家家喻户晓的公司,它自通常不超过几十个,图书馆里的同名图书和商店里的同种商 1998年问世以来,在极短的时间内就声誉鹊起,不仅超越了品通常也不超过几十种。 所有竞争对手,而且彻底改观了整个互联网的生态。这家公 但互联网的鲜明特点却是以上三条无一满足。事实上 司就是当今互联网上的第一搜索引擎:谷歌( Google) 即便在谷歌问世之前,互联网上的网页总数就己超过了诸如 在这样一家显赫的公司背后,自然有许许多多商战故图书馆藏书数量之类传统搜索对象的数目。而且这还只是 事,也有许许多多成功因素。但与普通商战故事不同的是,冰山一角,因为与搜索图书时单纯的书名搜索不同,互联 在谷歌的成功背后起着最关键作用的却是一个数学因素。 网上的搜索往往是对网页内容的直接搜索,这相当于将图书 本文要谈的就是这个数学因素 内的每一个字都变成了搜索对象,由此导致的数量才是真 谷歌作为一个搜索引擎,它的核心功能顾名思义,就是正惊人的,它不仅直接破坏了上述第一条,而且连带破坏了 网页搜索。说到搜索,我们都不陌生,因为那是凡地球人都二、三两条。在互联网发展的早期,象 Yahoo那样的门户 会的技能。我们在字典里查个生字,在图书馆里找本图书,网站曾试图为网页建立分类系统,但随着网页数量的激增 甚至在商店里寻一种商品等,都是搜索。如果我们稍稍推究这种做法很快就“挂一漏万”了。而搜索结果的重复度更 下的话,就会发现那些搜索之所以可能,并且人人都会,是以快得不能再快的速度走向失控。这其实是可以预料的 在很大程度上得益于以下三条 因为几乎所有网页都离不开几千个常用词,因此除非搜索 1.搜索对象的数量较小——比如一本字典收录的字生僻词,否则出现几十万、几百万、甚至几千万条搜索结 通常只有一两万个,一家图书馆收录的不重复图书通常不果都是不足为奇的。 过几十万种,一家商店的商品通常不超过几万种等。 互联网的这些“不良特点”给搜索引擎的设计带来了极 2.搜索对象具有良好的分类或排序—一比如字典里大的挑战。而在这些挑战之中,相对来说,对一、二两条的 的字按拼音排序,图书馆里的图书按主题分类,商店里的破坏是比较容易解决的,因为那主要是对搜索引擎的存储空 商品按品种或用途分类等 间和计算能力提出了较高要求,只要有足够多的钱来买“装 3.搜索结果的重复度较低——比如字典里的同音字备”,这些还算是容易解决的。套用电视连续剧《蜗居》中 数学文化/第2卷第1期12
World of Mathematics 数学烟云 数学文化/第2卷第1期 12 在如今这个互联网时代，有一家家喻户晓的公司，它自 1998 年问世以来，在极短的时间内就声誉鹊起，不仅超越了 所有竞争对手，而且彻底改观了整个互联网的生态。这家公 司就是当今互联网上的第一搜索引擎 ：谷歌 (Google)。 在这样一家显赫的公司背后，自然有许许多多商战故 事，也有许许多多成功因素。但与普通商战故事不同的是， 在谷歌的成功背后起着最关键作用的却是一个数学因素。 本文要谈的就是这个数学因素。 谷歌作为一个搜索引擎，它的核心功能顾名思义，就是 网页搜索。说到搜索，我们都不陌生，因为那是凡地球人都 会的技能。我们在字典里查个生字，在图书馆里找本图书， 甚至在商店里寻一种商品等，都是搜索。如果我们稍稍推究 一下的话，就会发现那些搜索之所以可能，并且人人都会， 在很大程度上得益于以下三条 ： 1. 搜索对象的数量较小——比如一本字典收录的字 通常只有一两万个，一家图书馆收录的不重复图书通常不 超过几十万种，一家商店的商品通常不超过几万种等。 2. 搜索对象具有良好的分类或排序——比如字典里 的字按拼音排序，图书馆里的图书按主题分类，商店里的 商品按品种或用途分类等。 3. 搜索结果的重复度较低——比如字典里的同音字 通常不超过几十个，图书馆里的同名图书和商店里的同种商 品通常也不超过几十种。 但互联网的鲜明特点却是以上三条无一满足。事实上， 即便在谷歌问世之前，互联网上的网页总数就已超过了诸如 图书馆藏书数量之类传统搜索对象的数目。而且这还只是 冰山一角，因为与搜索图书时单纯的书名搜索不同，互联 网上的搜索往往是对网页内容的直接搜索，这相当于将图书 内的每一个字都变成了搜索对象，由此导致的数量才是真 正惊人的，它不仅直接破坏了上述第一条，而且连带破坏了 二、三两条。在互联网发展的早期，象 Yahoo 那样的门户 网站曾试图为网页建立分类系统，但随着网页数量的激增， 这种做法很快就“挂一漏万”了。而搜索结果的重复度更 是以快得不能再快的速度走向失控。这其实是可以预料的， 因为几乎所有网页都离不开几千个常用词，因此除非搜索 生僻词，否则出现几十万、几百万、甚至几千万条搜索结 果都是不足为奇的。 互联网的这些“不良特点”给搜索引擎的设计带来了极 大的挑战。而在这些挑战之中，相对来说，对一、二两条的 破坏是比较容易解决的，因为那主要是对搜索引擎的存储空 间和计算能力提出了较高要求，只要有足够多的钱来买“装 备”，这些还算是容易解决的。套用电视连续剧《蜗居》中 谷歌背后的数学 卢昌海
World of Mathematics数学烟云 某贪官的台词来说,“能用钱解决的问题就不是大问题”。确定排序。具体地说,一个网页被其它网页链接得越多,它 但对第三条的破坏却要了命了,因为无论搜索引擎的硬件如的排序就越靠前。不仅如此,佩奇和布林还进一步提出 何强大,速度如何快捷,要是搜索结果有几百万条,那么任个网页越是被排序靠前的网页所链接,它的排序就也应该越 何用户想从其中“海选”出自己真正想要的东西都是几乎不靠前。这一条的意义也是不言而喻的,就好比一篇论文被诺 可能的。这一点对早期搜索引擎来说可谓是致命伤,而且它贝尔奖得主所引用,显然要比被普通研究者所引用更说明其 不是用钱就能解决的问题。 价值。依照这个思路,网页排序问题就跟整个互联网的链接 这致命伤该如何治疗呢?药方其实很简单,那就是对结构产生了关系,正是这一关系使它成为了一个不折不扣的 搜索结果进行排序,把用户最有可能需要的网页排在最前数学问题 面,以确保用户能很方便地找到它们。但问题是:网页的水 思路虽然有了,具体计算却并非易事,因为按照这种 平千差万别,用户的喜好更是万别千差,互联网上有一句思路,想要知道一个网页W的排序,不仅要知道有多少网 流行语叫做:“在互联网上,没人知道你是一条狗”( On the页链接了它,而且还得知道那些网页各自的排序—因为来 Internet, nobody knows you' re a dog)。连用户是人是狗都“没自排序靠前网页的链接更“值钱”。但作为互联网大家庭的 人知道”,搜索引擎又怎能知道哪些搜索结果是用户最有可一员,W;本身对其它网页的排序也是有贡献的,而且基于 能需要的,并对它们进行排序呢 来自排序靠前网页的链接更“值钱”的原则,这种贡献与W1 在谷歌主导互联网搜索之前,多数搜索引擎采用的排的排序有关。这样一来,我们就陷入了一个“先有鸡还是先 序方法,是以被搜索词语在网页中的出现次数来决定排序,有蛋”的循环之中:想要知道W的排序,就得知道与它链 出现次数越多的网页排在越前面。这个判据不能说毫无道接的其它网页的排序,而想要知道那些网页的排序,却又首 理,因为用户搜索一个词语,通常表明对该词语感兴趣。既先得知道W的排序。 然如此,那该词语在网页中的出现次数越多,就越有可能表 为了打破这个循环,佩奇和布林采用了一个很巧妙的 示该网页是用户所需要的。可惜的是,这个貌似合理的方法思路,即分析一个虚拟用户在互联网上的漫游过程。他们假 实际上却行不大通。因为按照这种方法,任何一个像祥林嫂定:虚拟用户一旦访问了一个网页后,下一步将有相同的几 样翻来复去倒腾某些关键词的网页,无论水平多烂,一旦率访问被该网页所链接的任何一个其它网页。换句话说,如 被搜索到,都立刻会“金榜题名”,这简直就是广告及垃圾网果网页W1有N个对外链接,则虚拟用户在访问了W之后, 页制造者的天堂。事实上,当时几乎没有一个搜索引擎不被下一步点击这些链接中任何一个的几率均为1N。初看起来 祥林嫂”们所困扰,其中最具讽刺意味的是:堪称互联网这一假设并不合理,因为任何用户都有偏好,怎么可能以相 巨子的当年四大搜索引擎在搜索自己公司的名字时,居然只同的几率访问一个网页的所有链接呢?但如果我们考虑到 有一个能使之出现在搜索结果的前十名内,其余全被“祥林佩奇和布林的虚拟用户实际上是对互联网上全体用户的 嫂”们挤跑了。 种平均意义上的代表,这条假设就不象初看起来那么不合理 就是在这种情况下,1996年初,谷歌公司的创始人,了。那么网页的排序由什么来决定呢?是由该用户在漫游了 当时还是美国斯坦福大学( Stanford University)研究生的佩很长时间(理论上为无穷长时间)后访问各网页的几率分布 奇( Larry Page)和布林( Sergey brin)开始了对网页排序问题来决定,访问几率越大的网页排序就越靠前 的研究。这两位小伙子之所以研究网页排序问题,一来是导 为了将这一分析数学化,我们用pn)表示虚拟用户在 师的建议(佩奇后来称该建议为“我有生以来得到过的最好进行第n次浏览时访问网页W1的几率。显然,上述假设可 建议”),二来则是因为他们对这一问题背后的数学产生了以表述为(请读者自行证明) 兴趣。 pn+1)=2jpn)p→NN 网页排序问题的背后有什么样的数学呢?这得从佩奇 和布林看待这一问题的思路说起。在佩奇和布林看来,网页这里B-是一个描述互联网链接结构的指标函数( indicator 的排序是不能靠每个网页自己来标榜的,无论把关键词重复 function),其定义是:如果网页W;有链接指向网页W,则 多少次,垃圾网页依然是垃圾网页。那么,究竟什么才是网P-;取值为1,反之则为0。显然,这条假设所体现的正是 页排序的可靠依据呢?出生于书香门第的佩奇和布林(两人前面提到的佩奇和布林的排序原则,因为右端求和式的存在 的父亲都是大学教授)想到了学术界评判学术论文重要性的表明与W有链接的所有网页W都对W的排名有贡献,而 通用方法,那就是看论文的引用次数。在互联网上,与论文求和式中的每一项都正比于p,则表明来自那些网页的贡献 引用相类似的是显然是网页链接。因此,佩奇和布林萌生了与它们的自身排序有关,自身排序越靠前(即p越大),贡 一个网页排序的思路,那就是通过研究网页间的相互链接来献就越大。 数学文化/第2卷第1期
World of Mathematics 数学烟云 数学文化/第2卷第1期 13 某贪官的台词来说，“能用钱解决的问题就不是大问题”。 但对第三条的破坏却要了命了，因为无论搜索引擎的硬件如 何强大，速度如何快捷，要是搜索结果有几百万条，那么任 何用户想从其中“海选”出自己真正想要的东西都是几乎不 可能的。这一点对早期搜索引擎来说可谓是致命伤，而且它 不是用钱就能解决的问题。 这致命伤该如何治疗呢？药方其实很简单，那就是对 搜索结果进行排序，把用户最有可能需要的网页排在最前 面，以确保用户能很方便地找到它们。但问题是 ：网页的水 平千差万别，用户的喜好更是万别千差，互联网上有一句 流行语叫做 ：“在互联网上，没人知道你是一条狗”(On the Internet, nobody knows you're a dog)。连用户是人是狗都“没 人知道”，搜索引擎又怎能知道哪些搜索结果是用户最有可 能需要的，并对它们进行排序呢？ 在谷歌主导互联网搜索之前，多数搜索引擎采用的排 序方法，是以被搜索词语在网页中的出现次数来决定排序， 出现次数越多的网页排在越前面。这个判据不能说毫无道 理，因为用户搜索一个词语，通常表明对该词语感兴趣。既 然如此，那该词语在网页中的出现次数越多，就越有可能表 示该网页是用户所需要的。可惜的是，这个貌似合理的方法 实际上却行不大通。因为按照这种方法，任何一个像祥林嫂 一样翻来复去倒腾某些关键词的网页，无论水平多烂，一旦 被搜索到，都立刻会“金榜题名”，这简直就是广告及垃圾网 页制造者的天堂。事实上，当时几乎没有一个搜索引擎不被 “祥林嫂”们所困扰，其中最具讽刺意味的是 ：堪称互联网 巨子的当年四大搜索引擎在搜索自己公司的名字时，居然只 有一个能使之出现在搜索结果的前十名内，其余全被“祥林 嫂”们挤跑了。 就是在这种情况下，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 越大），贡 献就越大
World of Mathematics数学烟云 6 1313 41116 133 30 88 6416 43|2 随机矩阵在谷歌算法里占据了重要的地位 为符号简洁起见,我们将虚拟用户第n次浏览时访问各即所谓的“悬挂网页”( dangling page)注 网页的几率合并为一个列向量p,它的第i个分量为p(n) 上述公式的求解是简单得不能再简单的事情,即 并引进一个只与互联网结构有关的矩阵H,它的第i行j列 的矩阵元为H=P2-N,则上述公式可以改写为 Poti= hpn 其中po为虚拟读者初次浏览时访问各网页的几率分布(在 佩奇和布林的原始论文中,这一几率分布被假定为是均匀分 这就是计算网页排序的公式。 布)。 熟悉随机过程理论的读者想必看出来了,上述公式描 如前所述,佩奇和布林是用虚拟用户在经过很长(理 述的是一种马尔可夫过程( Markov process,而且是其中最论上为无穷长)时间的漫游后访问各网页的几率分布,即 简单的一类,即所谓的平稳马尔可夫过程( stationary Markov lim→=Pa’来确定网页排序的。这个定义要想管用,显然要 process)-,而H则是描述转移概率的所谓转移矩阵解决三个问题 ( transition matrⅸx)。不过普通马尔可夫过程中的转移矩阵通 常是随机矩阵( (stochastic matrix),即每一列的矩阵元之和都 极限lima→=pa是否存在? 为1的矩阵(请读者想一想,这一特点的“物理意义”是什 2.如果极限存在,它是否与po的选取无关? 么?)注二。而我们的矩阵H却可能有一些列是零向量 3.如果极限存在,并且与po的选取无关,它作为网页 从而矩阵元之和为0,它们对应于那些没有对外链接的网页, 排序的依据是否真的合理? 数学文化/第2卷第1期14
World of Mathematics 数学烟云 数学文化/第2卷第1期 14 为符号简洁起见，我们将虚拟用户第 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) [ 注三 ] 。 上述公式的求解是简单得不能再简单的事情，即 ： pn = Hnp0 其中 p0 为虚拟读者初次浏览时访问各网页的几率分布（在 佩奇和布林的原始论文中，这一几率分布被假定为是均匀分 布）。 如前所述，佩奇和布林是用虚拟用户在经过很长（理 论上为无穷长）时间的漫游后访问各网页的几率分布，即 limn →∞ pn，来确定网页排序的。这个定义要想管用，显然要 解决三个问题 ： 1. 极限 limn →∞ pn 是否存在？ 2. 如果极限存在，它是否与 p0 的选取无关？ 3. 如果极限存在，并且与 p0 的选取无关，它作为网页 排序的依据是否真的合理？ 随机矩阵在谷歌算法里占据了重要的地位
World of Mathematics数学烟云 +5 0.10 0.70 S 1 a 1.0 0.20 0.5 0.95 a a 0.5 04 0.05 a 06人a0 040 a 0.30 2 马尔可夫过程( Markov process在谷歌算法里占据了重要的地位。我们称离散的马尔可夫过程为马尔可夫链;其在各个时刻的状态转变由 个概率矩阵所控制。这是一个马尔可夫过程的例子 如果这三个问题的答案都是肯定的,那么网页排序问题样的网页,就会由于没有对外链接而永远停留在那里),这 就算解决了。反之,哪怕只有一个问题的答案是否定的,网显然是不合理的。这种不合理效应是如此显著,以至于在 页排序问题也就不能算是得到满意的解决。那么实际答案如个连通性良好的互联网上,哪怕只有一个“悬挂网页”,也足 何呢?很遗憾,是后一种,而且是其中最糟糕的情形,即 以使整个互联网的网页排序失效,可谓是“一粒老鼠屎坏了 个问题的答案全都是否定的。这可以由一些简单的例子看一锅粥”。 出。比方说,在只包含两个相互链接网页的迷你型互联网上, 为了解决这些问题,佩奇和布林对虚拟用户的行为进行 如果p=(1,0)2,极限就不存在(因为几率分布将在(1,0)了修正。首先,他们意识到无论真实用户还是虚拟用户,当 和(0,1)2之间无穷振荡)。而存在几个互不连通(即互不链他们访问到“悬挂网页”时,都不可能也不应该“在一棵树 接)区域的互联网则会使极限——即便存在一与p的选取上吊死”,而是会自行访问其它网页。对于真实用户来说,自 有关(因为把p选在不同区域内显然会导致不同极限)。至行访问的网页显然与各人的兴趣有关,但对于在平均意义上 于极限存在,并且与p的选取无关时它作为网页排序的依代表真实用户的虚拟用户来说,佩奇和布林假定它将会在整 据是否真的合理的问题,虽然不是数学问题,答案却也是否个互联网上随机选取一个网页进行访问。用数学语言来说 定的,因为任何一个“悬挂网页”都能象黑洞一样,把其它这相当于是把H的列向量中所有的零向量都换成e/N(其中 网页的几率“吸收”到自己身上(因为虚拟用户一旦进入那e是所有分量都为1的列向量,N为互联网上的网页总数)。 数学文化/第2卷第1期15
World of Mathematics 数学烟云 数学文化/第2卷第1期 15 如果这三个问题的答案都是肯定的，那么网页排序问题 就算解决了。反之，哪怕只有一个问题的答案是否定的，网 页排序问题也就不能算是得到满意的解决。那么实际答案如 何呢？很遗憾，是后一种，而且是其中最糟糕的情形，即三 个问题的答案全都是否定的。这可以由一些简单的例子看 出。比方说，在只包含两个相互链接网页的迷你型互联网上， 如果 p0 = (1, 0) T ，极限就不存在 ( 因为几率分布将在 (1, 0) T 和 (0, 1) T 之间无穷振荡 )。而存在几个互不连通（即互不链 接）区域的互联网则会使极限——即便存在——与 p0的选取 有关（因为把 p0 选在不同区域内显然会导致不同极限）。至 于极限存在，并且与 p0 的选取无关时它作为网页排序的依 据是否真的合理的问题，虽然不是数学问题，答案却也是否 定的，因为任何一个“悬挂网页”都能象黑洞一样，把其它 网页的几率“吸收”到自己身上（因为虚拟用户一旦进入那 样的网页，就会由于没有对外链接而永远停留在那里），这 显然是不合理的。这种不合理效应是如此显著，以至于在一 个连通性良好的互联网上，哪怕只有一个“悬挂网页”，也足 以使整个互联网的网页排序失效，可谓是“一粒老鼠屎坏了 一锅粥”。 为了解决这些问题，佩奇和布林对虚拟用户的行为进行 了修正。首先，他们意识到无论真实用户还是虚拟用户，当 他们访问到“悬挂网页”时，都不可能也不应该“在一棵树 上吊死”，而是会自行访问其它网页。对于真实用户来说，自 行访问的网页显然与各人的兴趣有关，但对于在平均意义上 代表真实用户的虚拟用户来说，佩奇和布林假定它将会在整 个互联网上随机选取一个网页进行访问。用数学语言来说， 这相当于是把 H 的列向量中所有的零向量都换成 e/N（其中 e 是所有分量都为 1 的列向量，N 为互联网上的网页总数）。 马尔可夫过程 (Markov process) 在谷歌算法里占据了重要的地位。我们称离散的马尔可夫过程为马尔可夫链；其在各个时刻的状态转变由 一个概率矩阵所控制。这是一个马尔可夫过程的例子。 S S S 0 0 0 0 1 1 1 1 2 a a a a a a 0.5 0.5 0.6 1.0 0.4 0.20 0.70 0.10 +5 -1 0.95 0.05 0.40 0.30 0.30
World of Mathematics数学烟云 百度一下 百度的创始人李彦宏 如果我们引进一个描述“悬挂网页”的指标向量( indicator aS+(1-a )ee/N vector)a,它的第i个分量的取值视W1是否为“悬挂网页” 而定,如果是“悬挂网页”,取值为1,否则为零,并用S表 这个矩阵不仅是一个随机矩阵,而且由于第二项的加 示修正后的矩阵,则: 盟,它有了一个新的特点,即所有矩阵元都为正(请读者想 s=H+aeN 一想,这一特点的“物理意义”是什么?),这样的矩阵是所 谓的素矩阵( primitive matrix)四。这一修正因此被称为素 显然,这样定义的S矩阵的每一列的矩阵元之和都性修正( primitivity adjustment) 是1,从而是一个不折不扣的随机矩阵。这一修正因此被经过这两类修正,网页排序的计算方法就变成了 称为随机性修正( stochasticity adjustment)。这一修正相 当于剔除了“悬挂网页”,从而可以给上述第三个问题带 pu=Gp 来肯定回答(当然,这一回答没有绝对标准,可以不断改 这个算法能给上述问题提供肯定答案吗?是的,它能。 进)。不过,这一修正解决不了前两个问题。因此,佩奇因为随机过程理论中有一个所谓的马尔可夫链基本定理 和布林引进了第二个修正。他们假定,虚拟用户虽然是虚( Fundamental theorem of markov chains),它表明在一个马尔 拟的,但多少也有一些“性格”,不会完全死板地只访问当可夫过程中,如果转移矩阵是素矩阵,那么上述前两个问题 前网页所提供的链接。具体地说,他们假定虚拟用户在每的答案就是肯定的。而随机性修正已经解决了上述第三个问 步都有一个小于1的几率a访问当前网页所提供的链题,因此所有问题就都解决了。如果我们用p表示pn的极 接,同时却也有一个几率1-a不受那些链接所限,随机限注五,则p给出的就是整个互联网的网页排序——它的 访问互联网上的任何一个网站。用数学语言来说(请读者每一个分量就是相应网页的访问几率,几率越大,排序就越 自行证明),这相当于是把上述S矩阵变成了一个新的矩靠前。 阵G 这样,佩奇和布林就找到了一个不仅含义合理,而且数 数学文化/第2卷第1期16
World of Mathematics 数学烟云 数学文化/第2卷第1期 16 G = αS + (1-α)eeT/N 这个矩阵不仅是一个随机矩阵，而且由于第二项的加 盟，它有了一个新的特点，即所有矩阵元都为正（请读者想 一想，这一特点的“物理意义”是什么？），这样的矩阵是所 谓的素矩阵 (primitive matrix) [ 注四 ] 。这一修正因此被称为素 性修正 (primitivity adjustment)。 经过这两类修正，网页排序的计算方法就变成了 ： pn = Gn p0 这个算法能给上述问题提供肯定答案吗？是的，它能。 因为随机过程理论中有一个所谓的马尔可夫链基本定理 (Fundamental Theorem of Markov Chains)，它表明在一个马尔 可夫过程中，如果转移矩阵是素矩阵，那么上述前两个问题 的答案就是肯定的。而随机性修正已经解决了上述第三个问 题，因此所有问题就都解决了。如果我们用 p 表示 pn 的极 限 [ 注五 ] ，则 p 给出的就是整个互联网的网页排序——它的 每一个分量就是相应网页的访问几率，几率越大，排序就越 靠前。 这样，佩奇和布林就找到了一个不仅含义合理，而且数 如果我们引进一个描述“悬挂网页”的指标向量 (indicator vector) a，它的第 i 个分量的取值视 Wi 是否为“悬挂网页” 而定，如果是“悬挂网页”，取值为 1，否则为零，并用 S 表 示修正后的矩阵，则 ： S = H + ae T /N 显然，这样定义的 S 矩阵的每一列的矩阵元之和都 是 1，从而是一个不折不扣的随机矩阵。这一修正因此被 称为随机性修正 (stochasticity adjustment)。这一修正相 当于剔除了“悬挂网页”，从而可以给上述第三个问题带 来肯定回答（当然，这一回答没有绝对标准，可以不断改 进）。不过，这一修正解决不了前两个问题。因此，佩奇 和布林引进了第二个修正。他们假定，虚拟用户虽然是虚 拟的，但多少也有一些“性格”，不会完全死板地只访问当 前网页所提供的链接。具体地说，他们假定虚拟用户在每 一步都有一个小于 1 的几率 α 访问当前网页所提供的链 接，同时却也有一个几率 1-α 不受那些链接所限，随机 访问互联网上的任何一个网站。用数学语言来说（请读者 自行证明），这相当于是把上述 S 矩阵变成了一个新的矩 阵 G ： 百度的创始人李彦宏
World of Mathematics数学烟云 学上严谨的网页排序算法,他们把这个算法称为 Page rank是一百万美元。与谷歌在短短几年之后的惊人身价相比,那 不过要注意的是,虽然这个名称的直译恰好是“网页排序”,简直就是“跳楼大甩卖”。可惜当时却无人识货。佩奇和布 但它实际上指的是“佩奇排序”,因为其中的“Page”不是指林在硅谷“叫卖”了一圈,连一个买家都没找到。被他们找 网页,而是佩奇的名字。这个算法就是谷歌排序的数学基础,过的公司包括了当时搜索业巨头之一的 Excite(该公司后来 而其中的矩阵G则被称为谷歌矩阵( Google matrix) 想必连肠子都悔青了)。为了不让自己的心血荒废,佩奇和 细心的读者可能注意到了 布林只得将公司继续办了下去 我们还遗漏了一样东西,那就是谷 直办到今天,这就是谷歌的“发家 歌矩阵中描述虚拟用户“性格”的 那个a参数。那个参数的数值是 谷歌成立之初跟其它一些 多少呢?从理论上讲,它应该来自 “发迹于地下室”(one-man-in- 于对真实用户平均行为的分析,不 basement)的∏T公司一样寒酸:雇 过实际上另有一个因素对它的选 员只有一位(两位老板不算),工 取产生了很大影响,那就是G"p0 作场所则是一位朋友的车库。但 收敛于p的快慢程度。由于G是 它出类拔萃的排序算法很快为它 个N×N矩阵,而N为互联网 赢得了声誉。公司成立仅仅三个 上—确切地说是被谷歌所收录 月,《 PC Magzine》杂志就把谷歌 的—网页的总数,在谷歌成立之 谷歌公司创始人佩奇(左)和布林(右) 列为了年度最佳搜索引擎。2001 初为几千万,目前为几百亿,是一 年,佩奇为“佩奇排序”申请到了 极其巨大的数字。因此G是一个超大型矩阵,甚至很可能专利,专利的发明人为佩奇,拥有者则是他和布林的母校斯 是人类有史以来处理过的最庞大的矩阵。对于这样的矩阵,坦福大学。2004年8月,谷歌成为了一家初始市值约17亿 G"po收敛速度的快慢是关系到算法是否实用的重要因素,而美元的上市公司。不仅公司高管在一夜间成为了亿万富翁, 这个因素恰恰与a有关。可以证明,a越小,GPp的收敛就连当初给过他们几十美元“赞助费”的某些同事和朋友也 速度就越快。但a也不能太小,因为太小的话,“佩奇排序”得到了足够终身养老所用的股票回报。作为公司摇篮的斯坦 中最精华的部分,即以网页间的彼此链接为基础的排序思路福大学则因拥有“佩奇排序”的专利而获得了180万股谷歌 就被弱化了(因为这部分的贡献正比于α),这显然是得不股票。2005年12月,斯坦福大学通过卖掉那些股票获得了 偿失的。因此,在α的选取上有很多折衷的考虑要做,佩奇3.36亿美元的巨额收益,成为美国高校因支持技术研发而获 和布林最终选择的数值是a=0.85。 得的有史以来最巨额的收益之一{注七l 以上就是谷歌背后最重要的数学奥秘。与以往那种凭 谷歌在短短数年间就横扫整个互联网,成为搜索引擎业 借关键词出现次数所作的排序不同,这种由所有网页的相互的新一代霸主,佩奇和布林的那个排序算法无疑居功至伟 链接所确定的排序是不那么容易做假的,因为做假者再是把可以说,是数学成就了谷歌补注。当然,这么多年过去了 自己的网页吹得天花乱坠,如果没有真正吸引人的内容,别谷歌作为IT界研发能力最强的公司之一,它的网页排序方 人不链接它,一切就还是枉然注六。而且“佩奇排序”还有法早已有了巨大的改进,由当年单纯依靠“佩奇排序”演变 个重要特点,那就是它只与互联网的结构有关,而与用户为了由两百多种来自不同渠道的信息(其中包括与网页访问 具体搜索的东西无关。这意味着排序计算可以单独进行,而量有关的统计数据)综合而成的更加可靠的方法。而当年曾 无需在用户键入搜索指令后才临时进行。谷歌搜索的速度之给佩奇和布林带来过启示的学术界,则反过来从谷歌的成功 所以快捷,在很大程度上得益于此 中借鉴了经验,如今一些学术机构对论文影响因子( Impact 在本文的最后,我们顺便介绍一点谷歌公司的历史。佩 factor)的计算已采用了类似“佩奇排序”的算法 奇和布林对谷歌算法的研究由于需要收集和分析大量网页 在本文的最后,还有一件事情在这里提一下,那就是与 间的相互链接,从而离不开硬件支持。为此,旱在研究阶段,佩奇和布林研究排序算法几乎同时,有另外几人也相互独立 他们就四处奔走,为自己的研究筹集资金和硬件。1998年9地沿着类似的思路从事着研究[注八。他们中有一位是当时 月,他们为自己的试验系统注册了公司—即如今大名鼎鼎在美国新泽西州工作的中国人,他的算法后来也成就了一家 的谷歌公司。但这些行为虽然近乎于创业,他们两人当时却公司—家中国公司。此人的名字叫做李彦宏( Robin li), 并无长期从商的兴趣。1999年,当他们觉得打理公司干扰他所成就的那家公司就是百度。这些新公司的发展极好地印 了自己的研究时,甚至萌生了卖掉公司的想法。他们的开价证了培根( Francis bacon)的一句名言:知识就是力量 数学文化/第2卷第1期
World of Mathematics 数学烟云 数学文化/第2卷第1期 17 是一百万美元。与谷歌在短短几年之后的惊人身价相比，那 简直就是“跳楼大甩卖”。可惜当时却无人识货。佩奇和布 林在硅谷“叫卖”了一圈，连一个买家都没找到。被他们找 过的公司包括了当时搜索业巨头之一的 Excite（该公司后来 想必连肠子都悔青了）。为了不让自己的心血荒废，佩奇和 布林只得将公司继续办了下去，一 直办到今天，这就是谷歌的“发家 史”。 谷歌成立之初跟其它一些 “ 发 迹 于 地 下 室 ”(one-man-inbasement) 的 IT 公司一样寒酸 ：雇 员只有一位（两位老板不算），工 作场所则是一位朋友的车库。但 它出类拔萃的排序算法很快为它 赢得了声誉。公司成立仅仅三个 月，《PC Magzine》杂志就把谷歌 列为了年度最佳搜索引擎。2001 年，佩奇为“佩奇排序”申请到了 专利，专利的发明人为佩奇，拥有者则是他和布林的母校斯 坦福大学。2004 年 8 月，谷歌成为了一家初始市值约 17 亿 美元的上市公司。不仅公司高管在一夜间成为了亿万富翁， 就连当初给过他们几十美元“赞助费”的某些同事和朋友也 得到了足够终身养老所用的股票回报。作为公司摇篮的斯坦 福大学则因拥有“佩奇排序”的专利而获得了 180 万股谷歌 股票。2005 年 12 月，斯坦福大学通过卖掉那些股票获得了 3.36 亿美元的巨额收益，成为美国高校因支持技术研发而获 得的有史以来最巨额的收益之一 [ 注七 ] 。 谷歌在短短数年间就横扫整个互联网，成为搜索引擎业 的新一代霸主，佩奇和布林的那个排序算法无疑居功至伟， 可以说，是数学成就了谷歌 [ 补注 ] 。当然，这么多年过去了， 谷歌作为 IT 界研发能力最强的公司之一，它的网页排序方 法早已有了巨大的改进，由当年单纯依靠“佩奇排序”演变 为了由两百多种来自不同渠道的信息（其中包括与网页访问 量有关的统计数据）综合而成的更加可靠的方法。而当年曾 给佩奇和布林带来过启示的学术界，则反过来从谷歌的成功 中借鉴了经验，如今一些学术机构对论文影响因子 (impact factor) 的计算已采用了类似“佩奇排序”的算法。 在本文的最后，还有一件事情在这里提一下，那就是与 佩奇和布林研究排序算法几乎同时，有另外几人也相互独立 地沿着类似的思路从事着研究 [ 注八 ] 。他们中有一位是当时 在美国新泽西州工作的中国人，他的算法后来也成就了一家 公司——一家中国公司。此人的名字叫做李彦宏 (Robin Li)， 他所成就的那家公司就是百度。这些新公司的发展极好地印 证了培根 (Francis Bacon) 的一句名言 ：知识就是力量。 学上严谨的网页排序算法，他们把这个算法称为 PageRank 不过要注意的是，虽然这个名称的直译恰好是“网页排序”， 但它实际上指的是“佩奇排序”，因为其中的“Page”不是指 网页，而是佩奇的名字。这个算法就是谷歌排序的数学基础， 而其中的矩阵 G 则被称为谷歌矩阵 (Google matrix)。 细心的读者可能注意到了， 我们还遗漏了一样东西，那就是谷 歌矩阵中描述虚拟用户“性格”的 那个 α 参数。那个参数的数值是 多少呢？从理论上讲，它应该来自 于对真实用户平均行为的分析，不 过实际上另有一个因素对它的选 取产生了很大影响，那就是 Gn p0 收敛于 p 的快慢程度。由于 G 是 一个 N×N 矩阵，而 N 为互联网 上——确切地说是被谷歌所收录 的——网页的总数，在谷歌成立之 初为几千万，目前为几百亿，是一 个极其巨大的数字。因此 G 是一个超大型矩阵，甚至很可能 是人类有史以来处理过的最庞大的矩阵。对于这样的矩阵， Gn p0 收敛速度的快慢是关系到算法是否实用的重要因素，而 这个因素恰恰与 α 有关。可以证明，α 越小，Gn p0 的收敛 速度就越快。但 α 也不能太小，因为太小的话，“佩奇排序” 中最精华的部分，即以网页间的彼此链接为基础的排序思路 就被弱化了（因为这部分的贡献正比于 α），这显然是得不 偿失的。因此，在 α 的选取上有很多折衷的考虑要做，佩奇 和布林最终选择的数值是 α = 0.85。 以上就是谷歌背后最重要的数学奥秘。与以往那种凭 借关键词出现次数所作的排序不同，这种由所有网页的相互 链接所确定的排序是不那么容易做假的，因为做假者再是把 自己的网页吹得天花乱坠，如果没有真正吸引人的内容，别 人不链接它，一切就还是枉然 [ 注六 ] 。而且“佩奇排序”还有 一个重要特点，那就是它只与互联网的结构有关，而与用户 具体搜索的东西无关。这意味着排序计算可以单独进行，而 无需在用户键入搜索指令后才临时进行。谷歌搜索的速度之 所以快捷，在很大程度上得益于此。 在本文的最后，我们顺便介绍一点谷歌公司的历史。佩 奇和布林对谷歌算法的研究由于需要收集和分析大量网页 间的相互链接，从而离不开硬件支持。为此，早在研究阶段， 他们就四处奔走，为自己的研究筹集资金和硬件。1998 年 9 月，他们为自己的试验系统注册了公司——即如今大名鼎鼎 的谷歌公司。但这些行为虽然近乎于创业，他们两人当时却 并无长期从商的兴趣。1999 年，当他们觉得打理公司干扰 了自己的研究时，甚至萌生了卖掉公司的想法。他们的开价 谷歌公司创始人佩奇 ( 左 ) 和布林 ( 右 )
World of Mathematics数学烟云 注释 匚参考文献 1.马尔可夫过程,也称为马尔可夫链( Markov chain),是 1. D. Austin, How Google Finds Your Needle in the 类离散随机过程,它的最大特点是每一步的概率分 Web's Haystack 布都只与前一步有关。而平稳马尔可夫过程则是指转 移概率与步数无关的马尔可夫过程(体现在我们的例 2. J. Battelle, The Birth of Google, Wired(August 子中,即H与n无关)。另外要说明的是,本文在表 述上不同于佩奇和布林的原始论文,后者并未使用诸 3.S. Brin and L Page, The Anatomy of a Large-Scale 如“马尔可夫过程”或“马尔可夫链”那样的术语,也 Hypertextual Web Search Engine, Seventh International 并未直接运用这一领域内的定理 World-Wide Web Conference, April 14-18, 1998 2.在更细致的分类中,这种每一列的矩阵元之和都为1 的随机矩阵称为左随机矩阵( (eft stochastic matrix),以 Brisbane Australia 区别于每一行的矩阵元之和都等于1的所谓右随机矩 4. 0. Ibe, Markov Processes for Stochastic Modeling, 阵( right stochastic matrix)。这两者在应用上基本是等 (Elsevier Academic Press, 2009) 价的,区别往往只在于约定。 3.这种几乎满足随机矩阵条件,但有些列(或行)的矩 5.A. N. Langville and C D. Meyer, Google's PageRank 阵元之和小于1的矩阵也有一个名称,叫做亚随机矩 and Beyond: The Science of Search Engine Rankings, F (substochastic matrix) 4.确切地说,这种所有矩阵元都为正的矩阵不仅是素矩 6. C. Rousseau and Y Saint-Aubin, Mathematics and 阵,而且还是所谓的正矩阵( positive matrIx)。这两者 Technology, (Springer, 2008) 的区别是:正矩阵要求所有矩阵元都为正,而素矩阵 只要求某个正整数次幂为正矩阵。 5.读者们想必看出来了,p其实是矩阵G的本征值为1 的本征向量,而利用虚拟用户确定网页排序的思路其 实是在用迭代法解决上述本征值问题。在数学上可以 证明,上述本征向量是唯一的,而且G的其它本征值 补注 λ全都满足<1(更准确地说,是≤x—这也正是 G"p0的收敛速度与有关的原因)。 6.当然,这绝不意味着在网页排序上已不可能再做假。 有些读者对“是数学成就了谷歌”这一说法不以 相反,这种做假在互联网上依然比比皆是,比如许多 为然,认为是佩奇和布林的商业才能,或将数学与商 广告或垃圾网页制造者用自动程序到各大论坛发贴 业结合起来的才能成就了谷歌。这是一个见仁见智 建立对自己网页的链接,以提高排序,就是一种常见 的问题,看法不同不足为奇。我之所以认为是数学 的做假手法。为了遏制做假,谷歌采取了很多技术手 成就了谷歌,是因为谷歌当年胜过其它搜索引擎的 段,并对有些做假网站采取了严厉的惩罚措施。这种 地方只有算法。除算法外,佩奇和布林当年并无其它 惩罚(有时是误罚)对于某些靠互联网吃饭的公司有 胜过竞争对手的手段,包括商业手段。如果让他们去 毁灭性的打击力。 当其它几家搜索引擎公司的老总,用那几家公司的算 7.从投资角度讲,斯坦福大学显然是过早卖掉了股票 法,他们是不可能脱穎而出的;而反过来,如果让其 否则获利将更为丰厚。不过,这正是美国名校的一个 它几家搜索引擎公司的老总来管理谷歌,用谷歌的算 可贵之处,它们虽擅长从支持技术研发中获利,却并 不唯利是图。它们有自己的原则,那就是不能让商业 法,我相信谷歌依然能超越对手。因此,虽然谷歌后 利益干扰学术研究。为此,它们通常不愿长时间持有 来确实用过不少出色的商业手段(任何一家那样巨型 特定公司的股票,以免在无形中干扰与该公司存在竞 的公司都必然有商业手段上的成功之处),而当年那 争关系的学术研究的开展 个算法在今天的谷歌—一如正文所述—则早已被 8.那些研究与“佩奇排序”的类似仅仅在于大方向(即 更复杂的算法所取代,但我认为谷歌制胜的根基和根 都利用互联网的链接结构来决定网页排序),而非具 源在于那个算法,而非商业手段,因此我说“是数学 体算法类似。 成就了谷歌”。 数学文化/第2卷第1期18
World of Mathematics 数学烟云 数学文化/第2卷第1期 18 参考文献 1. D. Austin, How Google Finds Your Needle in the Web's Haystack. 2. J. Battelle, The Birth of Google, Wired (August 2005). 3. S. Brin and L. Page, The Anatomy of a Large-Scale Hypertextual Web Search Engine, Seventh International World-Wide Web Conference, April 14-18, 1998, Brisbane, Australia. 4. O. Ibe, Markov Processes for Stochastic Modeling, (Elsevier Academic Press, 2009). 5. A. N. Langville and C. D. Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings, (Princeton University Press, 2006). 6. C. Rousseau and Y. Saint-Aubin, Mathematics and Technology, (Springer, 2008). 补注 有些读者对“是数学成就了谷歌”这一说法不以 为然，认为是佩奇和布林的商业才能，或将数学与商 业结合起来的才能成就了谷歌。这是一个见仁见智 的问题，看法不同不足为奇。我之所以认为是数学 成就了谷歌，是因为谷歌当年胜过其它搜索引擎的 地方只有算法。除算法外，佩奇和布林当年并无其它 胜过竞争对手的手段，包括商业手段。如果让他们去 当其它几家搜索引擎公司的老总，用那几家公司的算 法，他们是不可能脱颖而出的 ；而反过来，如果让其 它几家搜索引擎公司的老总来管理谷歌，用谷歌的算 法，我相信谷歌依然能超越对手。因此，虽然谷歌后 来确实用过不少出色的商业手段（任何一家那样巨型 的公司都必然有商业手段上的成功之处），而当年那 个算法在今天的谷歌——如正文所述——则早已被 更复杂的算法所取代，但我认为谷歌制胜的根基和根 源在于那个算法，而非商业手段，因此我说“是数学 成就了谷歌”。 注释 1. 马尔可夫过程，也称为马尔可夫链 (Markov chain)，是 一类离散随机过程，它的最大特点是每一步的概率分 布都只与前一步有关。而平稳马尔可夫过程则是指转 移概率与步数无关的马尔可夫过程 ( 体现在我们的例 子中，即 H 与 n 无关 )。另外要说明的是，本文在表 述上不同于佩奇和布林的原始论文，后者并未使用诸 如“马尔可夫过程”或“马尔可夫链”那样的术语，也 并未直接运用这一领域内的定理。 2. 在更细致的分类中，这种每一列的矩阵元之和都为 1 的随机矩阵称为左随机矩阵 (left stochastic matrix)，以 区别于每一行的矩阵元之和都等于 1 的所谓右随机矩 阵 (right stochastic matrix)。这两者在应用上基本是等 价的，区别往往只在于约定。 3. 这种几乎满足随机矩阵条件，但有些列（或行）的矩 阵元之和小于 1 的矩阵也有一个名称，叫做亚随机矩 阵 (substochastic matrix)。 4. 确切地说，这种所有矩阵元都为正的矩阵不仅是素矩 阵，而且还是所谓的正矩阵 (positive matrix)。这两者 的区别是 ：正矩阵要求所有矩阵元都为正，而素矩阵 只要求某个正整数次幂为正矩阵。 5. 读者们想必看出来了，p 其实是矩阵 G 的本征值为 1 的本征向量，而利用虚拟用户确定网页排序的思路其 实是在用迭代法解决上述本征值问题。在数学上可以 证明，上述本征向量是唯一的，而且 G 的其它本征值 λ 全都满足 |λ|<1（更准确地说，是 |λ| ≤ α ——这也正是 Gn p0的收敛速度与 α 有关的原因）。 6. 当然，这绝不意味着在网页排序上已不可能再做假。 相反，这种做假在互联网上依然比比皆是，比如许多 广告或垃圾网页制造者用自动程序到各大论坛发贴， 建立对自己网页的链接，以提高排序，就是一种常见 的做假手法。为了遏制做假，谷歌采取了很多技术手 段，并对有些做假网站采取了严厉的惩罚措施。这种 惩罚（有时是误罚）对于某些靠互联网吃饭的公司有 毁灭性的打击力。 7. 从投资角度讲，斯坦福大学显然是过早卖掉了股票， 否则获利将更为丰厚。不过，这正是美国名校的一个 可贵之处，它们虽擅长从支持技术研发中获利，却并 不唯利是图。它们有自己的原则，那就是不能让商业 利益干扰学术研究。为此，它们通常不愿长时间持有 特定公司的股票，以免在无形中干扰与该公司存在竞 争关系的学术研究的开展。 8. 那些研究与“佩奇排序”的类似仅仅在于大方向（即 都利用互联网的链接结构来决定网页排序），而非具 体算法类似