HITS算法

最近在折腾HITS,PageRank,等。有所得。
无论是HITS,还是PageRank,都是对一个网络图做结构分析。最早用在搜索上,现在很多人也拿来做社交网络的分析。
言归正传。

——————————-

基本思路

无论是PageRank,还是HITS,它的基本出发点是一致的:它们都认为,在web上的一个从网页A指向网页B的link,代表着一种认可,表示网页A的作者认可网页B。当一个网页越被广泛认可,就表示这个网页越重要。

HITS更进一步,将这种认可细分成了两种属性:
Authority — 如果一个web page提供了关于某个topic的信息,那么这个page就是有价值的,这样的页面就是authorities;
如果有很多的其它page都指向该page,说明这个page的authority的值就高;

graph2

Hub — 还有一些页面,比如yahoo主页这种,虽然它本身不提供任何topic的信息,但是从yahoo主页出发,可以跳转到很多有价值的页面上去。这样的页面成为hubs;
之前用inlinks来衡量页面的authority,这里用outlinks来衡量页面的hub;

graph1

因为大部分的页面既有inlinks,又有outlinks,所以这些页面同时具有Authority和Hub的属性。HITS算法的核心,就是根据一个有向结构图,计算得到每个节点的authority和hub值。

算法

HITS最早是用来做搜索排序的,所以原始论文中描述的是执行搜索query的过程:

1. 用传统的,例如基于VSM的搜索引擎先进行搜索,从结果中选择t个top result;
2. 这t个页面被称为root set,t的数量级大概是几百;
3. root set中的每个页面,需要找出这些页面的inlinks的来源页面和outlinks所指向的页面;
4. root set + inlinks page + outlinks page的所有页面和它们之间的链接关系构成了一个有向图;
5. 计算这个有向图所有节点的authority 和 hub值 (重点!);
6. 将authority 和 hub值高的页面作为此次查询的结果返回;

在IR领域内,上述的整个流程称为HITS,但是其它领域使用HITS时,大多数只需要用到第5步的算法。
下面说说怎么计算authority和hub。

思路很简单, “mutually recursive”:

1. 假设每个节点i都有一个authority值 xi 和 一个hub值 yi;
2. 初始化的时候,给每个节点一个authority和hub的默认值,比如都是1;
3. 于是在下一次迭代的时候, 新的authority值 xi就等于节点i的inlinks对应节点的hub值之和:

clipboard

同样,新的hub值 yi 等于节点i的outlinks对应节点的authority值之和;

clipboard[5]

经过反复多次的迭代,就可以计算得到每个节点的authority 和 hub的收敛值。

矩阵计算

首先定义有向图的邻接矩阵:

clipboard[8]

计算的过程用矩阵表示:

clipboard[10]

千万别忘记了最后的normalization。因为authority 和 hub的计算都是sum计算,如果不做normalization,很容易就溢出了。

将上面的公式重构一下:

clipboard[12]

算法最终回归到计算邻接矩阵的特征向量。
实际计算过程中,不需要同时的迭代计算X和Y,只需要迭代的计算其中一个向量,比如X,然后根据 Y = LX就可以得到另外一个。

HITS的缺陷

我将HITS的问题分成了两类,一类是和搜索相关的,还有一类是与计算Authority和Hub值相关的。

1. HITS一个很大的诟病是,它是query-dependent。每一次query,都需要实时构造一个graph然后计算HITS,这点和PageRank相比尤其明显;
2. 另外一个问题是如何构造query对应的graph。原始的算法,是需要将root set的“周边”节点都放到graph中。如此设计的本意是为了扩展语义,能够将一些相关的(但term不匹配的)页面包含进来。但是这么做也引入了很多的问题,例如有些node的inlinks非常之多(想想有多少link指向了google首页),再比如某个节点可能有大量来自同一个host的inlinks,这可能权重由于该host被重复计算。实际上,HITS的原始论文中也对这些问题做了讨论,采取了一些过滤的措施,例如来源同一个host的inlinks/outlinks是有限制的,单个节点总的inlinks的数量也是有限制的。总之,需要小心的裁剪graph
3. Topic Drift. 这一点所有基于structure analysis的算法都会碰到这个问题,比如计算得到的authority的页面,可能并不和query相关。例如搜索“WWW conference”,得到权重最高的页面都来源于term “WWW”。解决办法是将structure analysis和content analysis结合起来;

以上的缺陷都是和搜索这个具体问题相关的。剩下的这个问题是和算法相关的,并且在我看来是最大的问题。

HITS对spamming很敏感,或者换句话说,HITS很容易被spam欺骗:

graph3

我们很容易构造出上图中的spammer节点,让他指向大量的Authority高的节点(构造outlinks很容易)。这样,该节点的Hub值就会特别高。因此,HITS算法中的Hub计算特别容易受干扰。而一旦获得了高Hub的spam节点,因为Authority和Hub是迭代着互相计算的,所以也就很容易“制造”出Authority高的节点。
根据我自己的实验,Hub排名高的节点没有太大的意义,几乎不可用。倒是Authority的排名还稍微好一些,但是也很容易受到inlinks很高的spam节点的影响。

 

总的来说,HITS有个非常好的特性,就是区分了节点的Authority和Hub属性。但是算法设计不如PageRank漂亮。

Reference

1. Authoritative Sources in a Hyperlinked Environment
2. A Survey of Eigenvector Methods of Web Information Retrieval

—END.—

Advertisements
相册 | 此条目发表在Link Analysis分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s