PageRank是Google发明的用来衡量网页质量和重要性的,将无序的网页们变得有序。PageRank的发明,让Google的搜索结果大大领先于别的搜索引擎,从而开创了Google搜索独占鳌头的时代。
PageRank 的基本思想是被重要的网页所指的网页更重要:
如果一个网页被很多其它网页链接到的话说明这个网页比较重要,也就是PageRank值会相对较高;如果一个PageRank值很高的网页链接到一个其它的网页,那么被链接到的网页的PageRank值会相应地因此而提高。
简单的回顾一下PageRank 的计算公式。
上式是计算网页A的PageRank。Ti是页面中存在着到网页A的链接的网页。C(Ti)是网页Ti中的存在的所有链接的数量。d是阻尼系数,一般定义为用户随机点击链接(random walk)的概率,通常取值0.85。而(1-d)代表着不考虑入站链接的情况下随机进入一个页面的概率。
形象的解释,PageRank就像模拟一个悠闲的上网者,上网者首先随机选择一个网页打开,然后在这个网页上呆了几分钟后,跳转到该网页所指向的链接,这样无所事事、漫无目的地在网页上跳来跳去,PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。这里,
上网者是一个悠闲的上网者,而不是一个愚蠢的上网者,上网者是聪明而悠闲。他悠闲,漫无目的,总是随机的选择网页。他聪明,在走到一个终结网页或者一个陷阱网页,不会傻傻的干着急,他会在浏览器的地址随机(1-d)输入一个地址,当然这个地址可能又是原来的网页,但这里给了他一个逃离的机会,让他离开这万丈深渊。
由于
PageRank给原本无序的网页带来了有序
,在网页搜索中,PageRank发挥的作用是巨大的,总结如下几点。
第一,引导爬虫优先爬取高质量的网页
。爬虫从一些种子网页出发,提取网页中所有出现的链接,然后沿着新出现的链接,接着爬取,循环往复。在PageRank发明之前,爬虫要么随机选取新发现的链接,或是根据链接被发现的次数,来指导爬取的先后顺序,这样很难控制所爬取的网页的质量。PageRank发明之后,系统围绕每个时段的所有网页的快照,计算每个链接的PageRank,并排序。然后,爬虫根据PageRank的大小,择优爬取。由于资源限制,很难爬取所有网页,有了PageRank,就可以在有限资源下,快速的爬取千亿级别的高质量网页。由于PageRank能够保证爬下来索引的网页集合是高质量,尽可能减少作弊网页,为之后的处理提供了优质的起点。
第二,提高搜索结果排序
。在搜索词和文档的相关性差不多的情况下,PageRank大的排在前,也就是说用户先看到的是高质量的网页结果。常用的做法是将PageRank作为一个因子和相关性分数相乘得到最后的排序分数。比如,网页A和B和某个搜索词的相关性分数都是0.8,但PR(A) = 0.9,PR(B) = 0.8,那么Score(A) = 0.8*0.9 = 0.72,Score(B) = 0.8*0.8 = 0.64,显然A应该排在B之前。
第三,保证高质量网页能检索出来
。每个网页都有一个ID,ID按照PageRank的大小来赋值的,PageRank越大的高质量网页被赋予越小的ID。然后,倒排索引是根据ID排序的。这样检索时,只要检查前面的几千或上万个网页就行,不用检查所有含有某个词的网页,况且在响应时间要求下,不可能检查所有的包含搜索词的网页。比如,几乎所有的网页都包含“的”,如果搜索词中有“的”,系统不可能检查所有的网页并且给每个网页打分,那么,我们就需要只看前面的高质量的网页,也就是说ID小的网页。这样,至少保证我们的搜索结果中先出现的是好的网页。在这个过程中,一般使用固定大小的最小堆,如果下一个网页的相关性分数小于现在的最小值,扔掉。否则取代当前的最小值,再调整堆。