PageRank：经典图排序算法的理论与实践

FreeGuideOnline 最新 2026-06-14

PageRank：经典图排序算法的理论与实践

什么是 PageRank？

PageRank 是由 Google 创始人拉里·佩奇和谢尔盖·布林在 1998 年提出的一种对图节点进行重要性排序的算法。最初用于对网页搜索结果进行排序，如今已成为图分析、推荐系统、社交网络影响力评估等领域的基础工具。它的核心思想非常直观：一个页面如果被许多其他重要页面链接，那么它本身也是重要的。

作为经典图算法，理解 PageRank 不仅能帮助你掌握网页排序的底层逻辑，还能为你解锁大量基于图结构的实际应用场景。

图论基础：把网页看作图

在 PageRank 的视角下，整个互联网就是一个有向图（Directed Graph）：

  • 节点（Vertex）：每个网页。
  • 边（Edge）：网页之间的超链接，方向从源页面指向目标页面。

对于节点 A，我们关心两个属性：

  • 出度（Out-degree）：从 A 指向其他节点的链接数量。
  • 入度（In-degree）：从其他节点指向 A 的链接数量。

一个真实的网页图非常稀疏，但 PageRank 的数学建模不受图规模直接影响，只依赖图的邻接结构。为了理解算法，我们先从一个只有 4 个页面的小例子入手。

PageRank 的核心思想：链接投票模型

PageRank 可以被形象地理解为一个“民主投票”系统：

  • 页面 A 向页面 B 添加一个链接，相当于 A 把一部分自身的重要性“投票”给了 B。
  • 每个页面的总票数（重要性）会被均分给所有它链接出去的页面：如果 A 有 n 个出链，则每个被链接的页面得到 A 重要性的 1/n。

但这种简单传递存在两个问题：

  1. 排名沉没（Rank Sink）：多个页面互相链接形成一个闭环，从外部获得的票数无法流出，导致这些页面重要性虚高。
  2. 孤立页面：没有出链的页面（称为“悬挂节点”）会让传递路线中断。

为了解决这些问题，PageRank 引入了阻尼因子（Damping Factor）和随机跳转模型。

随机游走与数学公式

PageRank 基于一个叫做随机冲浪者模型的假设：一个用户随机点击链接浏览网页，偶尔会感到无聊，直接跳转到一个完全随机的页面。这样，任何一个页面的重要性都由两部分组成：

  • 链接传递过来的重要性（从其他页面平均分配得到）
  • 随机跳转带来的基础重要性（一个极小的均分值）

设图中共有 N 个节点，PR(i) 表示节点 i 的 PageRank 值，d 为阻尼因子（通常取 0.85），则 PageRank 的迭代公式为：

PR(i) = (1 - d) / N  +  d * Σ ( PR(j) / out(j) )

其中，求和符号 Σ 遍历所有指向 i 的节点 j，out(j) 是节点 j 的出度。若 j 的出度为 0（悬挂节点），通常会对所有节点均分其 PR 值，或者添加虚拟外链指向所有节点。

迭代过程初始化时，通常设所有节点的 PR = 1/N，然后反复计算上式直至收敛（PR 值的变化小于某个极小阈值，如 1e-6）。

算法实现：迭代计算步骤

  1. 构建邻接矩阵或转移矩阵 M：
    如果节点 j 有 k 条出边，则从 j 到每个被指向节点 i 的转移概率为 1/k，否则为 0。悬挂节点对应的列全为 1/N。
  2. 初始化 PR 向量：长度为 N，每个元素为 1/N。
  3. 迭代更新： 
    new_PR = (1-d)/N * 1_vector  +  d * M * old_PR
    其中 1_vector 是全 1 列向量。
  4. 检查收敛：计算 new_PR 与 old_PR 的 L1 范数（差的绝对值之和）是否小于阈值。
  5. 满足阈值后输出最终的 PageRank 向量。

伪代码：

N = 节点数量
d = 0.85
threshold = 1e-6
PR = [1/N] * N
while True:
    new_PR = [ (1-d)/N ] * N
    for 每条边 (j -> i):
        new_PR[i] += d * PR[j] / out[j]
    if sum(|new_PR - PR|) < threshold:
        break
    PR = new_PR
返回 PR

实例演练：一个小型图的 PageRank 计算

考虑下图结构：

  • 节点 A 链接到 B 和 C
  • 节点 B 链接到 C
  • 节点 C 链接到 A
  • 节点 D 链接到 C

用有向边表示：A→B, A→C, B→C, C→A, D→C。

出度计数：

  • A: 2 (指向 B,C)
  • B: 1 (指向 C)
  • C: 1 (指向 A)
  • D: 1 (指向 C)

总节点数 N=4，取 d=0.85。初始 PR = [0.25, 0.25, 0.25, 0.25]。

第 1 次迭代：

  • PR(A) = (1-0.85)/4 + 0.85 * (来自 C 的票，C 出度为 1) = 0.0375 + 0.85 * PR(C)/1 代入初始值：0.0375 + 0.85 * 0.25 = 0.25
  • PR(B) = 0.0375 + 0.85 * (来自 A 的票，A 出度为 2) = 0.0375 + 0.85 * 0.25/2 ≈ 0.14375
  • PR(C) = 0.0375 + 0.85 * (来自 A 的票 + 来自 B 的票 + 来自 D 的票) A→C: 0.25/2 = 0.125；B→C: 0.25/1 = 0.25；D→C: 0.25/1 = 0.25；合计 0.625 所以 PR(C) = 0.0375 + 0.85*0.625 = 0.56875
  • PR(D) = 0.0375 + 0（没有页面指向 D）= 0.0375

第一次迭代后：PR = [0.25, 0.14375, 0.56875, 0.0375]
继续迭代若干次后，数值会稳定在接近最终结果：A 约 0.324, B 约 0.142, C 约 0.382, D 约 0.15（具体值依赖于悬挂节点处理，此处 D 无出链，实际计算中需将其 PR 均分给所有节点，该调整使 D 有贡献）。

阻尼因子的作用与悬挂节点处理

阻尼因子 d（通常 0.85）控制着链接结构与均匀分布之间的权衡。若 d=1，则完全信任链接传递，会导致排名沉没问题；若 d=0，则所有页面得到完全相同的 1/N，排序失去意义。0.85 在实践中平衡了两者，确保随机跳转能“修复”非连通图带来的问题。

悬挂节点（出度为 0）必须特殊处理，否则它们的 PR 会凭空消失，无法传递。常见方法有两种：

  • 假设悬挂节点有指向所有节点的链接，即转移矩阵中该节点对应的列全设为 1/N。
  • 在迭代时，先计算全体 PR 的总和，缺失的部分按比例补回每个节点。

现在主流的实现（如 Google 原始文献）采用第一种方法，称之为“随机跳转矩阵调整”。

代码实战：Python 实现 PageRank

下面展示一个简洁且功能完备的 PageRank 计算函数，使用稀疏矩阵可扩展至更大图。

def pagerank(graph, d=0.85, max_iter=100, tol=1e-6):
    """
    graph: 邻接字典，key 为节点，value 为出链列表
    返回：字典 {节点: PageRank值}
    """
    nodes = list(graph.keys())
    N = len(nodes)
    # 节点索引映射
    idx = {node: i for i, node in enumerate(nodes)}
    
    # 初始化 PR
    pr = np.ones(N) / N
    
    # 出度数组
    out_degree = np.array([len(graph[node]) for node in nodes], dtype=float)
    # 处理悬挂节点：假设指向所有节点
    dangling = (out_degree == 0)
    
    # 构建稀疏转移矩阵（压缩稀疏行）
    row_ind = []
    col_ind = []
    data = []
    for j, node in enumerate(nodes):
        if out_degree[j] == 0:
            # 悬挂节点：均匀分布
            for i in range(N):
                row_ind.append(i)
                col_ind.append(j)
                data.append(1.0 / N)
        else:
            for target in graph[node]:
                i = idx[target]
                row_ind.append(i)
                col_ind.append(j)
                data.append(1.0 / out_degree[j])
    M = csr_matrix((data, (row_ind, col_ind)), shape=(N, N))
    
    damping_vec = np.ones(N) * ((1 - d) / N)
    
    for _ in range(max_iter):
        new_pr = damping_vec + d * M.dot(pr)
        if np.sum(np.abs(new_pr - pr)) < tol:
            break
        pr = new_pr
    
    return {node: pr[idx[node]] for node in nodes}

使用示例：

graph = {
    'A': ['B', 'C'],
    'B': ['C'],
    'C': ['A'],
    'D': ['C']
}
result = pagerank(graph)
print(result)  # 近似值 {'A': 0.324, 'B': 0.142, 'C': 0.382, 'D': 0.152}

个性化 PageRank 与变体

标准 PageRank 给出全局重要性排序，但很多场景下我们需要基于特定兴趣或节点的相对重要性。

  • 个性化 PageRank（Personalized PageRank）：将随机跳转向量从均匀分布 (1-d)/N 替换为一个偏向于某个（或某些）节点的个性化向量。例如，若用户喜欢体育类页面，则跳转概率在体育种子节点上更高，其他页面为 0。这样计算结果表示“相对于该用户”的页面重要性。
  • 主题敏感 PageRank（Topic-Sensitive PageRank）：预先为多个主题离线计算各自的主题向量，线上根据用户查询的主题类别进行加权组合。

这两种变体在推荐系统中被广泛使用，例如在 Pinterest 的图推荐、社交网络的好友推荐中均有成功实践。

应用场景一览

PageRank 早已超越网页排序，成为图数据中节点权威性评估的通用框架：

  1. 搜索引擎：对查询匹配的网页进行排序（结合其他数百个信号）。
  2. 学术论文影响力分析：将引用网络看作有向图，PageRank 可衡量论文的权威程度。
  3. 社交网络意见领袖挖掘：在 Twitter 关注关系图上，PageRank 值高的用户代表其信息传播影响力大。
  4. 推荐系统：在用户-物品交互图上，通过双部图扩展的 PageRank 计算物品相对排名。
  5. 文本摘要：以句子为节点，相似度为边构建图，用 PageRank 提取关键句（如 TextRank 算法）。
  6. 生物信息学：蛋白质相互作用网络中的关键蛋白识别。

总结与深入学习的建议

PageRank 巧妙地将图结构转化为稳定、可收敛的节点分值，其背后的随机过程和马尔可夫链稳态思想，是理解众多图算法的基石。学习时，建议亲手复现迭代计算过程，并尝试调整阻尼因子观察收敛速度的变化。对于大规模图，由于转移矩阵极度稀疏，实际应用通常采用分布式计算框架（如 Pregel、Spark GraphX）以避免内存瓶颈。

掌握 PageRank 后，你可以继续探索：

  • HITS 算法（Hub/Authority 模型）
  • TextRank（自然语言处理中的无监督关键词提取）
  • 图神经网络（GNN） 中基于随机游走的嵌入方法（如 DeepWalk）

这些内容都以 PageRank 的思维为基础进行扩展，理解本源将使你的图算法学习之路更加顺畅。