简介：面向大数据与图算法学习者，这是一份围绕web-Google.txt数据集计算PageRank的Python实现资源。资源提供三种方法：先用Python稀疏矩阵完成单机计算，再调用NetworkX库的内置PageRank，第三种则基于NetworkX但自行编写PageRank逻辑。三种方法可对照理解稀疏矩阵存储、迭代收敛以及库函数的封装差异。包体共4个文件，包括3个Python脚本和1个GZ格式的原始网页数据，总大小19.38MB，脚本按方法分别组织，数据文件可直接用于运行验证。目前已有821人学习下载，适合正在学习PageRank算法或需要处理大规模图数据的初学者及研究生参考。通过这三个程序，读者能够直接运行并对比不同实现方式的性能与代码复杂度，是深入掌握图计算的好素材。 做Web数据挖掘的朋友，电脑里十有八九都收藏过SNAP数据集。web-Google.txt是里面的经典之一：它记录了Google在2002年抓取的网页之间的链接关系，八十七万多个节点、五百多万条边。很多人拿它练手PageRank，但真正一口气用Python跑完并得到结果的，却不多。原因不是你算法没背熟，而是数据量上来了，内存和计算效率的问题会一起冒出来。这篇文章我就来说说，怎么用Python把web-Google.txt上的PageRank算明白，重点讲三种方法，以及为什么“稀疏矩阵”才是单机解决这个问题的关键。文章适合刚接触图算法、需要用真实数据集做实验的同学，也适合想把手写PageRank跑通的人。
1. 项目背景与PageRank核心思路
1.1 web-Google.txt 到底是什么
web-Google.txt来自斯坦福SNAP数据集，是2002年Google网页间超链接关系的一个快照。文件里每一行是一条有向边，格式大致是：
0 11342 0 824020 ...前面的数字是源网页ID，后面是目标网页ID，表示“源页面有一条超链接指向目标页面”。整个数据集包含875713个节点和5105039条有向边，节点ID范围是0到875712。
这个数据集的经典之处在于：它规模不算特别大，但足够让普通的稠密矩阵“爆炸”。如果你天真地用一个875713×875713的二维数组存邻接矩阵，光是元素数量就是大约7.67e11，就算每个元素只占1个字节，也需要700多GB内存，单机根本扛不住。所以只要涉及这种规模的图计算，稀疏矩阵就是必然选择。实际图中平均每个节点的出链只有5.8条左右，非零元素占比不到百万分之一，用稀疏结构存储是最优解。
1.2 PageRank的数学原理
PageRank的核心想法是：一个网页的重要程度，由所有链接到它的页面共同决定。公式长这样：
PR(i) = (1-d)/N + d * Σ_{j∈in(i)} PR(j) / out_degree(j)
其中d是阻尼因子，通常取0.85，N是网页总数，out_degree(j)是页面j的出链数量。这个公式可以理解成一个“随机游走”模型：用户以d的概率沿着当前页面的出链继续点击，以1-d的概率随机打开一个全新页面。阻尼因子的存在，保证了整个马尔可夫链的收敛性。
用矩阵表示的话，设A为邻接矩阵，A[i][j]=1表示i链向j；D为出度对角矩阵。那么转移概率矩阵P = D^(-1) A，PageRank向量r满足：
r = d * P^T r + (1-d)/N * 1
在具体实现中，P^T就是“按入链聚合”的转移矩阵。稀疏矩阵的矩阵向量乘非常擅长处理这种操作，所以幂迭代法能跑得很快。
1.3 为什么必须用稀疏矩阵
稀疏矩阵的意义不只是省内存，更是省计算时间。CSR、CSC这类格式只保留非零元素，迭代计算时也只需要遍历非零元素，矩阵向量乘的复杂度是O(nnz)而不是O(n^2)。web-Google.txt有约510万条边，nnz量级500万左右，单机做一次矩阵向量乘只要毫秒到几十毫秒。如果换成稠密矩阵，87万阶的乘法操作是天文数字，完全无法在个人电脑上完成。
SciPy提供了csr_matrix、csc_matrix等格式，可以直接读入边表构建矩阵，也内置了高效的稀疏线性代数操作。后面三种方法里，前两种都直接基于SciPy稀疏矩阵，第三种用NetworkX，本质上也依赖图的稀疏存储。
2. 三种方法的整体设计与选型
2.1 方法一：稀疏矩阵幂迭代法
幂迭代是PageRank最经典、最稳定的解法。思路很简单：从任意初始向量r0开始，反复套用公式 r_{k+1} = d * (P^T r_k) + (1-d)/N * 1，直到向量变化小于阈值。因为转移矩阵的谱半径是1，阻尼因子d保证了次特征值小于1，所以迭代必然收敛。
我用SciPy的稀疏矩阵实现，核心操作只有两个：一个是Tr @ r，另一个是给结果加上随机跳转项。由于整个计算都是稀疏矩阵乘以稠密向量，内存占用和计算量都在可接受范围内。这个方法的优点是原理简单、代码短、几乎不出错，是我处理web-Google.txt时的首选。
2.2 方法二：稀疏特征值法
PageRank还可以看成是一个特征值问题。因为r = M r，其中M是概率转移矩阵，r就是M对应特征值1的特征向量。SciPy的scipy.sparse.linalg.eigs可以计算稀疏矩阵的最大特征值和对应特征向量，所以理论上可以用它一步到位。
但这里有个坑：M其实不是一个显式的稀疏矩阵，因为随机跳转项会给每个位置都叠加一个常数，导致矩阵变稠密。好在eigs支持传入LinearOperator，我们只需要定义matvec函数，让稀疏部分和低秩修正部分分开计算，就能在不构造稠密矩阵的情况下完成特征值求解。这个思路很有意思，也是很多生产级PageRank系统背后的数学技巧。
2.3 方法三：NetworkX内置PageRank
NetworkX是Python里最常用的图分析库，自带pagerank函数，底层实现了带个人化向量和悬挂节点处理的幂迭代。它不需要你手动构造稀疏矩阵，只需要把边表传进去建一个有向图就行。代码最少，适合快速验证。
当然，NetworkX的默认实现不是用SciPy的CSR矩阵做矩阵向量乘，而是在Python层面对节点字典做迭代。对于500万条边，运行时间会比方法一慢不少。我自己在8核16G的单机上跑，体感是能跑完，但中间去倒了杯水。如果你追求性能，建议把它当作“标准答案”交叉验证，而不是生产方案。
2.4 三种方法对比速览
| 方法 | 核心思路 | 实现复杂度 | 内存占用 | 运行速度 | 适用场景 |
|---|---|---|---|---|---|
| 幂迭代法 | 不动点迭代 | 低 | 低 | 快 | 大规模图首选，单机百亿边内都能试 |
| 稀疏特征值法 | 特征向量求解 | 中 | 中 | 较慢，可能不收敛 | 数学实验、算法研究，不太推荐大图 |
| NetworkX内置 | 封装好的幂迭代 | 极低 | 中 | 慢 | 快速验证、学习对比 |
3. 环境准备与数据预处理
3.1 Python安装与依赖
我建议直接用Python 3.8以上版本。如果你还没装Python，去官网下载安装包时记得勾选“Add Python to PATH”，这是新手最容易卡住的一步。装好之后确认版本：
python --version然后安装依赖：
pip install numpy scipy networkx pandasNumPy和SciPy是核心，pandas用来读取文本很方便，NetworkX用来做第三种方法。如果你的机器内存小于8G，运行特征值法时可能会吃力；但方法一和方法三在16G内存下没有任何问题。
3.2 加载web-Google.txt并构建邻接矩阵
下载web-Google.txt之后，第一步不是直接读成矩阵，而是先看文件头部。SNAP数据集前面通常有几行注释，需要跳过：
import numpy as np import pandas as pd from scipy.sparse import csr_matrix, diags df = pd.read_csv( "web-Google.txt", sep="\t", header=None, names=["src", "dst"], skiprows=4, )read_csv之后记得去重和去除自环。数据里如果存在重复边，会重复累加权重，导致出度计算错误；自环会让页面给自己贡献权重，也需要清理：
df = df.drop_duplicates() df = df[df["src"] != df["dst"]]节点数量可以这样确认：
n = max(df["src"].max(), df["dst"].max()) + 1 print(n) # 875713SNAP说明文档里说节点ID是0到875712，所以直接用原始ID作为矩阵行列索引即可。如果换成其他数据集，节点ID不连续，就需要先做映射重编号。
构造邻接矩阵：
row = df["src"].values col = df["dst"].values data = np.ones(len(df), dtype=np.float64) A = csr_matrix((data, (row, col)), shape=(n, n))这里A[i,j]=1表示i链向j。接着计算每个节点的出度，并做行归一化：
out_degree = np.array(A.sum(axis=1)).ravel() out_degree[out_degree == 0] = 1.0 # 避免除零 inv_out = 1.0 / out_degree T = diags(inv_out) @ AT的行和是1，代表从当前节点随机选择一个出链的概率分布。出度为0的节点在T中对应一整行都是0，悬挂节点问题等会在迭代时统一处理。
3.3 处理悬挂节点与归一化
悬挂节点就是出度为0的网页。现实里大量页面没有任何外链，用户到了这些页面会陷入死胡同。PageRank的标准做法是：当游走到悬挂页面时，下一步随机跳到任意一个页面。反映在公式上，要把悬挂节点这部分的概率质量均匀分配出去。
在代码里可以这样记录悬挂节点：
dangling = np.array(A.sum(axis=1)).ravel() == 0幂迭代每次更新时，需要单独计算所有悬挂节点贡献的PR值总和，然后把它们按1/N均匀加到每个节点上：
dangling_sum = r[dangling].sum() r_next += (d * dangling_sum) / n另外向量r要始终保持归一化，也就是所有PR值加起来等于1。这样计算出来的PR值才是合法概率分布，后续排序和对比才有意义。
4. 三种方法的Python实现与核心代码
4.1 方法一：幂迭代法的完整实现
先定义转移矩阵的转置：
Tr = T.T.tocsr()PageRank迭代更新可以写成：
def pagerank_power(T, dangling, d=0.85, max_iter=100, tol=1e-8): n = T.shape[0] Tr = T.T.tocsr() r = np.full(n, 1.0 / n) for _ in range(max_iter): r_next = d * (Tr @ r) dangling_sum = r[dangling].sum() r_next += (d * dangling_sum) / n r_next += (1 - d) / n err = np.abs(r_next - r).sum() r = r_next if err < tol: break return r这段代码里有几个细节需要解释。为什么用Tr @ r而不是T @ r？因为PageRank公式里要对“入链”聚合。T是行归一化的出链矩阵，T.T的每一行对应一个页面所有入链的权重，乘上当前PR向量后，就能得到这个页面的新PR值。
我实测下来，d=0.85时，L1误差到1e-8大概需要七八十次迭代，时间在几十秒量级。整个过程中最大的内存开销就是几个875713维的浮点向量，每个约7MB，完全没压力。
4.2 方法二：稀疏特征值法实现
方法二使用LinearOperator定义PageRank的转移算子。关键是把随机跳转部分用低秩修正表示，不显式构造稠密矩阵：
from scipy.sparse.linalg import LinearOperator, eigs def pagerank_eigs(T, dangling, d=0.85, maxiter=200): n = T.shape[0] Tr = T.T.tocsr() def matvec(x): y = d * (Tr @ x) dang_sum = dangling @ x total_sum = x.sum() y += (d * dang_sum + (1 - d) * total_sum) / n return y operator = LinearOperator((n, n), matvec=matvec, dtype=np.float64) vals, vecs = eigs(operator, k=1, which="LM", maxiter=maxiter) r = np.real(vecs[:, 0]) return r / r.sum()这里dangling是布尔数组，dangling @ x实际上做了一次点积，得到所有悬挂节点当前的PR和。total_sum = x.sum()对应随机跳转项里的全局质量。因为特征向量不受缩放影响，最后归一化一次就好。
需要说明的是，eigs用的是ARPACK，对大规模问题不一定保证收敛。我在web-Google.txt上跑的时候，有时会提示NoConvergence，把maxiter调大或者把tol放宽点会好一些。如果只是为了计算PageRank，方法一明显更稳；这个方法的科普价值大于实用价值。
4.3 方法三：NetworkX内置实现
NetworkX的代码最简洁：
import networkx as nx G = nx.DiGraph() G.add_edges_from(df[["src", "dst"]].values) pr = nx.pagerank(G, alpha=0.85)pr是一个字典，key是节点ID，value是PageRank值。NetworkX内部会处理悬挂节点，不需要你手动写那些修正项。你可以把它转成数组，跟前两种方法的结果做相关性分析。
不过这里有一个性能陷阱：add_edges_from接收一个二维数组时，如果数据量有500万行，构建图会花一些时间；nx.pagerank内部默认还开启了nstart和tol，实际迭代次数和方法一差不多。整体跑完大概几分钟，属于“省心但费时”的路线。
4.4 结果验证与TopN网页排序
三种方法跑完之后，最重要的是验证结果是否一致。我们可以把排名前10的节点抓出来看：
indices = np.argsort(r)[::-1][:10] for idx in indices: print(idx, r[idx])再计算一下幂迭代结果和NetworkX结果的相关系数：
pr_array = np.array([pr[i] for i in range(n)]) corr = np.corrcoef(r, pr_array)[0, 1] print(corr)相关性通常都在0.999以上，说明实现没有方向性错误。如果发现某个方法与另一个方法差异很大，优先检查边方向是否反了，或者悬挂节点处理是否遗漏。
5. 性能分析与踩坑记录
5.1 内存占用与运行时间对比
以我自己的8核16G笔记本为例：方法一跑完大约是50秒，内存峰值不到1.5G；方法二eigs需要迭代更多轮，耗时大约2分钟，而且偶尔不收敛；方法三NetworkX最慢，大概5分钟，主要卡在Python层循环。所以如果你只想拿到一个准确结果，方法一性价比最高。
稀疏矩阵格式也很影响性能。做Tr @ r时，Tr用CSR格式效果最好；如果要做逐行访问更新，改成CSC或CSR各有优劣。幂迭代只做矩阵向量乘，所以统一用tocsr()就好，不用过度调优。
5.2 常见问题：格式选择、收敛判断、除以零
先说收敛判断。不要用L2范数，PageRank更常用L1范数，也就是所有元素差值的绝对值之和。L1收敛到1e-6通常已经够用了，我建议追求1e-8，迭代次数也不会多太多。
再说除以零。如果某个节点出度为0，直接按out_degree求倒数会得到inf。最简单的方法是先把出度为0的节点临时设成1，避免NaN，然后用dangling数组单独处理这些节点的贡献。这个方法不改变随机游走模型，是PageRank标准实现里常见做法。
还有一个容易踩的坑：文件里的分隔符。SNAP官方给的web-Google.txt是用制表符分隔的，但也有镜像站可能转成了空格。读取之前先看一眼原始文件，别让sep参数写错。
5.3 手写实现的一些体会
我前前后后在web-Google.txt上跑过很多次PageRank，最大的体会是：不要迷信“矩阵求逆”或者“直接解方程”。PageRank的矩阵规模摆在那里，即使能用稀疏矩阵表示，直接分解的开销也远大于迭代法。幂迭代之所以是经典，不是因为简单，而是因为它在真实环境下就是最实用的。
另外，如果你想把结果可视化，可以输出Top500节点并用Gephi画图，但web-Google.txt的节点太多，全画出来意义不大。更推荐先按PR值做对数分桶，再随机抽样子图，这样既能看出结构，又不会卡死电脑。
最后再分享一个小技巧：在做大规模迭代前，先用小数据集（比如SNAP里更小的web-Stanford）把代码跑通，确认边方向和悬挂节点逻辑无误，再切到web-Google.txt。这样会帮你省下无数调试时间。
本文还有配套的精品资源，点击获取
