比较pagerank算法和hits算法的优缺点

《比较pagerank算法和hits算法的优缺点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、题目：请比较PageRank算法和HITS算法的优缺点，除此之外，请再介绍2种用于搜索引擎检索结果的排序算法，并举例说明。答：1998年，SergeyBrin和LawrencePage[1]提出了PageRank算法。该算法基于“从许多优质的网页链接过来的网页，必定还是优质网页”的回归关系，来判定网页的重要性。该算法认为从网页A导向网页B的链接可以看作是页面A对页面B的支持投票，根据这个投票数来判断页面的重要性。当然，不仅仅只看投票数，还要对投票的页面进行重要性分析，越是重要的页面所投票的评价也就越高。根据这样的分析，得到了高评价的重要页面会被给予较高的PageRank值，在检索结果内的名次

2、也会提高。PageRank是基于对“使用复杂的算法而得到的链接构造”的分析，从而得出的各网页本身的特性。HITS算法是由康奈尔大学(CornellUniversity)的JonKleinberg博士于1998年首先提出。Kleinberg认为既然搜索是开始于用户的检索提问，那么每个页面的重要性也就依赖于用户的检索提问。他将用户检索提问分为如下三种：特指主题检索提问（specificqueries，也称窄主题检索提问）、泛指主题检索提问（Broad-topicqueries，也称宽主题检索提问）和相似网页检索提问（Similar-pagequeries）。HITS算法专注于改善泛指主题检索的结

3、果。Kleinberg将网页（或网站）分为两类，即hubs和authorities，而且每个页面也有两个级别，即hubs（中心级别）和authorities（权威级别）。Authorities是具有较高价值的网页，依赖于指向它的页面；hubs为指向较多authorities的网页，依赖于它指向的页面。HITS算法的目标就是通过迭代计算得到针对某个检索提问的排名最高的authority的网页。通常HITS算法是作用在一定范围的，例如一个以程序开发为主题的网页，指向另一个以程序开发为主题的网页，则另一个网页的重要性就可能比较高，但是指向另一个购物类的网页则不一定。在限定范围之后根据网页的出度和入

4、度建立一个矩阵，通过矩阵的迭代运算和定义收敛的阈值不断对两个向量authority和hub值进行更新直至收敛。从上面的分析可见，PageRank算法和HITS算法都是基于链接分析的搜索引擎排序算法，并且在算法中两者都利用了特征向量作为理论基础和收敛性依据。虽然两种算法均为链接分析算法，但两者之间还是有明显的区别的。HITS算法计算的authority值只是相对于某个检索主题的权重，因此HITS算法也常被称为Query-dependent算法；而PageRank算法是独立于检索主题，因此也常被称为Query-independent算法。PageRank算法的优点在于它对互联网上的网页给出了一个

5、全局的重要性排序，并且算法的计算过程是可以离线完成的，这样有利于迅速响应用户的请求。不过，其缺点在于主题无关性，没有区分页面内的导航链接、广告链接和功能链接等，容易对广告页面有过高评价；另外，PageRank算法的另一弊端是，旧的页面等级会比新页面高，因为新页面，即使是非常好的页面，也不会有很多链接，除非他是一个站点的子站点。这就是PageRank需要多项算法结合的原因。HITS算法的优点在于它能更好地描述互联网的组织特点，由于它只是对互联网中的很小的一个子集进行分析，所以它需要的迭代次数更少，收敛速度更快，减少了时间复杂度。但HITS算法也存在如下缺点：中心网页之间的相互引用以增加其网页评

6、价，当一个网站上的多篇网页指向一个相同的链接，或者一个网页指向另一个网站上的多个文件时会引起评分的不正常增加，这会导致易受“垃圾链接”的影响；网页中存在自动生成的链接；主题漂移，在邻接图中经常包括一些和搜索主题无关的链接，如果这些链接自身也是中心网页或权威网页就会引起主题漂移：对于每个不同的查询算法都需要重新运行一次来获取结果。这使得它不可能用于实时系统，因为对于上千万次的并发查询这样的开销实在太大。PageRank算法和HITS算法都是客观的描述了网页之间的本质特征，但是它们都很少考虑到用户浏览习惯时的主题相关性。Hilltop算法：HillTop，是一项搜索引擎结果排序的专利，是Goog

7、le的一个工程师Bharat在2001年获得的专利。HillTop算法的指导思想和PageRank是一致的，即都通过反向链接的数量和质量来确定搜索结果的排序权重。但HillTop认为只计算来自具有相同主题的相关文档链接对于搜索者的价值会更大，即主题相关网页之间的链接对于权重计算的贡献比主题不相关的链接价值要更高。在1999-2000年，当这个算法被Bharat与其他Google开发人员开发出来的时候，他们称这