文档介绍：摘要:系统地分析了现有的页面排序算法,指出了它们各自的优势和存在的不足,并指出不同算法在不同领域和场合所具有的优势。建立专业搜索引擎是提高搜索准确性和性能的有效途径。通过网格技术将各种专业搜索引擎集成在一起,形成一个基于网格的搜索引擎,从而更好地满足不同背景不同偏好的用户需求。
关键词:搜索引擎;页面排序;链接分析
中图分类号::A
文章编号:1001-3695(2007)06-0004-04
的飞速发展,其提供的文档(网页)也以惊人的速度在增长。有关的调查统计表明,上的网页每不到一年的时间就会增长一倍。要从这么大量的信息库中提取出有用的信息就越来越依赖于搜索引擎的功能。而网页的排序则是搜索引擎要解决的关键问题之一。
Sergey Brin等人[1]提出PageRank算法开启了链接分析研究的热潮。基于链接分析的算法,提供了一种衡量网页质量的客观方法;独立于语言,独立于内容;无需人工干预就能自动发现Web上的重要资源,挖掘出Web上的重要社区,自动实现文档分类。PageRank在Google中的应用获得了巨大的商业成功。在最初的Google中,首先使用IR(Information Retrieve)算法找到所有与查询关键字相匹配的网页;然后根据页面因素(标题、关键字密度等)进行排名;最后通过PageRank得分调整网站排名结果。
近几年来,基于链接分析的页面排序算法一直是一个热点问题,学者提出了许多页面排序算法。
1 PageRank及其相关算法
基于链接分析的排序算法中,最为著名的就是PageRank。所谓链接分析主要基于如下两个重要假设:
①超文本链接包含了用户对一个网站的判断信息;
②对一个网站而言,如果其他网站链接到该网站的入链数越多,该网站越重要。
以上假设在各种基于链接分析的算法中均以某种方式体现出来。
PageRank算法
PageRank算法是最早提出的链接分析算法之一,并被Google用于计算网页的重要性得分。其基本思想是:如果网页 T 存在一个指向网页 A的链接,则表明T的所有者认为A比较重要,从而把T的一部分重要性得分赋予A。这个重要性得分的值则由 T 的PageRank值 PR(T)和T的出链(从T链出的链接)数C(T) 决定。具体公式为:PR(T) / C(T) 。而对于页面A, 其PageRank值 PR(A) 的计算如下:
PR(A)=PR(T 1)/C(T 1)+…+PR(T n)/C(T n)(1)
其中,T 1,T 2,…, T n为含有指向A链接的页面。
为了避免Link Sink(许多网页没有入链或出链)问题,对式(1)引入一个阻尼系数 d ,使其变为
PR(A)=(1-d)+d[PR(T 1)/C(T 1)+…+PR(T n)/C(T n)](2)
如此经过多次迭代,系统的PR值达到收敛。
PR 的计算公式可以从概率的角度解释为一个随机网络冲浪者随机选择一个网页后,不断地点击网页上的链接,但是从不返回;除非最后厌烦了才随机选择另一个页面。随机冲浪者访问某个页面的随机概率就是该页面的PageRank值;阻尼系数 d 就是随机冲浪者在某个页面会厌烦然后选择一个新页面的概率。页面的PageRank值越