PageRank和HITS算法

PageRank和HITS是链接分析算法，它们根据超链接图的结构而非仅仅页面内容来估计网页的重要性或权威性。

Definition

PageRank为每个页面分配一个与查询无关的重要性分数，该分数等于一个随机冲浪者（random surfer）的稳态概率，该冲浪者以阻尼概率（damping probability）跟随出站链接，否则进行瞬移；而HITS则针对一个与查询相关的子图，计算具有有价值内容的页面的权威分数，以及链接到良好权威页面的枢纽分数，两者相互强化。

Scope

本主题涵盖了两种基础的链接分析算法：PageRank，一种基于带有“瞬移”（teleportation）的随机游走模型（random-surfer model）的与查询无关的页面重要性度量；以及HITS，一种计算相互强化的枢纽（hub）和权威（authority）分数的与查询相关的方案。它涉及底层的随机游走和特征向量公式、阻尼和瞬移的作用、收敛性以及主题敏感的变体。它不包括这些分数如何与文本特征结合以形成最终排名，这属于网络搜索排名的范畴。

Core questions

• 随机游走模型如何将PageRank定义为稳态分布？
• 为什么PageRank需要阻尼或瞬移因子才能被良好定义？
• HITS中的枢纽和权威分数如何相互强化？
• 这些分数是如何迭代计算的，它们何时收敛？
• PageRank和HITS在与查询无关和与查询相关评分方面有何不同？

Key concepts

• PageRank
• 随机游走模型
• 阻尼因子和瞬移
• 稳态分布/主特征向量
• HITS
• 枢纽和权威
• 与查询无关的评分 vs. 与查询相关的评分
• 幂迭代和收敛

Key theories

PageRank随机游走模型

模拟一个冲浪者，他以等于阻尼因子的概率跟随链接，否则跳到随机页面，这产生了一个马尔可夫链，其独特的稳态分布通过长期访问量对页面进行评分，从而提供了一个稳定、与查询无关的重要性度量。

HITS枢纽和权威

在以查询为中心的子图中，HITS为每个页面分配一个权威分数，该分数与链接到它的页面的枢纽分数成比例；并分配一个枢纽分数，该分数与它链接到的页面的权威分数成比例，通过迭代这些相互强化的关系直到收敛来计算。

Clinical relevance

PageRank是大规模网络搜索兴起的关键，并且仍然是图上重要性和权威性的概念参考点。链接分析的思想超越了网络，推广到引文网络、社交网络影响力、欺诈检测和推荐等领域，只要存在类似认可的链接携带信息，这些思想就适用。

History

在1998年和1999年，两项几乎同时提出的研究表明超链接编码着权威性：Kleinberg的HITS和Page与Brin的PageRank。PageRank的与查询无关、全局计算的分数被证明非常适合网络规模的服务，并支撑了一个领先的搜索引擎，而HITS则影响了主题提炼和后来的图排名研究。

Key figures

• Larry Page
• Sergey Brin
• Jon Kleinberg
• Rajeev Motwani

Seminal works

• page1999
• kleinberg1999
• brin1998

Frequently asked questions

PageRank和HITS有什么区别？

PageRank预先从整个网络图中为每个页面计算一个单一的、与查询无关的重要性分数，而HITS则在检索时，针对围绕查询构建的小型子图计算与查询相关的枢纽和权威分数。PageRank更容易扩展到网络服务。

为什么PageRank需要阻尼因子？

没有阻尼因子，随机冲浪者可能会被困在没有出站链接的页面或循环中，稳态分布可能不是唯一的或定义不明确。阻尼（瞬移）概率允许冲浪者偶尔跳到随机页面，从而保证了唯一且表现良好的分数。