什么是HITS算法 | 集智百科-集智俱乐部
集智百科精选”是一个长期专栏,持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目,集智百科希望打造复杂性科学领域最全面的百科全书,欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入!

今天分享网络科学领域里面HITS算法这一主题。同为网络算法,HITS算法比较与PageRank算法有什么不同呢?本文将介绍HITS的基本概念,有哪些好玩的案例,知名的研究者、一些入门的学习资源。


目录


一、HITS算法的起源

二、HITS算法的原理

三、HITS、PageRank算法的区别

四、知名学者推介

五、相关资源推介

六、集智百科词条志愿者招募



一、HITS算法的起源

HITS算法的全称是“基于超链接的主题搜索”(Hyperlink-Induced Topic Search)。该算法于1999年由Jon Kleinberg提出,是一种用于对网页进行排序的算法。网页排序之后的结果有助于人们更方便地得到所关注的信息。

 

什么是HITS算法 | 集智百科-集智俱乐部

图1:HITS算法示意图


HITS算法受学术期刊排名方法的启发。顶级期刊(如Science)被引用的次数很多,具有很高的影响因子,具有更高的权威性。故而在比较某两个被引用次数大致相同的期刊时,被顶级期刊引用次数多的那个排名会更高。


HITS算法和PageRank算法在原理上有些类似。都既考虑网页本身的链接数,也考虑所链接网页的权威性。不过它们在概念模型、计算思路以及技术实现细节上有不同之处。

 


二、HITS算法的原理


权威值与枢纽值


HITS算法的基本思想是:每个网页的重要性由两个指标刻画,权威值(Authority)与枢纽值(Hub)。一个权威值高的网页会被很多网页指向(如微博大V)。一个枢纽值高的网页会指向很多网页(如大型目录网页),见下图。


什么是HITS算法 | 集智百科-集智俱乐部

图2:评价重要性的两个指标:权威值 Authority 与枢纽值 Hub


举例来说,当我们查找与“集智俱乐部”有关的网页时,集智俱乐部首页有较高的权威值,因为相关网页都会指向首页。另一方面,当某个网页指向大量权威机构首页时,那么该网页就会有较高的枢纽值。


权威值和枢纽值是互相依存、互相影响的,它们的计算方式如下:


  • 某网页的权威值 = 所有指向它的网页的枢纽值之和。

什么是HITS算法 | 集智百科-集智俱乐部

  • 某网页的枢纽值 = 所有它指向网页的权威值之和。


什么是HITS算法 | 集智百科-集智俱乐部


根集合与基本集合


HITS算法并非在互联网中所有的网页上计算,而是只关注一小部分网页。该算法首先通过文本搜索找到与关键词最相关的页面,得到根集合(root set)。然后从根集合延展,找到与其直接相连的网页(即邻居),得到基本集合(base set)。根集合与基本集合构成一个子图,即HITS算法的输入网页。


什么是HITS算法 | 集智百科-集智俱乐部

图3:HITS算法的输入网页


算法流程:


1. 初始化:将各节点的权威值和枢纽值均设为1。

2. 更新节点的权威值

3. 更新节点的枢纽值

4. 将权威值和枢纽值归一化。

5. 重复2-4步骤,直至最终收敛。



三、HITS、PageRank算法的区别 


HITS算法和PageRank算法可以看作兄弟算法。因为他们是同时期提出的对网页进行排序的两种算法。并且他们的原理有相似之处,都考虑了权威性网站的作用。

什么是HITS算法 | 集智百科-集智俱乐部

图4:PageRank算法示意


但这两种算法也有区别:


  • HITS计算每个网页的权威值和枢纽值,将二者分开考虑。而PageRank只计算PageRank值。

  • HITS只处理与关键词相关的网页集合,范围很小。而PageRank是全局算法,会计算互联网中所有网页的PageRank值。

  • 因为上一点的缘故,HITS算法更适合部署在客户端,而PageRank更适合部署在服务器端。


四、知名学者简介


Jon Kleinberg


什么是HITS算法 | 集智百科-集智俱乐部

图5:Jon Kleinberg


美国计算机科学家,康奈尔大学计算机科学教授。2006年获得国际数学联盟颁发的内万林纳奖。Kleinberg的研究跨越了从计算机网络由到数据挖掘到生物分子结构比对等诸多领域。他最为人称道的成就是“小世界理论”和万维网搜索算法。他设计了HITS算法,该算法的相关研究工作启发了Google的PageRank算法的诞生。


五、相关资源推荐


经典文献


Jon M. Kleinberg. 1999. Authoritative sources in a hyperlinked environment. J. ACM46, 5 (Sept. 1999), 604–632. 

HITS原版论文(引用超1万次)

https://dl.acm.org/doi/10.1145/324133.324140

文章

该文章介绍HITS算法的HITS算法的来源、原理,并利用python和MapReduce实现该算法。

HITS算法—从原理到实现

https://www.cnblogs.com/rubinorth/p/5800624.html


六、百科项目志愿者招募


作为集智百科项目团队的成员,本文内容由张祺、刘世康、李媛翯参与贡献。我们也为每位作者和志愿者准备了专属简介和个人集智百科主页,更多信息可以访问其集智百科个人主页:


什么是HITS算法 | 集智百科-集智俱乐部

什么是HITS算法 | 集智百科-集智俱乐部

什么是HITS算法 | 集智百科-集智俱乐部

什么是HITS算法 | 集智百科-集智俱乐部


以上内容都是我们做这项目的起点,作为来自不同学科和领域的志愿者,我们建立起一个有效的百科团队,分配有审校、翻译、编辑、宣传等工作。我们秉持:知识从我而来,问题到我为止的信念,认真负责编撰每一个词条。


在这里从复杂性知识出发与伙伴同行,同时我们希望有更多志愿者加入这个团队,使百科词条内容得到扩充,并为每位志愿者提供相应奖励与资源,建立个人主页与贡献记录,使其能够继续探索复杂世界。


欢迎扫描下方二维码添加负责人加入集智百科团队!


什么是HITS算法 | 集智百科-集智俱乐部


考资料


[1]HITS 集智百科

https://wiki.swarma.org/index.php?title=HITS算法_HITS_algorithm

[2]HITS 百度百科:

https://baike.baidu.com/item/HITS算法

[3]HITS 维基百科:

https://en.wikipedia.org/wiki/HITS_algorithm


来源:集智百科
编辑:曾祥轩



推荐阅读


混沌理论 | 集智百科
什么是PageRank算法 | 集智百科
PNAS前沿:悲观预测50年后全球气候,35%的区域不再宜居
棒不打鸳鸯:一种高效的聚类和社团发现算法
Nature:构建新冠肺炎蛋白质相互作用网络,潜在特效药缩小至69种
加入集智,一起复杂!




什么是HITS算法 | 集智百科-集智俱乐部



集智俱乐部QQ群|877391004

商务合作及投稿转载|swarma@swarma.org

◆ ◆ 

搜索公众号:集智俱乐部


加入“没有围墙的研究所”

什么是HITS算法 | 集智百科-集智俱乐部

让苹果砸得更猛烈些吧!



👇点击“阅读原文”,阅读集智百科更多有关HITS算法内容