PageRank算法及变体演进

可视化演示

链接投票思想

美食城里的每家店都有一块推荐板，顾客吃完后可以把店名写在上面。如果只看谁被写到的次数最多，一家店可能雇人刷屏就冲上榜首。PageRank 想解决的，正是这种“只看票数、不看投票人”的问题。在 PageRank 的世界里，每个网页都是一家店，网页之间的超链接就是一张写出去的推荐票。指向某个网页的链接越多，说明它的口碑越广。

从直觉出发，最简单的排名就是统计入链数量：

其中 $B_u$ 是所有指向网页 $u$ 的页面集合。这相当于“谁收到的推荐最多，谁就最有人气”。

不过，仅数推荐笔迹很容易被垃圾链接刷出来。真正的口碑不是“谁写得多”，而是“谁写的更有分量”。所以 PageRank 用了更聪明的递归思想：你的价值，由推荐你的人的价值共同决定。

随机游走模型

顾客在美食城并不会看完整张地图才决定去下一家，更多时候是顺着刚吃完饭的店家推荐，随机走向下一家。把这种“随机乱逛”重复无数次，哪家店被踏访的次数多，哪家店就人气高。PageRank 的发明人布林和佩奇正是这样想象用户在网页上的浏览行为——这就是随机游走模型。

如果当前在页面 $v$，它一共链接到 $N_v$ 个页面，那么用户点击其中某个页面 $u$ 的概率就是 $1/N_v$。这相当于把 $v$ 的推荐信均匀地抄送给了所有被链接的页面：

这里的 $P(v \to u)$ 是“从 $v$ 一步跳到 $u$”的转移概率。

随机游走者长期停留在各页面的比例，就是 PageRank 分数。这也是为什么 PageRank 可以被理解为图上的一种“稳态分布”：逛得越久，越常待的店，排名越高。

原始公式推导

美食家的推荐信不能只看一次，因为推荐者本身也在被别人推荐；每家店的推荐价值都与其他店纠缠在一起。PageRank 用迭代的方法破解这种“鸡生蛋、蛋生鸡”：先给每家店一个相同初始分，然后不断按推荐关系重新分配，直到分数稳定。

当一个页面 $v$ 指向另一个页面 $u$ 时，$v$ 会把自己当前的得分平均分成 $N_v$ 份，其中一份送给 $u$。网页 $u$ 的总分就是所有送来的份额之和：

这里的 $B_u$ 是所有指向 $u$ 的页面集合。

需要提醒的是，这个原始版本还没有阻尼因子，后文会看到它在真实网络上很容易出现收敛问题。

阻尼因子作用

真实顾客不会永远顺着推荐链走下去。他们可能突然想起想吃的麻辣烫，直接打开另一家店的页面。PageRank 把这种“跳出”建模为阻尼因子 $d$：以概率 $d$ 继续点链接，以概率 $1-d$ 随机跳到任意一家店。这样既保留了链接推荐的主线，又给整个系统注入外部流动性。

引入阻尼因子后的迭代公式是：

其中 $N$ 是全网页面总数，$d$ 通常取 0.85。

如果没有这种“跳出”，某些互相抬分的小圈子会不断累积分数，导致排名失衡。阻尼因子相当于给口碑系统安装了“通风口”，让流量不会被局部小团体垄断。

死胡同与修正

美食城里总有一些店从来不写推荐信，只默默收下别人的推荐。放在随机游走里，顾客一旦走进这种“没有出链”的页面，就像进了死胡同，再也没法继续点链接，排名分数会不断沉积在这里。这种页面叫做死胡同或悬挂节点，是每个 PageRank 初学者都会遇到的坑。

为了解决泄漏，Google 的做法是把死胡同收集到的分数统一拿出来，再平均分给所有页面。修正后的迭代式可以写成：

其中 $\text{leak}$ 是所有死胡同页面得分之和。

死胡同的修正让总分数始终守恒，迭代才能稳定收敛。没有这一步，排名分数会像漏水的水池一样越来越少。

个性化变体

如果你是素食主义者，走进美食城时并不会参考肉食老饕的推荐，而会从自己常去的素食店出发，沿着“气味相投”的推荐链探索。Personalized PageRank（个性化 PageRank）正是把全局排名里的“均匀随机跳转”，换成“按你的偏好跳转”。

设 $s(u)$ 表示你对页面 $u$ 的先验偏好，且所有 $s(u)$ 之和为 1。替代阻尼公式中的均匀项，就能得到个性化 PageRank 的迭代式：

其中 $\alpha$ 是重启概率，常用取值与 $1-d$ 类似，约 0.15。

当 $s$ 取均匀分布时，个性化 PageRank 退化为带阻尼的全局 PageRank；当 $s$ 按主题构造时就是主题敏感搜索；当 $s$ 来自可信种子网站时就是 TrustRank；在推荐系统里，这种方法也叫带重启的随机游走（RWR）。变体的核心是改变“按什么偏好进行随机跳转”，而传播逻辑本身不变。

应用场景

美食城口碑模型的适用范围远超餐厅：只要有一张“谁指向谁”的有向图，PageRank 就能回答“哪个节点更重要”。这也解释了为什么一个搜索引擎时代诞生的算法，今天依然活跃在各类图分析任务中。

在搜索引擎中，PageRank 曾经是谷歌排序的核心信号之一，帮助用户从内容农场中筛选出权威页面。在社交网络中，研究者用 Personalized PageRank 从少量可信种子出发计算影响力，找出真正的意见领袖。在推荐系统中，用户和商品可以构成一张二部图，带重启的随机游走能计算任意用户与商品之间的多跳相关性，为“猜你喜欢”提供召回候选。

这类应用共同点是：把具体业务关系抽象成图，再把 PageRank 或它的变体当作图上的相关性度量。只要某个场景能表示为“节点 + 边”，美食城的口碑传播逻辑就能迁移过去。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""从零实现 PageRank 迭代计算"""  def page_rank(graph, damping=0.85, max_iter=100, tol=1e-6):    pages = list(graph.keys())    n = len(pages)    index = {p: i for i, p in enumerate(pages)}    rank = [1.0 / n for _ in pages]    out_degree = {p: len(graph[p]) for p in pages}     for _ in range(max_iter):        new_rank = [(1.0 - damping) / n for _ in pages]        leak = sum(rank[index[p]] for p in pages if out_degree[p] == 0)         for p in pages:            if out_degree[p] == 0:                continue            share = rank[index[p]] / out_degree[p]            for q in graph[p]:                new_rank[index[q]] += damping * share         # 把死胡同泄漏的分数平均分给所有页面        for i in range(n):            new_rank[i] += damping * leak / n         diff = sum(abs(new_rank[i] - rank[i]) for i in range(n))        rank = new_rank        if diff < tol:            break     return {p: rank[index[p]] for p in pages}  if __name__ == "__main__":    web = {        "A": ["B", "C"],        "B": ["C"],        "C": ["A"],        "D": ["C", "E"],        "E": ["D"],    }    result = page_rank(web)    for page, score in sorted(result.items(), key=lambda x: -x[1]):        print("{}: {:.4f}".format(page, score))

1. rank = [1.0 / n for _ in pages]初始化每个网页得分相等，保证所有分数总和为 1。
2. leak = sum(rank[index[p]] for p in pages if out_degree[p] == 0)计算死胡同页面攒下的分数，后面会分给全网。
3. share = rank[index[p]] / out_degree[p]把页面 p 的得分按出链数均匀分给每个被链接页面。
4. new_rank[index[q]] += damping * share只有 d 比例的分数通过链接传播，剩下的留给随机跳转。
5. new_rank[i] += damping * leak / n把死胡同泄漏的分数重新平均分配到每个页面。
6. if diff < tol: break当两轮之间的变化足够小，就认为 PageRank 已经收敛。
7. result = page_rank(web)传入网页链接字典，返回每个页面的最终得分。

常见误区

面试题