COMP5313 Week 06 PageRank 讲课总结
COMP5313 Week 06 讲课总结：PageRank
本讲开头有期中相关说明，已不整理。optional / generalized PageRank 细节也不整理。
1. 本讲主题
老师从 HITS 过渡到 PageRank：
- HITS 有 hub / authority 两个分数。
- PageRank 每个页面只有一个重要性分数。
- PageRank 的核心是 endorsement 通过链接在页面之间传递。
Basic PageRank 是理论基础，实际使用的是 Scaled PageRank。
2. Basic PageRank
核心规则：
每个节点把自己的 PageRank 平均分给所有出链目标。
对节点 \(i\)：
[ v'i={ji} ]
其中 \(d_j^{out}\) 是节点 \(j\) 的出度。
矩阵形式：
[ '=M ]
\(M\) 是列随机矩阵，每一列和为 1。
3. Equilibrium / 固定点
PageRank 的 equilibrium 是更新后不变的概率分布。
Basic PageRank：
[ =M,_i v_i=1 ]
这里 \(\sum_i v_i=1\) 表示 PageRank 向量要归一化成概率分布。
老师讲小图时，常见做法是：
- 对每个节点写入链方程。
- 加上 \(\sum_i v_i=1\)。
- 解线性方程组。
4. Dead End
Dead end 是无出链节点。
问题：
- 如果节点没有出链，它的 PageRank 无处传递。
- 总 PageRank 质量会泄漏。
老师采用的处理：
- 给 dead end 加 self-loop。
- 也就是它把 PageRank 传给自己。
5. Spider Trap
Spider trap 是一组节点：
- 可以从外部进入。
- 进去后出不来。
Basic PageRank 会把分数逐渐积累到 trap 内，外部节点趋近 0。
这是为什么实际使用必须引入 scaled PageRank。
6. 收敛问题
Basic PageRank 即使有 equilibrium，迭代过程也可能振荡。
老师强调：
- 强连通有向图保证 unique equilibrium。
- 但如果图有周期结构，迭代可能不收敛。
- 无向连通非二部图时，Basic PR 会收敛。
无向图的 Basic PageRank equilibrium：
[ v_i= ]
即 PageRank 与节点度数成正比。
7. Scaled PageRank
Scaled PageRank 的更新公式：
[ v'_i=(M)_i+ ]
equilibrium：
[ =M+,_i v_i=1 ]
含义：
- 先按 Basic PageRank 更新。
- 再乘以 \(\alpha\)。
- 剩余 \(1-\alpha\) 平均分给所有节点。
- \(n\) 是节点总数。
- 常用 \(\alpha=0.85\)。
做题时可以把 Basic 里的 \(M\mathbf{v}\) 替换成：
[ M+ ]
8. Random Surfer 解释
Scaled PageRank 对应随机冲浪模型：
- 以概率 \(\alpha\) 沿当前页面随机出链走。
- 以概率 \(1-\alpha\) 随机跳到任意页面。
长期停留在某个页面的比例，就是该页面的 scaled PageRank。
这个 teleport 机制解决：
- dead end。
- spider trap。
- 非强连通导致的流量困住。
- 周期振荡。
9. Personalized PageRank
Personalized PageRank 和 scaled PageRank 的区别只在 teleport distribution。
Scaled PageRank：
[ = ]
Personalized PageRank：
[ =M+(1-) ]
\(\mathbf{s}\) 可以集中在某个目标节点或目标集合上。
用途：
- 衡量相对于某个节点 / 用户 / 主题的相关性。
- 比最短路径更细，因为同距离节点也能有不同 PPR 分数。
10. 考点重点
- 会区分 HITS 和 PageRank。
- 会写 Basic PageRank 更新式和 equilibrium 条件。
- 必须记住 \(\sum_i v_i=1\)。
- 知道 \(n\) 是节点总数。
- 会处理 dead end：加 self-loop。
- 会解释 spider trap。
- 会写 Scaled PageRank 公式，并知道 \(\alpha\) 常用 0.85。
- 会用 random surfer 解释 teleport。
- 会写 Personalized PageRank 公式，知道它只改变 teleport distribution。