1.前言

最近，搜索引擎 Google (http://www.google.com/)非常引人注目。Google 是基于现担任 CEO 的 Larry Page 和担任总经理的 Sergey Brin (2001年2月)在就读于美斯坦福大学研究生院时所开发的搜索引擎的一种检索服务。Google 从1998年9月开始服务,但 Netscape Communications 在 Google 的测试阶段就开始与其合作，美国 Yahoo! 公司也从2000年6月起将默认搜索引擎(美国 Yahoo! 不能检索时作为增补的搜索引擎)由原先合作的 Inktomi 转换为了 Google。日语版 Google 在2000年9月正式登场,现已被 BIGLOBE(NEC)所采用。 (注:2001年4月 Yahoo! JAPAN 和 @NIFTY，7月索尼，2002年1月 Excite 也相继与 Google 建立了协作关系)。

Google 被评价的优点不仅仅在于去除无用的(广告)标语构成单一页面的功能、独自的 Cache 系统、动态制成摘要信息、为实现高速检索而设置的分散系统(数千台规模的Linux群集器)等，而其中最大的优点正是它检索结果的正确性。一种能够自动判断网页重要性的技术「PageRank是(网页等级)」就是为此而设计的一种技术。 本文的目的就是以尽可能浅显易懂的语言来说明 PageRank 系统的概要和原理。

以下是 PageRank 的一篇基础文章。

Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998,
http://www-db.stanford.edu/~backrub/pageranksub.ps

为了更高效地计算 PageRank,以下是改良以后的一篇论文。

Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999,
http://dbpubs.stanford.edu:8090/pub/1999-31

另外，以下是 PageRank 的演示用资料(PowerPoint)。

Larry Page, 'PageRank: Bringing Order to the Web',
http://hci.stanford.edu/~page/papers/pagerank/ （已失效）

接下来就对这两篇文章(另加一篇资料)进行基本说明。 首先，用简单的例子来解说 PageRank 的概念，再归结到使用超链接关系的排序系统来解决大规模疏松疏矩阵的特性值的问题。然后我们会接触一些在现实世界中应用基本模型时出现的问题和对应方法。接下来，为了探讨是否能够作为「个人化 PageRank」使用，进行对免费全文检索系统 Namazu 的安装实验并对其结果进行阐述。最后发表我对 PageRank 的个人见解。

另外，为了能够理解以下的说明内容，需要大学基础课程程度的数学知识(尤其是线形代数)。然而为使文科生也能够顺利读下去，尽可能地不用算式来说明问题，同时，为了加入笔者个人的见解，没有加入像原文那么多的算法和数字，也存在许多不够严密和欠正确的地方，事先在次声明。具体内容请参照原文。

PageRank^(TM) 是美国 Google 公司的登记注册商标。

2. PageRank 的基本概念

PageRank 是基于「从许多优质的网页链接过来的网页，必定还是优质网页」的回归关系，来判定所有网页的重要性。

在以下冗长的说明中，许多部分大量地使用了专业用语，会造成理解上的困难。这一章虽然准备集中于定性而简单的解说,但是，即使如此也会有怎么也不明白的时候，此时只要能够理解「从许多优质的网页链接过来的网页，必定还是优质网页」这一思考方法也就非常得可贵了。因为在所有几个要点中，这个是最重要的思考方法。

来自于 Google 自己的介绍「Google的受欢迎的秘密(http://www.google.co.jp/intl/ja/why_use.html)」 是象以下一样解说的。

关于PageRank
    PageRank，有效地利用了 Web 所拥有的庞大链接构造的特性。 从网页A导向网页B的链接被看作是对页面A对页面B的支持投票，Google根据这个投票数来判断页面的重要性。可是 Google 不单单只看投票数(即链接数)，对投票的页面也进行分析。「重要性」高的页面所投的票的评价会更高，因为接受这个投票页面会被理解为「重要的物品」。
    根据这样的分析,得到了高评价的重要页面会被给予较高的 Page Rank(网页等级)，在检索结果内的名次也会提高。PageRank 是 Google 中表示网页重要性的综合性指标，而且不会受到各种检索(引擎)的影响。倒不如说，PageRank 就是基于对"使用复杂的算法而得到的链接构造"的分析，从而得出的各网页本身的特性。
    当然，重要性高的页面如果和检索词句没有关联同样也没有任何意义。为此 Google 使用了精练后的文本匹配技术，使得能够检索出重要而且正确的页面。

通过下面的图我们来具体地看一下刚才所阐述的算法。具体的算法是，将某个页面的 PageRank 除以存在于这个页面的正向链接,由此得到的值分别和正向链接所指向的页面的 PageRank 相加，即得到了被链接的页面的 PageRank。

让我们详细地看一下。提高 PageRank 的要点，大致有3个。

• 反向链接数 (单纯的意义上的受欢迎度指标)
• 反向链接是否来自推荐度高的页面 (有根据的受欢迎指标)
• 反向链接源页面的链接数 (被选中的几率指标)

首先最基本的是，被许多页面链接会使得推荐度提高。也就是说「(被许多页面链接的)受欢迎的页面，必定是优质的页面」。所以以反向链接数作为受欢迎度的一个指标是很自然的想法。这是因为，“链接”是一种被看作「可以看看这个页面/这个页会有用」的推荐行为。但是，值得骄傲的是 PageRank 的思考方法并没有停留在这个地方。

也就是说，不仅仅是通过反向链接数的多少，还给推荐度较高页面的反向链接以较高的评价。同时，对来自总链接数少页面的链接给予较高的评价，而来自总链接数多的页面的链接给予较低的评价。 换句话说「(汇集着许多推荐的)好的页面所推荐的页面，必定也是同样好的页面」和「与感觉在被胡乱链接的链接相比，被少数挑选出的链接肯定是优质的链接」这两种判断同时进行着。一方面，来自他人高水平网页的正规链接将会被明确重视，另一方面，来自张贴有完全没有关联性的类似于书签的网页的链接会作为「几乎没有什么价值(虽然比起不被链接来说好一些)」而被轻视。

因此，如果从类似于 Yahoo! 那样的 PageRank 非常高的站点被链接的话，仅此网页的 PageRank 也会一下子上升；相反地，无论有多少反向链接数，如果全都是从那些没有多大意义的页面链接过来的话，PageRank 也不会轻易上升。不仅是 Yahoo!, 在某个领域中可以被称为是有权威的(或者说固定的)页面来的反向链接是非常有益的。但是，只是一个劲地在自己一些同伴之间制作的链接，比如像「单纯的内部照顾」这样的做法很难看出有什么价值。也就是说，从注目于全世界所有网页的视点来判断(你的网页)是否真正具有价值。

综合性地分析这些指标，最终形成了将评价较高的页面显示在检索结果的相对靠前处的搜索结构。

以往的做法只是单纯地使用反向链接数来评价页面的重要性，但 PageRank 所采用方式的优点是能够不受机械生成的链接的影响。 也就是说，为了提高 PageRank 需要有优质页面的反向链接。 譬如如果委托 Yahoo! 登陆自己的网站，就会使得 PageRank 骤然上升。但是为此必须致力于制作(网页的)充实的内容。这样一来，就使得基本上没有提高 PageRank 的近路(或后门)。不只限于PageRank (Clever 和 HITS 等也同样)，在利用链接构造的排序系统中，以前单纯的 SPAM 手法将不再通用。这是最大的一个优点，也是 Google 方便于使用的最大理由。(虽然是最大的理由,但并不是唯一的理由。)

在这里请注意，PageRank 自身是由 Google 定量，而与用户检索内容的表达式完全无关。就像后边即将阐述的一样，检索语句不会呈现在 PageRank 自己的计算式上。不管得到多少的检索语句，PageRank 也是一定的、文件固有的评分量。

PageRank 的定性说明大致就是这样一些。但是，为了实际计算排列次序、比较等级，需要更定量性的讨论。以下一章将做详细的说明。

3.怎样求得 PageRank

我们感兴趣的是，在有像超级链接构造那样的互相参照关系的时候，定量地知道哪一个页面是最「重要」的。换句话大胆地说，这个也就是严密计算「应该从哪一页开始读取」这个指标的过程。就算从谁都不看的小页面开始读取也没有办法。

那么，一般地说为了使得像 Web 那样的超级链接构造能够反映在在排列次序上，需要在计算机上建立超级链接构造的数字模型。 怎么模型化需要取决于安装者的方针所以一概而论，但是如果应用图表理论来观察超级链接构造的话，最终常常回到线形代数考虑方法上去。这对于 PageRank 也是一样的。

求得的 PageRank 的评价

首先应该关注的是，PageRank 的名次和反向链接的数目是基本一致的。无论链接多少正向链接都几乎不会影响 PageRank，相反地有多少反向链接却是从根本上决定 PageRank 的大小。但是，仅仅这些并不能说明第1位和第2位之间的显著差别(同样地、第3位和第4位，第6位和第7位之间的差别)。总之，绝妙之处在于 PageRank 并不只是通过反向链接数来决定的。

让我们详细地看一下。ID=1 的文件的 PageRank 是0.304，占据全体的三分之一，成为了第1位。特别需要说明的是，起到相当大效果的是从排在第3位的 ID=2 页面中得到了所有的 PageRank(0.166)数。ID=2页面有从3个地方过来的反向链接，而只有面向 ID=1页面的一个链接，因此(面向ID=1页面的)链接就得到了所有的 PageRank 数。不过，就因为 ID=1页面是正向链接和反向链接最多的页面，也可以理解它是最受欢迎的页面吧。

反过来，最后一名的 ID=6 页面只有 ID=1 的15％的微弱评价,这可以理解为是因为没有来自 PageRank 很高的 ID=1 的链接而使其有很大地影响。 总之，即使有同样的反向链接的数目，链接源页面评价的高低也影响 PageRank 的高低。

4.实际应用时的问题

PageRank 的基本考虑方法并不是很难的东西。实用效果中的巨大成分并不是复杂离奇的算法，而是进行简单的线性变换，倒不如都属于简明直观的类别吧。但是，实际使用 Web 超级链接构造来计算 PageRank 的话，不是简单地能够用嘴巴来说明的东西。主要的困难主要有二个。一、由来于纯粹假设的数值模型和现实世界的不同；二，在实际数值计算上(专门技术的)困难。

6.对 PageRank 的个人的见解

(读者)应该没有余地去怀疑象 PageRank 那样利用超级链接来决定排列次序有效手法吧。

不过，阅读了这些论文以后笔者自身也考虑了许多问题。在这里，列举几个对 PageRank 的个人见解。虽是见解,说到底就是方法论，也许会有很多错误的地方。

• 关于 dangling page，不相反考虑的原因是什么？

只是因为考虑一定的变异概率时「偶然」会变成最简才不予考虑吗？还是有时看漏了什么吗？稍微有点不太明白。

• 改善推移概率行列的可能性

  说起来，为了保证 PageRank 的单一意义的性质(一意)，只要保证推移概率行列是最简(有向图表是强联结)就行了，没有必要所有的要素 a_ij 都是非零要素。事实上，像在web上浏览 Toyota 汽车网站后紧接着跳向色情网站，接着又继续跳到白宫网站浏览的怪异的人应该是不存在的吧。(请注意这里是指在随时间变化连续的形式)。因此，从实用的意义上来说，区别于改善多少的使用方便程度，应该留下对算法改良的余地。

• 考虑「逗留概率」会怎样

根据 PageRank 的考虑方法，在一定的时间后必定顺着链接前进到其他的页面，或者突然怪异的、歪曲的跳到其他页面。但是如果对照现实的web浏览模型，也要考虑一定的逗留概率。具体地说，就是推移概率行列的对角成分中只取( 1-c)/N 的话取得过小了。在原本所有变迁概率都一定的情况下，更加进一步分析会怎样？因为对于无聊的页面(浏览者)必定会想都不想就转到另外的页面，反过来对于重要的页面却会停留较长的时间。

• 如果考虑概率论应用的话必定会考虑其他许多问题

即使是将实现性置之度外，我们也再来试着进一步考虑这个想法。概率论中，存在着一种叫消灭概率或叫固定概率的概率。比起 PageRank 的单纯而同样考虑方法，导入这种考虑方法会得到更期望的结果，所以理所当然被大家所期待。大家都知道马尔可夫链中的分枝过程的考虑方法。这是考虑遗传基因突变时的一个模型，即，说明经过一定的时间而产生淘汰的可能性的模型。很多人认为这个考虑方法或许会被采用。那么导入带有限制的概率(禁忌概率)又会怎么样呢？ 即，相当于导入通过 n 次的推移从状态 i 移动到状态 j 时，不经过状态 k 的概率。如果考虑到web浏览的性质的话，不是也能理所当然地成为假定吗？

• 不能作为非马尔可夫过程(或者说 m次的多重马尔可夫过程)来考虑吗

所谓马尔可夫过程，就是与过去的经历无关，只从现在的状态来确定未来的概率法则的概率过程。 马尔可夫过程只依存于1步之前的过程。这个过程和没有对过去的记忆，没有依存于过去经历的要素。 PageRank 是在单纯马尔可夫过程随时间变化而固定的状态下计算时候所求得的结果。但是，人类的理性行动必须以非马尔可夫过程来表现。复杂的过程总是以一些形式和过去有着牵连。因此，不仅仅单一地分析从哪个页面连接来，而要分析沿着怎样的路径连接而来的。这样的分析才会使其有可能成为更有用的排序系统。在能抑制住计算量爆炸的范围内，试着引入非马尔可夫过程来研究说不定也很有趣。

在考虑到和看到的许许多多中，有像实际安装那样不太难的东西，也有因为只是嘴上说说而不知道怎样实际安装的东西，不管怎样，定量地评价它的效果是极为困难的。难道真的是不能实现的东西吗？

PageRank 的技术有多少

即使只是采用评价很高的 PageRank 技术，作为基本的想法也只是使用了枯竭的数值分析的手法来实现的。但是，象我在这里说明的事情，如果从专业的研究者来看完全是理所当然的事情了。只是克服规模这一点就能建立一个专业的研究领域吧。 也可以认为专业领域的内部并没有那么深的尽头。事实上，我做事，充其量只是表示了「如果是极其小规模的问题，即使是教科书的手法也能大约地得到满足计算量的结果」。

尽管是这样，充其量只触及了概要的表面就在嘴边说「没什么嘛，原来是程度这么简单的技术呀」 的那种不懂装懂的人也是有的。在这里事先强调：这种浅薄的看法是从根本上完全错误的。

当然，PageRank 技巧的非常好的地方是「从许多优质的页面连接过来的页面是还是优质的页面」，如果明白了就会觉得是简单的想法。但更进一步说，真正绝妙的地方是，不仅仅只是想到一个主意，而是将想法用固定状态变迁的概率分布来定式化，为了实证其有效性而实际地进行安装实验，并证明其在现实领域也能很好地运作的过程。在所有的这些阶段都成功了才是真正值得被称赞的。

的确，不仅有斩新而且巧妙的想法，再加上结合教科书的手法，也有可能制造出能和 Google 匹敌(或是凌驾)的搜索引擎。也可以说实际上 Google 自己也在这么做着。但是，实际完成的人却是少得惊人。假想模型中的「肯定能够完成」的东西和实际运作的东西之间有着天差地别。在实际问题上，处理大规模疏松行列本身，通过一般的手法也是相当的困难，需要高度的专业技术。应该铭记在头脑中总觉得能够理解的事和实现中能够做的事之间绝对会有不能填埋的差距。不可过分轻率地考虑。

　

感谢转载！其他许多的个人站点和BBS都介绍了此文。

• ZDNet China中文 如何提高网站在Google中的排名(2003/1/6报道) 。读不了... :-)
• ZDNet China 如何评价一个网站的人气(2002/8/5报道) 还是中文。读不懂... :-)
• 中村正三郎「BRAVO! Linux」Linux Japan 2001年5月号
• InternetWatch Watcher选出的今天的站点2001年3月16日号
• InternetWatch 摘要新闻2001年2月26日号
• Google World > Japanese >计算机>因特网> WWW >主页检索 目录
• Lycos /计算机、因特网/因特网/站点的检索、链接集/搜索引擎/机器人检索/ Google 目录
• Yahoo! JAPAN 商务经济>企业>因特网服务>企业间交易(BtoB)>检索，导航> Google 目录