COMP5313 Tutorial 05 - Hub and Authority 题解

Posted on Edited on In , Word count in article: 3.4k Reading time ≈ 12 mins.

Week 5 Tutorial: Hub and Authority 题解

课程：COMP5313/COMP4313 — Large Scale Networks, S1 2026 主题：理解 Hub and Authority 更新规则如何影响网页排名 依据教材 Networks, Crowds, and Markets 第 14 章

一、预备知识回顾

1.1 HITS 算法核心思想

Hubs and Authorities 算法将网页的重要性分为两个互补维度：

  • 权威（Authority）：内容上被认可为高质量信息来源的页面（如 Cornell 主页之于查询 "Cornell"）
  • 中枢（Hub）：本身不一定是权威，但指向许多权威页面的"列表型"页面（如"十大最佳新闻网站"）

两者是相互递归定义（Mutually Recursive Definition） 的：

"好的中枢指向许多好的权威；好的权威被许多好的中枢指向。"

1.2 更新规则（Update Rules）

每个页面 \(p\) 维护两个分数 \(\text{auth}(p)\) 和 \(\text{hub}(p)\)，初始值均为 \(1\)。

权威更新规则（Authority Update Rule）：

\[\text{auth}(p) \leftarrow \sum_{q \to p} \text{hub}(q)\]

即：页面 \(p\) 的权威分数 = 所有指向 \(p\) 的页面 \(q\) 的中枢分数之和。

中枢更新规则（Hub Update Rule）：

\[\text{hub}(p) \leftarrow \sum_{p \to q} \text{auth}(q)\]

即：页面 \(p\) 的中枢分数 = \(p\) 指向的所有页面 \(q\) 的权威分数之和。

1.3 k 步迭代与归一化

k 步 Hub-Authority 计算（k-step Hub-Authority Computation）：

  1. 初始化所有 \(\text{auth}(p) = \text{hub}(p) = 1\)
  2. 执行 \(k\) 轮迭代，每轮先后应用权威更新规则和中枢更新规则
  3. 最后进行归一化（Normalization）：每个权威分数除以所有权威分数之和；每个中枢分数除以所有中枢分数之和

二、练习 1：计算权威分数（Computing Authority Scores）

2.1 题目描述

在 Figure 1 的网页网络中，边如下： - \(C \to A\)，\(D \to A\)，\(E \to A\) - \(E \to B\)，\(F \to B\)

即：\(A\) 的入边来自 \(\{C, D, E\}\)；\(B\) 的入边来自 \(\{E, F\}\)；\(C, D, E, F\) 无入边。\(A, B\) 无出边。

要求执行 k = 2 步迭代，给出未归一化与归一化后的分数。

2.2 关键观察：哪些分数无需初始化

题目提示：不需要计算/初始化 \(\text{hub}(A), \text{hub}(B), \text{auth}(C), \text{auth}(D), \text{auth}(E), \text{auth}(F)\)。

原因分析： - \(A, B\) 没有出边 → 中枢更新规则下 \(\text{hub}(A) = \text{hub}(B) = \sum_{\text{出邻居}} \text{auth}(\cdot) = 0\)（空和） - \(C, D, E, F\) 没有入边 → 权威更新规则下 \(\text{auth}(X) = \sum_{\text{入邻居}} \text{hub}(\cdot) = 0\)

所以这些分数在一轮迭代后即变为 0，后续恒为 0，完全可以忽略。

2.3 初始化

\[\text{hub}(C) = \text{hub}(D) = \text{hub}(E) = \text{hub}(F) = 1\]

2.4 Round 1

（a）权威更新：

\[\text{auth}(A) = \text{hub}(C) + \text{hub}(D) + \text{hub}(E) = 1 + 1 + 1 = 3\]

\[\text{auth}(B) = \text{hub}(E) + \text{hub}(F) = 1 + 1 = 2\]

（b）中枢更新：

\[\text{hub}(C) = \text{auth}(A) = 3\]

\[\text{hub}(D) = \text{auth}(A) = 3\]

\[\text{hub}(E) = \text{auth}(A) + \text{auth}(B) = 3 + 2 = 5\]

\[\text{hub}(F) = \text{auth}(B) = 2\]

Round 1 结果： | 节点 | auth | hub | |------|------|-----| | A | 3 | — | | B | 2 | — | | C | — | 3 | | D | — | 3 | | E | — | 5 | | F | — | 2 |

2.5 Round 2

（a）权威更新：

\[\text{auth}(A) = \text{hub}(C) + \text{hub}(D) + \text{hub}(E) = 3 + 3 + 5 = 11\]

\[\text{auth}(B) = \text{hub}(E) + \text{hub}(F) = 5 + 2 = 7\]

（b）中枢更新：

\[\text{hub}(C) = \text{auth}(A) = 11\]

\[\text{hub}(D) = \text{auth}(A) = 11\]

\[\text{hub}(E) = \text{auth}(A) + \text{auth}(B) = 11 + 7 = 18\]

\[\text{hub}(F) = \text{auth}(B) = 7\]

Round 2 未归一化结果： | 节点 | auth | hub | |------|------|-----| | A | 11 | — | | B | 7 | — | | C | — | 11 | | D | — | 11 | | E | — | 18 | | F | — | 7 |

2.6 归一化

权威归一化： 分母 \(= \text{auth}(A) + \text{auth}(B) = 11 + 7 = 18\)

\[\widehat{\text{auth}}(A) = \frac{11}{18}, \quad \widehat{\text{auth}}(B) = \frac{7}{18}\]

中枢归一化： 分母 \(= \text{hub}(C) + \text{hub}(D) + \text{hub}(E) + \text{hub}(F) = 11 + 11 + 18 + 7 = 47\)

\[\widehat{\text{hub}}(C) = \widehat{\text{hub}}(D) = \frac{11}{47}, \quad \widehat{\text{hub}}(E) = \frac{18}{47}, \quad \widehat{\text{hub}}(F) = \frac{7}{47}\]

2.7 观察与结论

  • \(E\) 同时指向 \(A\) 和 \(B\) → \(E\) 是最强中枢（\(\frac{18}{47}\)）
  • \(A\) 有 3 个中枢指向（\(C, D, E\)）→ \(A\) 的权威分数 \(\frac{11}{18} > \frac{7}{18}\)
  • 每轮迭代后，\(A\) 与 \(B\) 的权威比例逐渐稳定（即向主特征向量（Principal Eigenvector） 收敛）

三、练习 2：创建网页（Creating Web Pages）

3.1 题目描述

目标：新建页面 \(X\)，尽可能获得高归一化权威分数。

策略：同时新建 \(Y\) 指向 \(X\)。问题是 \(Y\) 是否应同时指向其他强权威节点？

两种方案： 1. 方案 1：\(Y \to X\)，仅此一条出边 2. 方案 2：\(Y \to A\)，\(Y \to B\)，\(Y \to X\)

3.2 方案 1 的分析

新增节点和边：\(Y \to X\)。\(X\) 无出边。

需要初始化的中枢/权威：原网络的 \(\{C, D, E, F\}\) 和新加入的 \(Y\) → 共 5 个初始 hub = 1。

Round 1 权威更新：

  • \(\text{auth}(A) = 3\)（\(C, D, E\) 指入）
  • \(\text{auth}(B) = 2\)（\(E, F\) 指入）
  • \(\text{auth}(X) = \text{hub}(Y) = 1\)（仅 \(Y\) 指入）

Round 1 中枢更新：

  • \(\text{hub}(C) = \text{hub}(D) = 3\)
  • \(\text{hub}(E) = 5\)
  • \(\text{hub}(F) = 2\)
  • \(\text{hub}(Y) = \text{auth}(X) = 1\)

Round 2 权威更新：

  • \(\text{auth}(A) = 3 + 3 + 5 = 11\)
  • \(\text{auth}(B) = 5 + 2 = 7\)
  • \(\text{auth}(X) = \text{hub}(Y) = 1\)

Round 2 中枢更新：

  • \(\text{hub}(C) = \text{hub}(D) = 11\)
  • \(\text{hub}(E) = 18\)
  • \(\text{hub}(F) = 7\)
  • \(\text{hub}(Y) = \text{auth}(X) = 1\)

观察：\(Y\) 只指向 \(X\)，而 \(X\) 是一个新创建的孤立权威，权威分数永远 = \(\text{hub}(Y) = 1\)。\(Y\) 的中枢分数也永远 = \(\text{auth}(X) = 1\)。它们陷入"互相确认"的孤岛。

归一化： - 权威总和 = \(11 + 7 + 1 = 19\) - 中枢总和 = \(11 + 11 + 18 + 7 + 1 = 48\)

\[\widehat{\text{auth}}(X) = \frac{1}{19}, \quad \widehat{\text{hub}}(Y) = \frac{1}{48}\]

\[\widehat{\text{auth}}(A) = \frac{11}{19}, \quad \widehat{\text{auth}}(B) = \frac{7}{19}\]

结论：方案 1 下 \(X\) 的归一化权威分数仅为 \(\frac{1}{19} \approx 0.053\)。

3.3 方案 2 的分析

新增节点和边：\(Y \to A\)，\(Y \to B\)，\(Y \to X\)。\(X\) 无出边。

Round 1 权威更新：

  • \(\text{auth}(A) = \text{hub}(C) + \text{hub}(D) + \text{hub}(E) + \text{hub}(Y) = 1 + 1 + 1 + 1 = 4\)
  • \(\text{auth}(B) = \text{hub}(E) + \text{hub}(F) + \text{hub}(Y) = 1 + 1 + 1 = 3\)
  • \(\text{auth}(X) = \text{hub}(Y) = 1\)

Round 1 中枢更新：

  • \(\text{hub}(C) = \text{auth}(A) = 4\)
  • \(\text{hub}(D) = \text{auth}(A) = 4\)
  • \(\text{hub}(E) = \text{auth}(A) + \text{auth}(B) = 4 + 3 = 7\)
  • \(\text{hub}(F) = \text{auth}(B) = 3\)
  • \(\text{hub}(Y) = \text{auth}(A) + \text{auth}(B) + \text{auth}(X) = 4 + 3 + 1 = 8\)

Round 2 权威更新：

  • \(\text{auth}(A) = \text{hub}(C) + \text{hub}(D) + \text{hub}(E) + \text{hub}(Y) = 4 + 4 + 7 + 8 = 23\)
  • \(\text{auth}(B) = \text{hub}(E) + \text{hub}(F) + \text{hub}(Y) = 7 + 3 + 8 = 18\)
  • \(\text{auth}(X) = \text{hub}(Y) = 8\)

Round 2 中枢更新：

  • \(\text{hub}(C) = \text{auth}(A) = 23\)
  • \(\text{hub}(D) = \text{auth}(A) = 23\)
  • \(\text{hub}(E) = \text{auth}(A) + \text{auth}(B) = 23 + 18 = 41\)
  • \(\text{hub}(F) = \text{auth}(B) = 18\)
  • \(\text{hub}(Y) = \text{auth}(A) + \text{auth}(B) + \text{auth}(X) = 23 + 18 + 8 = 49\)

归一化： - 权威总和 = \(23 + 18 + 8 = 49\) - 中枢总和 = \(23 + 23 + 41 + 18 + 49 = 154\)

\[\widehat{\text{auth}}(A) = \frac{23}{49}, \quad \widehat{\text{auth}}(B) = \frac{18}{49}, \quad \widehat{\text{auth}}(X) = \frac{8}{49}\]

\[\widehat{\text{hub}}(C) = \widehat{\text{hub}}(D) = \frac{23}{154}, \quad \widehat{\text{hub}}(E) = \frac{41}{154}, \quad \widehat{\text{hub}}(F) = \frac{18}{154}, \quad \widehat{\text{hub}}(Y) = \frac{49}{154}\]

3.4 两方案对比

方案 \(\widehat{\text{auth}}(X)\) 解释
方案 1 \(\frac{1}{19} \approx 0.053\) \(Y\) 只指向 \(X\)，\(Y\) 本身被视为低质量中枢
方案 2 \(\frac{8}{49} \approx 0.163\) \(Y\) 同时指向 \(A, B\)，成为"高质量中枢"，再把自身权重传给 \(X\)

核心洞见（Core Insight）：

让推荐页面 \(Y\) 同时指向已有的强权威（如 \(A, B\)），会让 \(Y\) 获得高中枢分数；这个高中枢分数随后通过 \(Y \to X\) 的链接转化为 \(X\) 的高权威分数。

这揭示了 HITS 算法的一个关键特征：权威的提升不仅取决于被多少页面指向，更取决于指向者的中枢质量（Hub Quality）。

4.1 题目描述

创建 三个 新页面 \(X, Y, Z\)，通过设计 \(Y\) 和 \(Z\) 的出边（\(X\) 无出边），使得在 2 步 HITS 计算后，按权威分数排名，\(X\) 位列第二。

4.2 最优策略

策略设计： - \(Y \to A\)，\(Y \to X\) - \(Z \to A\)，\(Z \to X\) - \(X\) 无出边

即 \(Y\) 和 \(Z\) 都同时指向 \(A\)（最强权威）和 \(X\)。

图示（Figure 3 对应）： 

Y ---> X
Y ---> A
Z ---> X
Z ---> A
C ---> A
D ---> A
E ---> A
E ---> B
F ---> B

4.3 Round 1 详细计算

初始：\(\text{hub}(C) = \text{hub}(D) = \text{hub}(E) = \text{hub}(F) = \text{hub}(Y) = \text{hub}(Z) = 1\)

权威更新：

  • \(\text{auth}(A) = \text{hub}(C) + \text{hub}(D) + \text{hub}(E) + \text{hub}(Y) + \text{hub}(Z) = 1+1+1+1+1 = 5\)
  • \(\text{auth}(B) = \text{hub}(E) + \text{hub}(F) = 1+1 = 2\)
  • \(\text{auth}(X) = \text{hub}(Y) + \text{hub}(Z) = 1+1 = 2\)

中枢更新：

  • \(\text{hub}(C) = \text{auth}(A) = 5\)
  • \(\text{hub}(D) = \text{auth}(A) = 5\)
  • \(\text{hub}(E) = \text{auth}(A) + \text{auth}(B) = 5+2 = 7\)
  • \(\text{hub}(F) = \text{auth}(B) = 2\)
  • \(\text{hub}(Y) = \text{auth}(A) + \text{auth}(X) = 5+2 = 7\)
  • \(\text{hub}(Z) = \text{auth}(A) + \text{auth}(X) = 5+2 = 7\)

4.4 Round 2 详细计算

权威更新：

  • \(\text{auth}(A) = \text{hub}(C) + \text{hub}(D) + \text{hub}(E) + \text{hub}(Y) + \text{hub}(Z) = 5+5+7+7+7 = 31\)
  • \(\text{auth}(B) = \text{hub}(E) + \text{hub}(F) = 7+2 = 9\)
  • \(\text{auth}(X) = \text{hub}(Y) + \text{hub}(Z) = 7+7 = 14\)

4.5 排名验证

Round 2 权威分数（未归一化）：

节点 auth
A 31
X 14
B 9

排名：\(A > X > B\) ✓

\(X\) 成功位列第二，超越了原网络中的 \(B\)。

4.6 能否让 X 排第一？

结论：不可能。

证明（引理：\(\text{auth}(X) \le \text{hub}(Y) + \text{hub}(Z)\)）：

由于 \(X\) 只能通过 \(Y\) 和 \(Z\) 的链接获得权威（题目设 \(X\) 无出边、且新增节点只有 \(Y, Z, X\)），故 \[\text{auth}(X) = \text{hub}(Y) \cdot \mathbb{1}[Y \to X] + \text{hub}(Z) \cdot \mathbb{1}[Z \to X] \le \text{hub}(Y) + \text{hub}(Z)\]

情况分析：

情况 a：\(Y, Z\) 均不指向 \(A\) 和 \(B\) 则 \(\text{hub}(Y)\) 和 \(\text{hub}(Z)\) 只能通过指向 \(X\) 获得权威贡献，类似练习 2 的方案 1：\(\text{hub}(Y), \text{hub}(Z)\) 会停留在非常小的值（从 1 开始，只能通过 \(X \to\) 的路径回传，而 \(X\) 无出边），因此 \(\text{auth}(X)\) 微不足道。

情况 b：\(Y, Z\) 指向 \(A\) 此时 \(\text{hub}(Y) + \text{hub}(Z)\) 对 \(\text{auth}(A)\) 也有贡献，并且原网络中 \(\text{hub}(C) + \text{hub}(D) + \text{hub}(E)\) 也继续贡献 \(\text{auth}(A)\)。故： \[\text{auth}(A) \ge \text{hub}(Y) + \text{hub}(Z) + [\text{hub}(C) + \text{hub}(D) + \text{hub}(E)] \ge \text{auth}(X) + (\text{正值})\] 因此 \(\text{auth}(A) > \text{auth}(X)\)，\(X\) 必不可能超越 \(A\)。

情况 c：\(Y, Z\) 指向 \(B\) 对称地，\(\text{auth}(B) \ge \text{hub}(Y) + \text{hub}(Z) + [\text{hub}(E) + \text{hub}(F)]\)，\(X\) 不可能超越 \(B\)（至少在 \(Y, Z\) 都同时指向 \(B\) 和 \(X\) 时）。

综合三种情况：若 \(Y, Z\) 同时指向 \(A\) 和 \(X\)，则 \(X\) 最多排第二（低于 \(A\)）；若指向 \(B\) 和 \(X\)，则 \(X\) 最多排第二（低于 \(B\)）。无论如何，\(X\) 最多排第二。

4.7 核心启示

  • 对抗 HITS 的难点：算法的相互递归结构使得"伪造中枢"和"伪造权威"之间存在内在张力
  • 理论上的上界：\(X\) 的权威分数受到 \(\text{hub}(Y) + \text{hub}(Z)\) 的限制；而要提升 \(\text{hub}(Y) + \text{hub}(Z)\)，必须让它们指向 \(A\) 或 \(B\)，这同时也提升了 \(A\) 或 \(B\) 的权威分数
  • 与 PageRank 的对比：PageRank 通过出度均分权重的机制（一页的 PageRank 被等分给所有出链），让"稀释"防御垃圾链接农场；HITS 则通过双重推导的自洽性实现防御

五、综合总结

5.1 关键公式回顾

规则 公式
权威更新 \(\text{auth}(p) \leftarrow \sum_{q \to p} \text{hub}(q)\)
中枢更新 \(\text{hub}(p) \leftarrow \sum_{p \to q} \text{auth}(q)\)
权威归一化 \(\widehat{\text{auth}}(p) = \text{auth}(p) / \sum_q \text{auth}(q)\)
中枢归一化 \(\widehat{\text{hub}}(p) = \text{hub}(p) / \sum_q \text{hub}(q)\)

5.2 练习经验教训

  1. 计算简化技巧：无出边节点的中枢分数恒为 0；无入边节点的权威分数恒为 0。可在计算前剔除，减少工作量
  2. 相互递归是核心：中枢分数通过指向权威页面获得；权威分数通过被中枢指向获得
  3. 操纵 HITS 的策略：新节点若想获得高权威，应让其推荐页同时指向已有强权威以提升推荐页的中枢质量
  4. 算法的局限：HITS 存在被一定程度操纵的可能性，但其双重递归结构限制了单纯创建少数页面能获得的权威等级

5.3 与课程其他章节的联系

  • 第 14.2 节（教材）：HITS 算法的基础理论来源
  • PageRank（第 14.3 节）：另一种链接分析方法，采用"流体"模型而非双重递归
  • SEO 与游戏论（第 14.4 节）：搜索引擎与网站作者之间的博弈——本练习就是一个微型 SEO 攻防案例

六、术语表

中文术语 English Term 简要说明
权威 Authority 被认可的高质量信息来源页面
中枢 Hub 指向许多权威的"列表型"页面
权威更新规则 Authority Update Rule \(\text{auth}(p) \leftarrow \sum_{q \to p} \text{hub}(q)\)
中枢更新规则 Hub Update Rule \(\text{hub}(p) \leftarrow \sum_{p \to q} \text{auth}(q)\)
k 步 Hub-Authority 计算 k-step Hub-Authority Computation 执行 k 轮交替更新后归一化
归一化 Normalization 除以分数总和使分数和为 1
相互递归定义 Mutually Recursive Definition 两量彼此依对方定义
主特征向量 Principal Eigenvector 对应最大特征值的特征向量，HITS 极限状态
搜索引擎优化 Search Engine Optimization (SEO) 提升页面搜索排名的技术
孤立权威 Isolated Authority 仅被一小群节点互指的孤岛权威
权威上界引理 Authority Upper Bound Lemma \(\text{auth}(X) \le \sum_{Y \to X} \text{hub}(Y)\)

文档版本：2026-04-16 对应教材：Easley & Kleinberg, Networks, Crowds, and Markets, 第 14 章