COMP5313 Lecture 05 Summary - The Web, Hubs and Authorities

Posted on In , , Word count in article: 403 Reading time ≈ 1 mins.

Lecture 05 — The Structure of the Web, Hubs and Authorities

主题

这节从 social network 转到 information network，重点讲： - Web graph - bow-tie structure - hubs and authorities (HITS)

1. Web 是什么图

Web 可以看成一个 directed graph： - 节点：网页 - 有向边：超链接

与社交网络不同，信息网络强调“引用/推荐/指向”的方向性。

2. Bow-tie structure of the Web

Web 宏观上常呈 bow-tie 结构，包括： - SCC（强连通核心） - IN - OUT - tendrils / tubes - disconnected parts

直觉

不是所有网页都互相可达，而是形成一个中心核心，外面还有只进不出、只出不进等区域。

3. Hubs and Authorities

HITS 的思想是把节点分成两种角色：

Authority

被很多高质量 hub 指向的页面。

Hub

指向很多高质量 authority 的页面。

4. 递归定义

  • 一个好 hub 指向很多好 authority
  • 一个好 authority 被很多好 hub 指向

所以 hub 和 authority 是互相强化的。

5. 矩阵视角

设邻接矩阵为 ： - authority 分数与 有关 - hub 分数与 有关

进一步可得： - authority 对应 的主特征向量 - hub 对应 的主特征向量

6. 为什么 HITS 有意义

有些页面本身不是最终权威内容，但它们是优质导航页。

例如： - 课程资源导航页是 hub - 被它指向的官方内容页是 authority

7. 应用

不仅适用于 Web，也适用于： - citation network - recommendation / expert finding - knowledge network

takeaway

HITS 的核心不是“谁最重要”这一个分数，而是把重要性拆成两种角色：会指路的 hub，和值得被指向的 authority。