现在的位置: 首页 > 搜索技术 > 正文

搜索引擎算法研究专题六:HITS算法

2017年12月19日 搜索技术 ⁄ 共 1240字 ⁄ 字号 评论关闭

HITS(Hyperlink-Induced Topic Search)是由Kleinberg在90年代末提出的基于链接分析的网页排名算法。该算法与查询相关。

  用HITS算法评估网页质量,可得到内容权威度(Authority)和链接权威度(Hub)。内容权威度与网页自身直接提供内容信息的质量相关,网页被引用得越多,其内容权威度越高;而链接权威度与网页提供的超链接的质量相关,引用内容质量高的网页越多,网页的链接权威度越高。

  一个好中心网页应该指向很多权威性网页,而一个好的权威性网页则应该被很多好的中心性网页所指向。对整个Web集合而言,Authority和Hub是相互依赖、相互加强、相互优化的关系,这是HITS算法的基础。

  HITS算法的施行是“迭代—收敛”的过程,即网页A链接权威度的数值是通过其链向的网页的内容权威度决定的,而网页A的内容权威度的数值则是由链向其的网页的链接权威度决定的。Authority和hub的值相互递归定义,即authority的值是指向给页面的hub值之和,而hub的值则是该页面指向的页面的authority值之和。

  每个节点的Hub和Authority的值用下述算法计算:

  赋予每个节点的hub值和authority值都为1。运行Authority更新规则。运行Hub更新规则。Normalize数值,即每个节点的Hub值除所有Hub值之和,每个Authority值除所有Authority值之和。必要时从第二步开始重复。

  在实施中还要考虑被链接页面的相关性。该算法要完成一系列迭代过程,每个迭代过程包含两个基本步骤:

  Authority值更新:更新每个节点的Authority值,为该节点指向的Hub的数值之和。即由信息Hubs链接的节点被赋予了高authority值。Hub值更新:更新每个节点的Hub值,使之等于它指向的每个节点的Authority值之和。即通过链接到同一主题的authorities节点的节点被赋予了高hub值。

  因在上述伪代码中,hub和authority的值不收敛,有必要限制该算法的迭代步数。方法之一是,在每步之后规范化hub和authority的值,即通过:dividingeach authority value by the sum of all authority values, and dividing each hubvalue by the sum of all hub values.

  与PageRank相似,HITS也是基于Web文档链接的迭代算法,然而也有一些重要差别:

  它是在查询时执行,而不是在建立索引时执行,与查询性能如时间等相关。因此,赋予页面的hub和authority权值也是query-specific。 它不是搜索引擎通用的技术(虽然据说Ask.com使用了相似的算法)。它计算了文档的两种权重即hub和authority,而非一种权重。它只处理相关文档的很小子集,而PageRank针对文档全集。

抱歉!评论已关闭.