COMP5313 Lecture 06 Summary - PageRank and Its Generalizations

Lecture 06 — PageRank and Its Generalizations

主题

这节在 HITS 之后继续讨论信息网络中的重要性排序，重点是： - PageRank - scaled PageRank - personalized PageRank

1. PageRank 的核心思想

PageRank 把链接看成“投票”，但不是所有票都一样。

来自重要页面的链接，票更重。

所以一个页面重要，当且仅当： - 很多页面指向它 - 尤其是很多重要页面指向它

2. 基本流量模型

若页面 的分数为 ，出度为 ，那么它会把自己的分数平均分给所有 outgoing links。

因此页面 的分数满足：

这就是 PageRank 的递归定义。

3. 为什么不能直接暴力解

大规模 Web 图非常大，直接高斯消元太贵，所以通常用迭代法： - 先初始化分数 - 不断更新 - 直到收敛

4. Random walk 解释

PageRank 可以理解为随机游走者： - 当前在某个页面 - 随机沿 outgoing link 走到下一页 - 长期稳定后，落在某个页面上的概率就是它的 PageRank

5. Scaled PageRank / damping

真实 Web 中会有 dead end / spider trap 等问题，所以需要 teleportation。

典型形式是：

其中： - 是 damping factor - 对应随机跳转

作用

• 保证收敛性
• 避免被局部结构困住
• 使排名更稳定

6. Personalized PageRank

uniform teleportation 可以改成偏向某个主题/用户/种子集合。

这样就能得到： - topic-sensitive ranking - user-specific ranking - recommendation style ranking

7. HITS vs PageRank

HITS

• 两个角色：hub 和 authority
• 更强调局部 query-dependent 结构

PageRank

• 单一重要性分数
• 更适合全局排序
• 重要页面会把权重传给别的重要页面

8. 课程里要掌握的重点

• 会写 PageRank 基本更新式
• 理解它的 random walk 含义
• 知道为什么需要 damping
• 能区分 HITS 与 PageRank 的思想差异

takeaway

PageRank 的本质是：重要性在图上流动，并在长期随机游走中沉淀到真正“被重要节点支持”的页面上。