搜索引擎

非完全PageRank策略(Partial PageRank)

既然都无法活着享用了,

现在我辛劳勤恳地收集这片叶子上的蜜露还有什么用呢?

为了这片灌丛的同胞们的利益所进行的政治斗争,

或者为了我们种族全体的利益所进行的哲学研究又有什么用呢?

                                                                                  —富兰克林

        PageRan是一种著名的链接分析算法,可以用来衡量网页的重要性(关于技术的细节,之后小编会讲链接的分析)。所以自然地,可以想到用PageRank的思想来对URL优先级进行顺序。但是这里有个问题是,PageRank是个全局性算法,也就是说当所有网页都下载完成后,其计算结果才是可靠的,而爬虫的目的就是去下载网页,在运行过程中只能看到一部分页面,所以在抓取阶段的网页是无法获得可靠PageRank得分的。

思考 非完全PageRank策略

        如果我们仍然坚持在这个“不完整”的互联网页面子集内计算PageRank呢?这就是非完全PageRank策略的基本思路: 对于已经下载网页,加上待抓取URL队列中的URL一起,形成网页集合,在此集合内进行PageRank计算,计算完成后,将待抓取URL队列里的网页按照PageRank得分由高到低排序,形成的序列就是爬虫接下来应该依次抓取的URL列表。这也是为何称之为“非完全PageRank的原因

        如果每次抓取到一个网页,就将所有已经下载的网页重新计算新的非完全PageRank值,明显效率太低,在现实中是 不可行的,一个折中的办法是:每当新下载的网页攒够K个,然后将所有下载页面重新计算一遍新的非完全PageRank。这样的计算效率还勉强能够接受,但是又引来新的问题:在展开下一轮PageRank计算之前,从新下载的网页抽取出包含的链接,很可能这些链接的重要性非常高,理应优先下载,这种情况该如何解决?非完全PageRank赋予这些新抽取出来,但是又没有PageRank值的网页一个临时PageRank值,将这个网页的所有入链传导的PageRank值汇总,作为临时PageRank值,如果这个值比待抓取URL队列中已经计算出来PageRank值的网页高,那么优先下载这个URL。

非完全PageRank策略

        我们设定每下载3个网页即进行新的PageRank值计算,此时已经有{P1,P2,P3}3个网页下载到本地,这3个网页包含的链接指向{P4,P5,P6},形成了待抓取URL队列,如何决定其下载顺序?将这6个网页形成新的集合,对这个集合计算PageRank值,这样P4,P5和P6就获得自己对应PageRank值,由大到小排序,即可得出其下载顺序。这里可以假设顺序为:P5,P4,P6,当下载P5页面后抽取出链接,指向页面P8,此时赋予P8临时PageRank值,如果这个值大于P4和P6的PageRank,则接下来优先下载P8。如此不断循环,即形成了非完全PageRank策略的计算思路。
       非完全PageRank看上去相对复杂,那么是否效果一定优于简单的宽度优先遍历策略呢?不同的实现结果存在争议,有些表明非完全PageRank结果略优,有些实现结果结论则恰恰相反。更有研究人员指出,非完全PageRank计算得出的重要性于完整的PageRank计算结果差异很大,不应作为衡量抓取过程中URL重要性计算的依据。