链接算法-authority算法解析

作者/来源：新睿云小编发布时间：2020-06-29

PageRank算法作为链接分析的基础算法之一虽说不错，但其弊端还是许多的，容易被作弊者做链接陷阱，或者弄链接农场来或许权重值。本身这些页面并不是用户所需要的，所以PageRank不能作为最终评分。

为了弥补这种弊端，于是康奈尔大学Jon Kleinberg 博士于1997 年首先提出的HITS算法。HITS算法是链接分析中非常基础且重要的算法，目前已被Teoma搜索引擎作为链接分析算法在实际中使用。

一、HITS算法简介

HITS算法中有两个比较重要的概念：

Hub页面：某个话题高质量目录

Authority页面：某个话题高质量内容页

如果互联网是一本书，则Hub相当于一本书的目录，目录中包含的页面是比较重要的页面。Authority则是被目录指向的页面，为重要的页面。

基本假设1：一个好的“Authority”页面会被很多好的“Hub”页面指向；

基本假设2：一个好的“Hub”页面会指向很多好的“Authority”页面；

HITS算法与PageRank算法有一个重要的区别，HITS算法是每次查询的时候权重值都需要迭代。PageRank则定期迭代，查询的时候已经计算完毕。

二、具体算法解析

具体算法：可利用上面提到的两个基本假设，以及相互增强关系等原则进行多轮迭代计算，每轮迭代计算更新每个页面的两个权值，直到权值稳定不再发生明显的变化为止。

1.根集合

1.1将查询q提交给基于关键字查询的检索系统，从返回结果页面的集合总取前n个网页(如n=200)，作为根集合(root set)，记为root，则root满足：

root中的网页数量较少

root中的网页是与查询q相关的网页

root中的网页包含较多的权威(Authority)网页

1.2扩展集合base

在根集root的基础上，HITS算法对网页集合进行扩充（参考图2）集合base，扩充原则是：凡是与根集内网页有直接链接指向关系的网页都被扩充到集合base，无论是有链接指向根集内页面也好，或者是根集页面有链接指向的页面也好，都被扩充进入扩展网页集合base。HITS算法在这个扩充网页集合内寻找好的“Hub”页面与好的“Authority”页面。

Hub与Authority

2.计算扩展集base中所有页面的Hub值（枢纽度）和Authority值（权威度）

分别表示网页结点 i 的Authority值(权威度)和Hub值(中心度)。

对于“扩展集base”来说，我们并不知道哪些页面是好的“Hub”或者好的“Authority”页面，每个网页都有潜在的可能，所以对于每个页面都设立两个权值，分别来记载这个页面是好的Hub或者Authority页面的可能性。在初始情况下，在没有更多可利用信息前，每个页面的这两个权值都是相同的，可以都设置为1，即：

每次迭代计算Hub权值和Authority权值：

网页 a (i)在此轮迭代中的Authority权值即为所有指向网页 a (i)页面的Hub权值之和：

a (i) = Σ h (i) ;

网页 a (i)的Hub分值即为所指向的页面的Authority权值之和：

h (i) = Σ a (i) 。

对a (i)、h (i)进行规范化处理:

将所有网页的中心度都除以最高中心度以将其标准化：

a (i) = a (i)/|a(i)| ；

将所有网页的权威度都除以最高权威度以将其标准化：

h (i) = h (i)/ |h(i)| ：

如此不断的重复第上一轮迭代计算中的权值和本轮迭代之后权值的差异，如果发现总体来说权值没有明显变化，说明系统已进入稳定状态，则可以结束计算，即a ( u),h(v)收敛。

给出了迭代计算过程中，某个页面的Hub权值和Authority权值的更新方式。假设以A(i)代表网页i的Authority权值，以H(i)代表网页i的Hub权值。在图6-14的例子中，“扩充网页集合”有3个网页有链接指向页面1，同时页面1有3个链接指向其它页面。那么，网页1在此轮迭代中的Authority权值即为所有指向网页1页面的Hub权值之和；类似的，网页1的Hub分值即为所指向的页面的Authority权值之和。

节点

3.输出排序结果

将页面根据Authority权值得分由高到低排序，取权值最高的若干页面作为响应用户查询的搜索结果输出。

上一篇 : 虚拟主机为什么仍然存在？其主要用途介绍

下一篇 : 云计算与大数据时代，服务器如何实现功能多样性？