Skip to content
返回搜索结果

PageRank Centrality

提出者
Page, Brin, Motwani & Winograd
年份
1999
类型
Iterative link-based centrality algorithm
类别
Centrality

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

PageRank 是一种基于链接的中心性算法,通过衡量有多少高质量节点指向它来为有向图中的每个节点分配重要性得分。该算法由拉里·佩奇(Larry Page)、谢尔盖·布林(Sergey Brin)、拉吉夫·莫特瓦尼(Rajeev Motwani)和特里·温诺格拉德(Terry Winograd)于 1999 年在斯坦福大学提出,它成为了 Google 搜索引擎的数学基础,并且仍然是网络科学和信息检索领域最具影响力的算法之一。

方法背后的直觉

设想一位随机网络冲浪者,他随机点击链接,偶尔会跳转到一个完全随机的页面,而不是继续沿着链接前进。在无限次点击后,这位冲浪者在每个页面上花费的时间比例就是该页面的 PageRank。一个经常被访问的页面——因为许多热门页面链接到它——会获得高分。阻尼因子(通常为 0.85)模拟了继续点击而不是跳转的概率。

历史学

PageRank 由拉里·佩奇(Larry Page)和谢尔盖·布林(Sergey Brin)在斯坦福大学开发,作为他们 BackRub 搜索项目的核心排名机制,该项目于 1998 年成为 Google。该算法的奠基性技术报告与拉吉夫·莫特瓦尼(Rajeev Motwani)和特里·温诺格拉德(Terry Winograd)合著,于 1999 年发表。该算法推广了基于特征向量的中心性在大规模有向网络中的应用,并直接启发了包括 HITS 和 TrustRank 在内的后续链接分析算法。

何时使用

当您需要根据全局结构重要性对有向图中的节点进行排名时,PageRank 是合适的,特别是当边的方向编码了认可或影响力(超链接、引用、社交关注)时。它假设图可以被建模为马尔可夫链,并且需要一个连通或强连通分量才能干净地收敛。它不太适用于无向网络,在这些网络中,HITS 或介数中心性可能更受青睐,并且它可能对链接垃圾邮件或人为夸大的入度敏感。

局限与注意事项

  • 需要有向图;应用于无向网络需要选择约定
  • 收敛速度取决于转移矩阵的谱隙,对于连接不佳的图可能很慢
  • 对阻尼因子 d 的选择敏感;不同的值可能显著改变排名
  • 容易受到链接农场操纵和人为构造的入链的影响

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 通过随机冲浪者马尔可夫链模型具有原理性的概率基础
  • 通过稀疏矩阵-向量乘法和幂迭代可扩展到非常大的图
  • 捕获全局图拓扑,奖励那些获得其他高分节点认可的节点
  • 在 Web、引用、生物和社交网络领域得到广泛验证

应用

  • 搜索引擎排名:根据网页的全局权威性对搜索结果进行排序
  • 学术引用分析:识别科学文献网络中有影响力的论文或期刊
  • 社交网络影响力测量:根据关注者的声望对用户进行排名
  • 生物网络分析:在蛋白质相互作用和基因调控网络中寻找枢纽蛋白或基因
  • 推荐系统:通过用户-物品二分图传播偏好信号

使用方式

使用方式

1

图中的每个节点最初都具有相等的 PageRank 得分 1/N,其中 N 是节点总数。这种均匀初始化确保了没有节点拥有人为的领先优势,并在第一次迭代之前在网络中提供了有效的概率分布。

公式
PR^{(0)}(v_i) = \frac{1}{N}, \quad \forall\, i \in \{1, \ldots, N\}
2

从图的邻接结构构建一个列随机转移矩阵 M。如果存在从节点 j 到节点 i 的边,则 M_ij 等于 1 除以节点 j 的出度,否则为零。悬空节点(没有出边)通常通过将它们的得分均匀地重新分配给所有节点来处理。

公式
M_{ij} = \begin{cases} \frac{1}{\text{out}(v_j)} & \text{if } (v_j \to v_i) \in E \\ 0 & \text{otherwise} \end{cases}
3

使用随机冲浪者公式迭代更新 PageRank 向量。在阻尼因子 d(默认为 0.85)下,每个节点获得一个基础的随机传送概率 (1-d)/N,加上 d 乘以所有链接到它的节点贡献的分数的加权总和。重复此步骤,直到得分稳定。

公式
PR^{(t+1)}(v_i) = \frac{1-d}{N} + d \sum_{v_j \in \mathcal{B}(v_i)} \frac{PR^{(t)}(v_j)}{\text{out}(v_j)}
4

每次迭代后,将得分向量变化量的 L1 范数与一个小容差 epsilon(例如 1e-6)进行比较。当变化量低于此阈值时,算法收敛,并将当前得分向量作为最终的 PageRank 分布返回。

公式
\left\| PR^{(t+1)} - PR^{(t)} \right\|_1 < \varepsilon

常见陷阱

  • 忽略悬空节点(没有出边的节点)可能会破坏转移矩阵的随机性质并导致不正确的得分
  • 在无向图上使用 PageRank 而不转换为对称转移模型可能会产生误导性的中心性估计
  • 设置容差过松会导致过早收敛;设置过紧会增加计算量而得分变化无意义
  • 将 PageRank 解释为绝对重要性度量,而不是特定图上下文中的相对排名

常见问题

阻尼因子 d 代表什么?应如何选择?

阻尼因子 d(通常为 0.85)是随机冲浪者跟随链接而不是随机传送到某个节点的概率。接近 1 的值使算法对图结构更敏感,但收敛速度更慢,并且更容易出现排名陷阱;接近 0 的值则接近均匀排名。0.85 的值由 Page 和 Brin 对 Web 图经验性验证,是标准的默认值。

PageRank 与度中心性有何不同?

度中心性仅计算节点直接入链的数量,所有来源一视同仁。PageRank 根据链接节点的得分来加权每个入链,因此来自高排名节点的认可比来自低排名节点的认可贡献更大。这种递归定义捕获了全局图结构,而不仅仅是局部连通性。

PageRank 能应用于无向图吗?

可以,但有注意事项。无向图必须通过用两条有向边替换每条无向边来转换为有向表示。由此产生的 PageRank 得分等于度中心性的一种函数,将该算法简化为加权度中心性。对于无向网络,通常使用特征向量中心性或介数中心性等替代中心性度量更为有效。

相关方法

参考文献

  1. Page, L., Brin, S., Motwani, R., & Winograd, T. (1999). The PageRank citation ranking: Bringing order to the web. Stanford InfoLab Technical Report.

    打开出版物文献
    已复制。