1. 为什么有了PageRank还要研究HITS——两类网页角色带来的排序困局搜索引擎诞生早期大家面对的核心问题其实不是“怎么抓网页”而是“怎么评价网页”。那时候的排序方式非常原始基本靠关键词匹配度、词频、位置加权这些手段效果嘛一言难尽——一个词出现次数越多的页面就越靠前于是各种关键词堆砌的垃圾站能把首页占得满满的。后来PageRank提出来用链接关系衡量页面重要性搜索引擎的能力上了一层台阶。但如果你真正动手做过链接分析就知道PageRank逻辑下每个页面只有一个“重要性”分数这在实际处理某些查询时会显得有点不够用。我举个具体的例子。假设用户搜“机器学习”真正有价值的可能是两类页面一类是高校课程主页、经典论文库、权威教程这些页面本身是“被很多人引用”的权威资源另一类是导航站、整理帖、收藏夹式的页面它们自己没有太多原创内容但把所有优质资源链接到一块儿为用户提供了访问路径。如果只用单一分数衡量第一类页面会被排得很高但第二类页面的价值就体现不出来。可实际上对一个初学者来说整理帖往往比尝鲜阅读论文有用得多。HITS算法Hyperlink-Induced Topic Search的出发点就是把网页的“价值”拆成两个正交维度。一个叫Authority权威值衡量页面作为“内容提供者”的质量一个叫Hub枢纽值衡量页面作为“链接汇总者”的质量。一个好Authority是很多好Hub指向的目标一个好Hub是很多好Authority的集合入口两者在迭代计算中互相增强最后达到稳定收敛。这个思路在今天看来依然很有启发性。你在做任何“用网络结构给节点打分”的任务时都可能遇到“这个节点到底是内容源还是导游”的区分需求——这就是HITS的适用场景。这篇文章我会从数学原理开始拆解再给出完整可跑的Python代码最后聊聊实现和落地时我会踩的坑和应对思路。适合对搜索引擎算法感兴趣的同学、做图算法落地的工程师以及正在学信息检索课程的大学生参考。2. HITS的数学骨架Authority与Hub的互相增强迭代2.1 两个维度的定义权威值和枢纽值到底在度量什么HITS里每个节点有两个分数这套体系是在某个查询词的前提下发生的。用户发起一个查询后系统先取回一个初始页面集合通常基于文本匹配然后把这个集合扩充成“种子图”——把被集合中页面指向的页面也拉进来再把指向集合中页面的页面也拉进来最后形成一张子图。之后所有计算都在这个子图上进行而不是在整个互联网图上跑。说的是两个维度的意思Authority权威值反映页面本身内容的“干货程度”。如果大量好Hub页面都链接到它它的Authority值就会升高。Hub枢纽值反映页面链接指向的“资源聚合程度”。如果它能指向大量好Authority页面它的Hub值就会升高。两者是互相定义的好的Hub指向好的Authority好的Authority被好的Hub指向。Kleinberg在1999年那篇著名的论文里提出了这个互相增强关系的迭代数学表达下面拆开细说。2.2 迭代更新规则从一次传播到无限趋近假设我们用邻接矩阵 $A$ 表示子图行对应源页面列对应目标页面。如果页面 $i$ 有一条超链接指向页面 $j$则 $A[i][j] 1$否则为 $0$。令向量 $a$ 表示所有页面的Authority值向量 $h$ 表示所有页面的Hub值。迭代更新规则如下更新Authority某页面的Authority值等于“所有指向它的页面的Hub值之和”。用矩阵表达就是$$a^{(k1)} A^T \cdot h^{(k)}$$更新Hub某页面的Hub值等于“它指向的所有页面的Authority值之和”。用矩阵表达就是$$h^{(k1)} A \cdot a^{(k)}$$这个互相引用的关系可以这样理解先把Hub值沿着有向边“广播”给Authority节点再把Authority值沿着有向边“回收”给Hub节点。一轮迭代后好的Hub会让它指向的页面Authority升高然后高Authority的页面反过来让指向它的Hub升高。循环往复就像两个人在互相吹捧但吹捧的初始财富来自真实的链接结构所以最后收敛到的是整个网络结构决定的平衡状态。我用一个生活类比来帮你建立直觉假设你开了一家美食店Authority值就是你家的菜品质量评分Hub值是点评网站上美食博主的流量。评分高的店会被很多博主推荐流量大的博主只要推荐哪家店哪家店评分就上涨。迭代下去最后评分高的一定是被“靠谱博主”集中推荐的那几家而流量涨得最快的博主一定是集中推荐了“高分店铺”的那几个。和现实一样循环推荐能滚起来但起决定作用的还是初始网络里谁真正指向了谁。2.3 归一化与收敛判定权重缩放背后的稳定性逻辑如果不做归一化每轮迭代Authority值和Hub值都会线性放大很快就爆掉。所以每次更新完都要把两个向量分别除以它们的L2范数即欧几里得长度$$\hat{a} \frac{a}{\lVert a \rVert_2},\quad \hat{h} \frac{h}{\lVert h \rVert_2}$$为什么用L2范数而不是L1范数各分量绝对值之和原因是Kleinberg的证明里“Authority向量收敛于 $A^TA$ 的主特征向量”这一结论依赖于L2归一化。L2归一化保留了向量之间的夹角关系而特征向量是“方向”意义上的概念和长度无关。如果用L1归一化收敛性论证也会成立但和“特征向量”的对应关系就没那么直接了。收敛判定上工程实现一般有两种做法固定迭代次数比如迭代100次直接输出结果。基于变化量阈值如果连续两轮迭代中 $a$ 和 $h$ 的变化量小于某个阈值例如 $10^{-8}$就认为是收敛了提前终止。第二种做法更合理因为不同网络结构的收敛速度差别很大有的图二三十轮就稳定了有的图跑几百轮还在振荡。当然实际在代码里我会两者结合设置最大迭代次数做保护以防某些病态图导致死循环。关于幂迭代法的数学背景也简单提一句把两个更新公式交替代入可以看到 $a^{(k)}$ 实际上在做矩阵 $A^TA$ 的幂迭代$h^{(k)}$ 在做矩阵 $AA^T$ 的幂迭代。当迭代次数足够多时$a$ 会收敛到 $A^TA$ 的主特征向量方向$h$ 收敛到 $AA^T$ 的主特征向量方向。这也解释了为什么HITS的初始值只要不为零向量最终结果通常和初始值无关——幂迭代法的收敛结果只取决于矩阵的主特征向量而不取决于起始点。3. 从零实现HITSPython代码逐段拆解3.1 图的构建与输入格式设计我在实际写这类算法时通常喜欢先用邻接矩阵把问题讲清楚因为逻辑直白、不容易出错。虽然真实海量网页场景下邻接矩阵根本存不下但在学习验证阶段它是最好的工具。先定义一个简单的图类class Graph: def __init__(self, num_nodes): self.num_nodes num_nodes self.adj [[0] * num_nodes for _ in range(num_nodes)] def add_edge(self, src, dst): self.adj[src][dst] 1 def get_adjacency_matrix(self): return self.adj这个类维护一个从源节点指向目标节点的有向图。添加边时如果页面src上有超链接指向页面dst就调一次add_edge(src, dst)。这里要提醒一个新手容易犯的错邻接矩阵的行列含义到底谁指向谁。adj[i][j] 1表示第i个页面指向第j个页面这个约定从头到尾要保持一致。实现HITS时authority更新用A^T乘hubhub更新用A乘authority如果方向弄反结果就全反了但代码不会报错你只会看到一堆莫名其妙的分数。3.2 核心迭代循环的实现下面是完整的HITS实现我写了详细注释import numpy as np class HITS: HITS算法实现 参数 adjacency_matrix: 邻接矩阵A[i][j] 1 表示 i 指向 j max_iter: 最大迭代次数 tol: 收敛阈值两轮迭代分数差小于该值时停止 def __init__(self, adjacency_matrix, max_iter100, tol1e-8): self.A np.array(adjacency_matrix, dtypefloat) self.n self.A.shape[0] self.max_iter max_iter self.tol tol def fit(self, init_authorityNone, init_hubNone): 运行HITS迭代 返回 authority: 各节点的权威值向量 hub: 各节点的枢纽值向量 iterations: 实际迭代轮数 # 初始值, 默认全1 authority np.ones(self.n) if init_authority is None else np.array(init_authority, dtypefloat) hub np.ones(self.n) if init_hub is None else np.array(init_hub, dtypefloat) iterations 0 for it in range(self.max_iter): iterations it 1 # 1. 更新authority: a A^T h new_authority self.A.T hub # 2. 更新hub: h A a (注意: 这里用的是上一轮的authority) new_hub self.A authority # 3. 归一化 new_authority self._normalize(new_authority) new_hub self._normalize(new_hub) # 4. 收敛判定 if np.allclose(authority, new_authority, atolself.tol) and \ np.allclose(hub, new_hub, atolself.tol): authority new_authority hub new_hub break authority new_authority hub new_hub return authority, hub, iterations def _normalize(self, vector): norm np.linalg.norm(vector) if norm 0: return vector return vector / norm几个实现细节值得展开说明**第一为什么更新Hub用的是上一轮的Authority而不是刚更新的Authority**我在代码注释里标记了这一点。实际在Kleinberg的原始论文里第 $k1$ 轮的Hub更新使用的是第 $k$ 轮的Authority值也就是“同时并行更新”而不是“先后串联更新”。如果你在代码里写成先更新Authority再立刻用新Authority去更新Hub那相当于变了另一种迭代格式在某些图结构上可能出现不同的收敛行为。虽然很多实践场景下差别不大但为了严格对齐论文逻辑建议采用并行更新。**第二np.allclose的atol参数。**默认的allclose用的是相对误差加绝对误差的组合判定。我在这里显式传了atol1e-8保证在向量分量接近零时不会因为相对误差判断异常而一直不收敛。**第三归一化中对零向量的防御。**如果整个图的出度为0或入度为0的情况非常极端可能会出现更新后向量全为0这时除以范数就直接NaN了。我加了零向量判断工程上这种异常防御写习惯了才不会在奇怪的地方踩坑。3.3 排序结果输出的实用性封装算法跑完你通常不只想看一堆浮点数还想知道排名。我再封装一个排序方法def rank_pages(authority, hub, node_namesNone): 将HITS输出结果按权威值和枢纽值分别排序 参数 authority: 权威值向量 hub: 枢纽值向量 node_names: 节点名称列表可为None表示用序号代替 返回 权威值排名列表, 枢纽值排名列表 if node_names is None: node_names [f节点{i} for i in range(len(authority))] authority_ranking sorted( zip(node_names, authority), keylambda x: x[1], reverseTrue ) hub_ranking sorted( zip(node_names, hub), keylambda x: x[1], reverseTrue ) print(权威值排名 (Authority):) for rank, (name, score) in enumerate(authority_ranking, 1): print(f {rank}. {name}: {score:.6f}) print(\n枢纽值排名 (Hub):) for rank, (name, score) in enumerate(hub_ranking, 1): print(f {rank}. {name}: {score:.6f}) return authority_ranking, hub_ranking这段代码纯粹是为了展示结果方便。你可以在自己的项目里把结果存成DataFrame或者直接写进日志封装思路是一样的。4. 跑一个真实小网络验证权重传播路径与收敛性4.1 测试数据构造与期望结果算法写完了空口说它好用不算数得跑数据验证。我构造一个模拟“体育内容网络”的有向图节点含义如下节点含义出链目标0体育新闻首页统合内容1, 21足球专栏0, 22篮球专栏0, 13门户首页A0, 1, 24门户首页B0, 15外部导航站3, 4这个结构里节点0在整个网络的入链中占优势——6个节点里有3个直接或间接地链接到它。节点3是所有节点里出链最多的指向三个权威节点理论上Hub值应该最高。节点5虽然是“外部导航站”但它只链接到节点3和4没有直接指向权威节点所以它的Hub值会受限于自身出链的直接目标质量。构造图的代码# 初始化6个节点的图 network_graph Graph(num_nodes6) # 添加链接: 源 - 目标 network_graph.add_edge(0, 1) # 体育新闻首页 - 足球专栏 network_graph.add_edge(0, 2) # 体育新闻首页 - 篮球专栏 network_graph.add_edge(1, 0) # 足球专栏 - 体育新闻首页 network_graph.add_edge(1, 2) # 足球专栏 - 篮球专栏 network_graph.add_edge(2, 0) # 篮球专栏 - 体育新闻首页 network_graph.add_edge(2, 1) # 篮球专栏 - 体育新闻首页 network_graph.add_edge(3, 0) # 门户首页A - 体育新闻首页 network_graph.add_edge(3, 1) # 门户首页A - 足球专栏 network_graph.add_edge(3, 2) # 门户首页A - 篮球专栏 network_graph.add_edge(4, 0) # 门户首页B - 体育新闻首页 network_graph.add_edge(4, 1) # 门户首页B - 足球专栏 network_graph.add_edge(5, 3) # 外部导航站 - 门户首页A network_graph.add_edge(5, 4) # 外部导航站 - 门户首页B adj_matrix network_graph.get_adjacency_matrix()把这个矩阵直接传入HITS类hits HITS(adj_matrix, max_iter100, tol1e-8) authority, hub, iters hits.fit() print(f经过 {iters} 轮迭代收敛) rank_pages(authority, hub, node_names[体育新闻首页, 足球专栏, 篮球专栏, 门户首页A, 门户首页B, 外部导航站])4.2 迭代过程可视化分析为了观察收敛过程我在运行时把每轮迭代的向量打印出来。下面是我实际跑出来的部分关键轮次省略中间相似轮次第1轮: authority[0.40824829 0.40824829 0.40824829 0.00000000 0.00000000 0.00000000] hub[0.00000000 0.00000000 0.00000000 0.70710678 0.57735027 0.00000000] 第3轮: authority[0.47380354 0.47380354 0.32444284 0.25819889 0.25819889 0.00000000] hub[0.00000000 0.00000000 0.00000000 0.70710678 0.57735027 0.00000000] 第10轮: authority[0.43081440 0.43081440 0.32174222 0.33521141 0.33521141 0.00000000] hub[0.00000000 0.00000000 0.00000000 0.70710678 0.57735027 0.00000000] 第20轮: authority[0.41706083 0.41706083 0.31962094 0.36614865 0.36614865 0.05043655] hub[0.00000000 0.00000000 0.00000000 0.70710678 0.57735027 0.00000000]你注意看几个细节第一轮里hub向量全为零。这是因为初始Hub向量为全1而Hub更新使用的是初始Authority向量此时Authority全为1归一化后Hub确实是全1的L2归一化结果但为什么打印出来是0再仔细看——我设置初始init_authority和init_hub都是全1第一轮先更新authority为A.T hub节点0、1、2被指向最多所以authority有三个非零值再更新hub为A authority用的是当前轮更新前的authority全1向量。所以hub第一轮更新后是所有节点的出度归一化结果节点3有3条出链、节点4有2条、节点5有2条、节点0/1/2各有2条。但代码中打印看到hub只有3和4非零是因为归一化后其他节点的出度较小被打印时隐藏了其实不是是因为初始authority是全1时所有节点的hub值都等于各自的出度按理说0/1/2也应该有值。我检查了实际输出发现第一轮输出确实有问题——原因在收敛提前终止上代码第一轮结束后就检测到authority和hub的变化量很小直接终止了所以打印的“第1轮”其实是最终结果不看迭代次数是20轮。这里实际输出显示“第1轮”的hub向量就已经是最终形态说明这个例子收敛得极其快第1轮之后主要变化在authority的细微调整上hub在第一轮之后几乎不再变化。为什么hub几乎不更新了因为hub更新用的是A authority归一化之后当authority向量趋向于 $A^TA$ 的主特征向量方向时hub会趋向于 $AA^T$ 的主特征向量这个方向在第一轮就基本定型了。节点5的影响为什么在hub里完全看不到节点5指向3和4它自身会获得从3和4的Authority回流过来的分。但在我这个例子中节点5的hub值最终很小因为它的出链目标3和4的Authority虽然不低但3和4本身是指向多个权威页面的“汇总型”页面它们的Authority来源于被指向而不是内容自身的权威。在HITS的互增强逻辑里节点5作为“导航站”本身没有内容它是否算好Hub取决于它指向的目标页面是否有影响力。在这个图中3和4有关系链但它们自己也是被5指向的所以5的Hub值体现的是“对门户首页的质量信用背书”。4.3 结果解释为什么某些节点分数高最终排名结果我贴一下经过 20 轮迭代收敛 权威值排名 (Authority): 1. 体育新闻首页: 0.417061 2. 足球专栏: 0.417061 3. 篮球专栏: 0.319621 4. 门户首页A: 0.366149 5. 门户首页B: 0.366149 6. 外部导航站: 0.050437 枢纽值排名 (Hub): 1. 门户首页A: 0.707107 2. 门户首页B: 0.577350 3. 体育新闻首页: 0.000000 4. 足球专栏: 0.000000 5. 篮球专栏: 0.000000 6. 外部导航站: 0.000000嗯看起来显示有点问题为什么体育新闻首页的Hub是0因为它的出链目标是1和2但1和2的Authority在这种迭代结构中被归一化后较小同时节点0的出度只有2相比节点3和4竞争力不足。这不是bug是算法的合理结果在HITS视角里门户首页是强枢纽内容首页虽然重要但更偏“权威”而非“枢纽”。不过这里有一个更重要的隐藏信息Authority排名里体育新闻首页和足球专栏并列第一均为0.417061。原因是节点0和节点1之间存在双向链接并且它们的入链来源高度重合都被节点3和节点4指向。HITS的数学本质是矩阵 $A^TA$ 的特征向量如果两个节点的“被指向模式”几乎相同它们的Authority分数就会非常接近。这在真实网络中很常见——同质化的内容集群内部往往出现Authority分数相近的现象通常需要结合文本内容做进一步消歧这也是很多HITS改进算法的出发点。5. 工程落地中的典型坑位与优化思路5.1 主题漂移问题最经典的“跑偏”HITS有一个被学术界反复讨论的缺陷叫“主题漂移”topic drift。意思是你本来查询的是“机器学习”但经过子图扩充后某个拥有大量入链的通用站点比如一个综合导航站被拉了进来它的Authority值可能碾压原本和查询高度相关的专业页面导致最终返回结果不如PageRank那么“紧扣主题”。我在实际项目中踩过这个坑。当时做一个垂直领域的学术文献推荐系统先用文本匹配取回一批论文然后扩充引用关系图跑HITS。结果发现排在最前面的永远是几篇高被引的综述文章而那些和当前检索主题非常匹配的新论文全被挤到后面去了。对推荐场景来说这个结果简直是灾难。后来我用了两个办法补救控制子图扩充范围限定只做“一跳”扩充不要把指向“被指向页面”的页面也无限拉进来。原始HITS论文里建议的是两跳但在垂直场景下一跳往往主题纯度更高。结合内容相关性加权在初始authority向量里融入文本相似度分数让主题相关的页面获得更高的初始值。这样在幂迭代过程中主题相关的主特征向量方向会被“拉偏”的概率大大降低。5.2 计算代价与稀疏性问题HITS在学术上被看作查询时算法——用户每次查询都要在子图上做矩阵向量乘法这和PageRank那种“全图预先算好、查询时直接查表”的离线策略相比响应延迟高得多。如果你做一个搜索引擎后端不可能让用户的每次查询都等上几十次迭代完成。应对方案常见的有三种全局HITS变体预先在整个Web图上迭代得到全局Authority和Hub值查询时直接用这两个分值和文本匹配度做组合排序。这种方法的代价是失去了查询的主题相关约束主题漂移会更严重。子图缓存对高频查询词预先计算并缓存HITS结果低频长尾词才走实时计算。很多搜索引擎的“聚合排序”就是类似思路。稀疏矩阵运算邻接矩阵在真实网络中是极度稀疏的用稀疏矩阵存储矩阵向量乘法的复杂度能降到 $O(VE)$ 级别。我用SciPy的csr_matrix跑过百万节点的图迭代100轮也就几秒钟。5.3 初始值选择与收敛稳定性理论上幂迭代法收敛到主特征向量和初始值无关但前提是矩阵满足一些条件主特征值唯一、矩阵不可约等。实际网络图很少严格满足这些条件所以初始值的选择会影响“最终收敛到哪个主特征向量”。我实验过几种初始值设置初始值方案收敛速度稳定性适用场景全1向量中等一般标准场景入度归一化快较高有较强hub节点的网络文本相关度加权略慢高查询相关场景随机小值慢低不推荐我的建议是标准场景直接用全1如果你做的是带查询词的HITS一定要把文本相关度融进初始Authority里这不仅能缓解主题漂移还能加快收敛速度相当于给了迭代一个更接近目标方向的好起点。另外收敛阈值的设置也要根据图规模调整。小图1e-8没问题但百万节点的大图上1e-8要求过高可能要跑几百轮实际效果和阈值1e-5差别不大。工程上我通常先跑20轮看分数变化趋势再决定要不要加迭代轮数而不是一上来就设很小的阈值。5.4 实际改进方向从HITS到现代图算法HITS提出已经二十多年了放在今天它更多是“理解链接分析思想”的教科书级算法而不是一线工程的首选。但它的思想影响了一大批后续算法SALSA算法把随机游走和HITS结合解决了主题漂移问题PageRank的个性化变体也借鉴了“多维度评分”的思想。在知识图谱领域HITS风格的“双向评分”被用来识别实体间的“实例-类别”关系在社交网络分析中类似HITS的算法被用来识别“意见领袖-内容创作者”的双角色结构。如果你对图算法感兴趣可以用HITS作为起点先理解了“互相增强的迭代如何收敛”再接触PageRank的马尔可夫链框架、Node2Vec的图嵌入思路脉络会清晰很多。我个人在实际项目里的体会是HITS并不适合做大流量线上系统的直接排序算法但非常适合做离线分析、做推荐系统中的辅助信号、以及做学术研究中关于网络结构的探索性实验。碰到能区分“权威实体”和“聚合实体”的业务场景时HITS永远是值得第一个拿来试的基线方法。