PageRank：互联网的民主
PageRank算法由Google创始人Larry Page和Sergey Brin于1996年提出， 革命性地改变了搜索引擎的工作方式。 它将互联网视为一个巨大的有向图，每个网页是节点，链接是有向边。
PageRank的核心思想：一个网页的重要性不仅取决于有多少网页链接到它（数量假设）， 更取决于链接它的网页本身有多重要（质量假设）。 这种"民主投票"机制通过幂迭代找到稳态分布，量化每个网页的重要性。
✦
24.1
从有向图到转移矩阵
邻接矩阵与转移矩阵的构造
将互联网建模为有向图：节点代表网页，有向边代表超链接。邻接矩阵A描述连接关系，转移矩阵T则将其转化为概率转移， 每列元素之和为1，表示从某节点跳转到其他节点的概率分布。
📐 从邻接矩阵到转移矩阵
步骤1：行求和
计算每个节点的出度（从该节点出发的边数）
步骤2：归一化
邻接矩阵每行除以对应出度
步骤3：转置
转置得到转移矩阵T，每列和为1
✦
24.2
PageRank的两个基本假设
数量假设与质量假设
PageRank算法基于两个核心假设：数量假设认为被更多网页链接的页面更重要；质量假设认为高质量页面的链接传递更多权重。 这两个假设结合，形成了一个自洽的排名系统。
🔢 数量假设
入度越高越重要
如果一个页面被很多其他页面链接，说明它可能包含有价值的信息
示例
维基百科首页被数百万页面链接，自然很重要
⭐ 质量假设
权威传递
被高排名页面链接比被低排名页面链接更有价值
示例
被《纽约时报》链接比被个人博客链接更能提升排名
🔄 数学表达：Tr = r
ri = Σj Tij rj
意义：节点i的PageRank值等于所有指向它的节点j传递来的权重之和
稳态：这是一个特征值问题，r是特征值λ=1对应的特征向量
✦
24.3
幂迭代与修正
迭代求解与阻尼系数
幂迭代（Power Iteration）是求解PageRank的常用方法。 从均匀分布开始，反复应用转移矩阵，直到收敛到稳态分布。 为了解决陷阱节点、排他性循环等问题，引入阻尼系数d=0.85， 表示有85%概率按链接跳转，15%概率随机跳到任意页面。
🔄 标准幂迭代
r(t+1) = T · r(t)
步骤：
1. 初始化：r(0) = [1/n, ..., 1/n]
2. 迭代：r(t+1) = T · r(t)
3. 归一化：使||r||1 = 1
4. 收敛检测：||r(t+1) - r(t)|| < ε
✨ 修正幂迭代
r(t+1) = d · T · r(t) + (1-d)/n · 1
解决的问题：
• 陷阱节点（悬挂节点）：无出边
• 排他性循环：封闭循环困住权重
• 分隔子图：不连通的子图
阻尼系数d：通常取0.85，表示85%按链接走，15%随机跳
⚠️ 标准幂迭代的失效情况
陷阱节点
没有出链接的节点（如被删除边e→a后的节点e）， 导致PageRank值流失，无法收敛
排他性循环
完全封闭的循环，PageRank值在循环内部传递， 无法分配给循环外的节点
分隔子图
图不连通，各子图独立收敛， 无法在全局达到一致的PageRank分配
✦
本章小结
本章介绍了PageRank算法， Google搜索引擎的核心技术之一。 它将互联网视为有向图，通过分析链接结构量化网页重要性。 PageRank的核心是数量假设和质量假设， 数学上表现为转移矩阵的特征向量问题。
🔄 算法流程
1
建模有向图
节点=网页，边=链接
2
邻接矩阵A
A[i][j]=1表示i→j
3
转移矩阵T
归一化+转置
4
幂迭代
r = T·r
5
修正（可选）
r = d·T·r + (1-d)/n
6
排名
按PageRank值排序
💡 关键概念
转移矩阵
每列元素之和为1，表示概率转移
稳态分布
Tr = r，马尔可夫链的平稳分布
特征值问题
r是λ=1对应的特征向量
阻尼系数
d=0.85，解决陷阱节点等问题
🌐 PageRank：图论 + 线性代数 + 马尔可夫链 🌐
一个算法改变互联网
图论
有向图、邻接矩阵
线性代数
特征值、幂迭代
概率论
马尔可夫链、稳态分布
从6个网页到数十亿网页，PageRank让搜索引擎成为可能