13、网页排名的HITS方法

网页排名的HITS方法

1. HITS算法概述

在网页搜索领域，除了广为人知的Google搜索，还有Teoma、Alexa和A9等搜索引擎。HITS（Hypertext Induced Topic Search）算法是用于网页排名的重要算法，它是Teoma搜索引擎流行度排名的基础。

HITS算法由Jon Kleinberg于1998年发明，与Brin和Page开发PageRank算法处于同一时期。和PageRank一样，HITS利用网页的超链接结构来为网页创建流行度得分，但也存在重要区别：
- PageRank为每个页面生成一个流行度得分，而HITS生成两个得分，分别是权威得分（authority score）和枢纽得分（hub score）。
- PageRank与查询无关，而HITS是查询相关的。

HITS将网页视为权威页面（authorities）和枢纽页面（hubs）。权威页面是有很多入链的页面，枢纽页面是有很多出链的页面。当“好的权威页面被好的枢纽页面指向，好的枢纽页面指向好的权威页面”这一循环陈述成立时，权威页面和枢纽页面才称得上“好”。因此，每个页面都在一定程度上既是权威页面又是枢纽页面。

2. HITS算法的数学表达

每个页面 $i$ 都有权威得分 $x_i$ 和枢纽得分 $y_i$。设 $E$ 是网页图中所有有向边的集合，$e_{ij}$ 表示从节点 $i$ 到节点 $j$ 的有向边。给定每个页面的初始权威得分 $x_i^{(0)}$ 和枢纽得分 $y_i^{(0)}$，HITS通过以下公式迭代细化这些得分：
[
x_i^{(k)} = \sum_{j:e_{ji} \in E}