049|PageRank算法的核心思想是什么？
2017-12-25洪亮劼来自北京
《AI技术内参》
上周我们介绍了信息搜索系统的历史进程，剖析了搜索系统的多轮打分系统，还深入探讨了倒
排索引，聊了聊它的核心技术。
这周我要和你分享的是在互联网搜索引擎兴起之后的一个研发需要，那就是如何理解网页和网
页之间的关系，特别是怎么从这些关系中提取网页中除文字以外的其他特性。这部分的一些核
心算法曾是提高搜索引擎质量的重要推进力量。另外，我们这周要分享的算法也适用于其他能
够把信息用结点与结点关系来表达的信息网络。
今天，我们先看一看用图来表达网页与网页之间的关系，并且计算网页重要性的经典算法：
PageRank。
PageRank的简要历史
时至今日，谢尔盖·布林（SergeyBrin）和拉里·佩奇（LarryPage）作为Google这一雄厚科
技帝国的创始人，已经耳熟能详。但在1995年，他们两人还都是在斯坦福大学计算机系苦读
的博士生。那个年代，互联网方兴未艾。雅虎作为信息时代的第一代巨人诞生了，布林和佩奇
都希望能够创立属于自己的搜索引擎。1998年夏天，两个人都暂时离开斯坦福大学的博士生
项目，转而全职投入到Google的研发工作中。他们把整个项目的一个总结发表在了1998年
的万维网国际会议上（WWW7，theseventhinternationalconferenceonWorldWide
Web）（见参考文献[1]）。这是PageRank算法的第一次完整表述。
PageRank一经提出就在学术界引起了很大反响，各类变形以及对PageRank的各种解释和
分析层出不穷。在这之后很长的一段时间里，PageRank几乎成了网页链接分析的代名词。给
你推荐一篇参考文献[2]，作为进一步深入了解的阅读资料。
PageRank的基本原理
我在这里先介绍一下PageRank的最基本形式，这也是布林和佩奇最早发表PageRank时的
思路。
首先，我们来看一下每一个网页的周边结构。每一个网页都有一个“输出链接”（Outlink）
的集合。这里，输出链接指的是从当前网页出发所指向的其他页面。比如，从页面A有一个
链接到页面B。那么B就是A的输出链接。根据这个定义，可以同样定义“输入链接”
（Inlink），指的就是指向当前页面的其他页面。比如，页面C指向页面A，那么C就是A
的输入链接。
有了输入链接和输出链接的概念后，下面我们来定义一个页面的PageRank。我们假定每一个
页面都有一个值，叫作PageRank，来衡量这个页面的重要程度。这个值是这么定义的，当前
页面I的PageRank值，是I的所有输入链接PageRank值的加权和。
那么，权重是多少呢？对于I的某一个输入链接J，假设其有N个输出链接，那么这个权重就
是N分之一。也就是说，J把自己的PageRank的N分之一分给I。从这个意义上来看，I的
PageRank，就是其所有输入链接把他们自身的PageRank按照他们各自输出链接的比例分配
给I。谁的输出链接多，谁分配的就少一些；反之，谁的输出链接少，谁分配的就多一些。这
是一个非常形象直观的定义。
然而，有了这个定义还是远远不够的，因为在这个定义下，页面I和页面J，以及其他任何页
面的PageRank值是事先不知道的。也就是等式两边都有未知数，这看上去是个无解的问
题。
布林和佩奇在他们的论文中采用了一种迭代算法。这个算法很直观，那就是既然不知道这些
PageRank的值，那我们就给他们一组初始值，这个初始值可以是这样的情形，所有页面有
相同的PageRank值。然后，根据我们上面所说的这个定义，更新所有页面的PageRank
值。就这么一遍一遍地更新下去，直到所有页面的PageRank不再发生很大变化，或者说最
后收敛到一个固定值为止。他们在文章中展示了实际计算的情况，往往是在比较少的迭代次数
后，PageRank值就能够收敛。
以上就是整个PageRank算法的基本思想和一种迭代算法。
PageRank算法的改进
完全按照我们上面介绍的这个最原始的PageRank算法，布林和佩奇很快就遇到了麻烦。
第一个麻烦就是有一些页面并没有输出链接，比如某些PDF文件，或者一些图片文件。由于
没有输出链接，这些页面只能聚集从上游输入链接散发过来的PageRank值，而不能把自己
的PageRank值分发出去。这样的结果就