050 | 经典图算法之HITS
洪亮劼
该思维导图由 AI 生成，仅供参考
这周我们分享的内容是如何理解网页和网页之间的关系。周一我们介绍了用图（Graph）来表达网页与网页之间的关系并计算网页的重要性，就是经典算法 PageRank。今天我来介绍一下 PageRank 的姊妹算法：HITS 算法。
HITS 的简要历史
HITS 是 Hypertext-Induced Topic Search 算法的简称。这个算法是由康奈尔大学计算机科学教授乔·克莱恩堡（Jon Kleinberg）于 1998 年发明的，正好和我们周一讲的布林和佩奇发表 PageRank 算法是同一年。
这里有必要简单介绍一下乔这个人。乔于 1971 年出生在马萨诸塞州波士顿。1993 年他毕业于康奈尔大学获得计算机科学学士学位，并于 1996 年从麻省理工大学获得计算机博士学位。1998 的时候，乔正在位于美国西海岸硅谷地区的 IBM 阿尔玛登（Almaden）研究院做博士后研究。HITS 的工作最早发表于 1998 年在旧金山举办的第九届 ACM-SIAM 离散算法年会上（详细论述可参阅参考文献）。
乔目前是美国国家工程院（National Academy of Engineering）和美国自然与人文科学院（American Academy of Arts and Sciences）院士。顺便提一下，乔的弟弟罗伯特·克莱恩堡也在康奈尔大学计算机系任教职。
HITS 的基本原理
在介绍 HITS 算法的基本原理之前，我们首先来复习一下网页的网络结构。每一个网页都有一个“输出链接”（Outlink）的集合。输出链接指的是从当前网页出发所指向的其他页面，比如从页面 A 有一个链接到页面 B，那么 B 就是 A 的输出链接。根据这个定义，我们来看“输入链接”（Inlink），指的就是指向当前页面的其他页面，比如页面 C 指向页面 A，那么 C 就是 A 的输入链接。
要理解 HITS 算法，我们还需要引入一组概念：“权威”（Authority）结点和“枢纽”（Hub）结点。这两类结点到底是什么意思呢？
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
HITS算法是一种用于计算网页重要性的算法，它包括权威值和枢纽值两个概念。权威值表示页面被其他枢纽页面链接的程度，而枢纽值表示页面链接到其他权威页面的程度。这种循环定义需要为每个页面准备两个值，即权威值和枢纽值。通过矩阵运算和特征向量求解，HITS算法可以计算出每个页面的权威值和枢纽值。与PageRank算法不同，HITS是查询关键字相关的算法，可以为用户提供不同的网页排序结果。然而，HITS算法在原始情况下可能不收敛到唯一解，需要进行类似于PageRank的处理。虽然HITS算法提供了新的视角，但其依赖于查询关键字可能导致计算量巨大。文章还提出了一个思考题，即是否可以将权威值和枢纽值对应的两个排序合并成一个排序。 HITS算法的核心思想是通过权威值和枢纽值来衡量网页的重要性，为用户提供不同的排序视角。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《AI 技术内参》，新⼈⾸单¥98
《AI 技术内参》，新⼈⾸单¥98
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(3)
- 最新
- 精选
xxw感觉可以适量列些公式。用文字表达公司有点闷逼2018-05-214
黄德平理一下思路，L表示连接矩阵，Lij是矩阵i行j列的元素，这个值取1当且仅当节点有链接指向节点j，否则为0。L的转置用M表示，根据权威值X和枢纽值Y的定义，我们可以得到 X=MY Y=LX 进一步可以得到 X=MLX Y=LMY LM和ML分别是两个矩阵的乘积，X和Y 可以迭代求解了。 真是费劲。。。 极客时间的回复是否可以支持latex公式渲染，或者图片2018-12-163
白杨某种意义上，可以把权威理解为精度，枢纽理解为广度，然后用F值的思想去合并2018-05-161
收起评论