PageRank 算法
Larry Page 和 Sergey Brin 发明 PageRank，奠定 Google 搜索引擎的核心技术。
事件概述
1998年，斯坦福大学的 Larry Page 和 Sergey Brin 发明了 PageRank 算法，并通过论文《The Anatomy of a Large-Scale Hypertextual Web Search Engine》发表。PageRank 通过分析网页之间的链接关系来评估网页的重要性，将互联网视为一个巨大的图，网页的排名取决于指向它的其他网页的数量和质量。这一算法成为 Google 搜索引擎的核心，帮助 Google 从众多搜索引擎中脱颖而出，彻底改变了人们获取信息的方式。PageRank 也是图神经网络和信息检索领域的经典算法，展示了如何从大规模链接结构中提取有价值信息。
深度学习笔记
背景、原理、影响与要点，一次读懂这个事件
背景与脉络
1990 年代中期，万维网爆炸式增长，传统搜索引擎按关键词频次排序，结果充斥垃圾页面。1996 年，斯坦福大学博士生 Larry Page 与 Sergey Brin 提出一个反直觉的想法：不再只看页面内容，而是看「谁链接它」——把整个互联网视为一张巨大的有向图，一个页面的重要性由链接它的页面数量与质量递归决定。这个想法成为 BackRub 项目（Google 前身）的核心，1998 年两人在万维网国际会议（WWW）论文《The Anatomy of a Large-Scale Hypertextual Web Search Engine》中发表了完整系统。PageRank 以 Larry Page 命名，它让 Google 在搜索结果质量上迅速超越所有对手，也成为图算法与网络科学最著名的应用之一。
核心要点
- 11998 年由 Larry Page 与 Sergey Brin 在斯坦福提出，是 Google 搜索引擎的核心排序算法。
- 2把互联网看作有向图，用链接结构递归地度量页面重要性。
- 3随机冲浪者模型给出概率解释：页面重要性等于长期停留在该页面的概率。
- 4引入阻尼因子（约 0.85）模拟用户偶尔跳转到随机页面，保证数学收敛。
- 5用幂迭代在稀疏矩阵上高效计算，可扩展到数十亿级别的网页规模。
原理与技术细节
PageRank 的数学非常简洁。设页面 i 的重要性为 r(i)，若页面 j 链向 n(j) 个页面，则每个出链传递 r(j)/n(j) 的重要性：r(i) = Σ_{j→i} r(j)/n(j)。这正是一个矩阵方程 r = Mᵀr，即图转移矩阵的主特征向量。直接迭代可能在某些环状结构上不收敛，于是引入阻尼：用户以概率 d（约 0.85）沿链接继续浏览，以 1−d 的概率跳转到任意页面，迭代式变为 r(i) = (1−d)/N + d·Σ_{j→i} r(j)/n(j)。这个方程对所有图都收敛到唯一正解，用幂迭代只需反复做稀疏矩阵-向量乘法，每轮复杂度与链接总数成正比。PageRank 本质上度量的是「在图上做随机游走时的平稳分布」，它把「声望」这个模糊概念变成了可计算的图性质。
影响与后续
PageRank 的直接后果是 Google 的崛起：排序质量的数量级提升让「组织全球信息」从口号变成产品，也催生了基于链接分析的整个 SEO 产业与对抗它的垃圾链接斗争。学术上，它是网络科学的奠基应用之一：随机游走、平稳分布、主特征向量这些概念从此进入大众技术语汇，并被移植到社交网络影响力排序、推荐系统、引文分析（它很像引文分析的递归形式）等无数场景。它的局限同样著名：链接可被买卖与操纵（链接农场）、新页面与冷门页面吃亏、只反映「声望」而不反映「相关」——Google 后来用数百个信号弥补这些缺陷。PageRank 的历史地位在于：它是第一个把大规模网络结构转化为产品级智能的算法。
学习要点
- 链接即投票，投票者的权重不同——递归定义重要性的思想极简却极强。
- 阻尼因子既解决收敛问题，也建模了真实用户的随机跳转行为。
- 幂迭代 + 稀疏矩阵让谱方法可以跑到十亿级规模。
- 任何排序信号都可被博弈，鲁棒性必须作为一等设计目标。
术语表
设想用户在网页间随机点击跳转，PageRank 即其长期访问各页面的概率分布。
反复用矩阵乘向量并归一化以逼近主特征向量的经典数值方法。
PageRank 中约 0.85 的继续沿链接浏览概率，保证算法收敛并模拟随机跳转。