上周我们介绍了信息搜索系统的历史进程,剖析了搜索系统的多轮打分系统,还深入探讨了倒排索引,聊了聊它的核心技术。
这周我要和你分享的是在互联网搜索引擎兴起之后的一个研发需要,那就是如何理解网页和网页之间的关系,特别是怎么从这些关系中提取网页中除文字以外的其他特性。这部分的一些核心算法曾是提高搜索引擎质量的重要推进力量。另外,我们这周要分享的算法也适用于其他能够把信息用结点与结点关系来表达的信息网络。
今天,我们先看一看用图来表达网页与网页之间的关系,并且计算网页重要性的经典算法:PageRank。
PageRank 的简要历史
时至今日,谢尔盖·布林(Sergey Brin)和拉里·佩奇(Larry Page)作为 Google 这一雄厚科技帝国的创始人,已经耳熟能详。但在 1995 年,他们两人还都是在斯坦福大学计算机系苦读的博士生。那个年代,互联网方兴未艾。雅虎作为信息时代的第一代巨人诞生了,布林和佩奇都希望能够创立属于自己的搜索引擎。1998 年夏天,两个人都暂时离开斯坦福大学的博士生项目,转而全职投入到 Google 的研发工作中。他们把整个项目的一个总结发表在了 1998 年的万维网国际会议上( WWW7,the seventh international conference on World Wide 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 值是事先不知道的。也就是等式两边都有未知数,这看上去是个无解的问题。