COMP5313 Week 05 Web 结构与 HITS 讲课总结
COMP5313 Week 05 讲课总结：Web Structure 与 HITS
1. 本讲主题
本讲进入信息网络和链接分析。老师主要讲：
- Web graph 和 citation network。
- 有向图中的路径与强连通分量。
- Web 的 bow-tie structure。
- HITS 算法的 hub-authority 思想。
谱分析相关推导属于 advanced / optional，不作为重点整理。
2. 信息网络
信息网络中，边通常表示“引用”“指向”或“推荐”。
两个典型例子：
- Web graph：网页是节点，超链接是有向边。
- Citation network：论文是节点，引用关系是有向边。
区别：
- Web link 可以更新和修改。
- Citation link 有时间方向，一篇论文通常只能引用过去的论文。
3. 有向图基础
有向图中路径必须沿边方向走。
Strongly Connected Component, SCC：
- 在一个 SCC 内，任意两个节点互相可达。
- SCC 是 maximal 的。
- 每个节点恰好属于一个 SCC。
SCC 是理解 Web bow-tie structure 和 PageRank trap 的基础。
4. Web 的 Bow-Tie Structure
老师讲了 Broder et al. 对 Web graph 的经典观察：
- Giant SCC：核心区域，任意两点互达。
- IN：可以到达 SCC，但 SCC 回不到它们。
- OUT：SCC 可以到达，但它们回不到 SCC。
- Tendrils / Tubes：从 IN 或 OUT 延伸出来，但不进入核心路径。
- Disconnected：与核心结构无关的部分。
这个结构说明 Web 不是一个简单的强连通图，而是有明显方向性和层次结构。
5. HITS 的核心思想
HITS 把页面分成两种角色：
- Authority：被很多好 hub 指向的页面。
- Hub：指向很多好 authority 的页面。
递归定义：
- 好 authority 被好 hub 指向。
- 好 hub 指向好 authority。
它适合处理搜索结果中的 prominent pages，尤其是好的 authority 之间不直接互相链接时。
6. HITS 更新规则
Authority 更新：
[ (p)=_{qp}(q) ]
Hub 更新：
[ (p)=_{pq}(q) ]
算法流程：
- 初始化所有 hub 和 authority 分数为 1。
- 交替执行 authority update 和 hub update。
- 每轮后归一化，防止数值无限增大。
- 迭代若干轮后得到排名。
7. 矩阵形式
设邻接矩阵为 \(A\)：
[ =A^T ]
[ =A ]
合并后：
[ ^{(k)}(AAT)k^{(0)} ]
Authority 类似对应 \(A^TA\)。
考试通常更重视更新规则和手算，不需要深入谱分解证明。
8. HITS 与 PageRank 的区别
HITS：
- 每个页面有两个分数：hub 和 authority。
- 原始 HITS 是 query-dependent，针对查询结果子图运行。
- 不需要 teleport。
PageRank：
- 每个页面只有一个全局重要性分数。
- 通过链接传递重要性。
- 后面 scaled PageRank 用 teleport 解决 trap 和收敛问题。
9. 考点重点
- 会解释 Web graph / citation network 的有向边含义。
- 会定义 SCC，并知道有向图路径必须沿方向。
- 会画出 Web bow-tie 的 SCC、IN、OUT、tendrils。
- 会解释 hub 与 authority 的递归关系。
- 必会 HITS 两条更新公式。
- 会按轮手算 HITS，并做归一化。
- 会区分 HITS 和 PageRank：两个分数 vs 一个分数，query-dependent vs global。