PageRank 算法核心思想
PageRank 的核心思想是：一个网页的重要性（排名）取决于指向它的其他网页的数量和质量。
（图片来源网络，侵删）
- 数量：指向一个网页的链接越多，这个网页就越重要。
- 质量：一个由高排名网页指向的链接，比一个由低排名网页指向的链接更有价值。
这形成了一个递归的定义：一个网页的排名取决于其他网页的排名，为了解决这个问题，PageRank 使用了迭代算法，通过多次迭代，让排名值逐渐收敛到一个稳定状态。
PageRank 公式
PageRank 的经典公式如下：
$$PR(A) = (1-d) + d \left( \frac{PR(T_1)}{C(T_1)} + \frac{PR(T_2)}{C(T_2)} + \dots + \frac{PR(T_n)}{C(T_n)} \right)$$
- $PR(A)$ 是页面 A 的 PageRank 值。
- $PR(T_1)$ 到 $PR(T_n)$ 是所有指向页面 A 的页面（$T_1, T_2, \dots, T_n$）的 PageRank 值。
- $C(T_i)$ 是页面 $T_i$ 的出链数量（即它链接出去的页面总数）。
- $d$ 是阻尼系数，通常取值为 0.85，它表示用户有 $d$ 的概率会沿着链接点击，而有 $(1-d)$ 的概率会随机跳转到任意一个页面（避免了“陷阱”问题）。
Python 从零实现 PageRank
我们将使用最基础的数据结构——字典和列表——来实现一个简单的 PageRank 算法。
（图片来源网络，侵删）
步骤 1: 定义网络结构
我们需要一个数据结构来表示网页之间的链接关系,一个字典非常适合这个任务，其中键是源页面，值是它指向的目标页面列表。
# 定义一个简单的网页链接图
# 键是源页面，值是它链接到的目标页面列表
graph = {
'A': ['B', 'C'],
'B': ['C'],
'C': ['A'],
'D': ['C'],
'E': ['A', 'B', 'C', 'D']
}
步骤 2: 准备数据
我们需要计算每个页面的出链数量,这在公式中是分母。
# 计算每个页面的出链数量
out_links = {page: len(links) for page, links in graph.items()}
# 获取所有页面的集合
all_pages = list(graph.keys())
num_pages = len(all_pages)
print("所有页面:", all_pages)
print("出链数量:", out_links)
步骤 3: 实现迭代算法
我们将使用一个循环来不断更新每个页面的 PageRank 值，直到所有页面的 PageRank 值变化非常小（收敛）为止。
def simple_pagerank(graph, damping_factor=0.85, epsilon=1e-6, max_iterations=100):
"""
一个简单的 PageRank 实现。
:param graph: 字典，表示网页链接图。
:param damping_factor: 阻尼系数 d。
:param epsilon: 收敛阈值，当所有节点的 PR 值变化小于此值时停止迭代。
:param max_iterations: 最大迭代次数，防止无限循环。
:return: 字典，包含每个页面的最终 PageRank 值。
"""
# 1. 初始化
pages = list(graph.keys())
num_pages = len(pages)
# 初始时，所有页面的 PR 值相等
pagerank = {page: 1.0 / num_pages for page in pages}
# 计算每个页面的出链数量
out_links = {page: len(links) for page, links in graph.items()}
# 2. 迭代计算
for i in range(max_iterations):
new_pagerank = {}
converged = True
# 计算每个页面的新 PR 值
for page in pages:
# 第一部分：随机跳转的概率 (1-d)
rank_sum = (1 - damping_factor) / num_pages
# 第二部分：来自所有入链页面的贡献
# 遍历所有页面，看它们是否链接到当前页面
for source_page, links in graph.items():
if page in links:
# source_page 有出链，则贡献其 PR 值的一部分
if out_links[source_page] > 0:
rank_sum += damping_factor * pagerank[source_page] / out_links[source_page]
new_pagerank[page] = rank_sum
# 检查是否收敛
if abs(new_pagerank[page] - pagerank[page]) > epsilon:
converged = False
# 更新 PR 值
pagerank = new_pagerank
# 如果已经收敛，则提前结束
if converged:
print(f"在第 {i+1} 次迭代后收敛。")
break
return pagerank
# --- 运行 ---
final_pagerank = simple_pagerank(graph)
print("\n最终的 PageRank 值:")
for page, rank in sorted(final_pagerank.items(), key=lambda item: item[1], reverse=True):
print(f"页面 {page}: {rank:.4f}")
代码解释
- 初始化：所有页面的初始 PageRank 值设为
1/N，N 是页面总数。 - 迭代循环：我们进行最多
max_iterations次迭代。 - 计算新 PR 值：对于每个页面
page：- 随机跳转部分：
(1-d)/N是一个基础值，确保即使没有页面指向它，它也能获得一定的排名。 - 链接贡献部分：遍历整个图，找到所有指向
page的页面source_page，对于每一个source_page，将其当前的 PR 值pagerank[source_page]除以其出链数out_links[source_page]，再乘以阻尼系数d，累加到rank_sum中。
- 随机跳转部分：
- 收敛检查：计算完所有页面的新 PR 值后，检查每个页面的新旧值之差是否都小于
epsilon，如果是，说明算法已经收敛，可以提前结束循环。 - 更新：将新计算出的
new_pagerank赋值给pagerank，为下一次迭代做准备。
优化实现：使用矩阵运算 (NumPy)
上面的实现虽然直观,但对于大规模网络效率低下，我们可以利用线性代数和 NumPy 来优化，因为 PageRank 本质上是一个矩阵-向量乘法问题。
（图片来源网络，侵删）
网络的矩阵表示
我们可以用邻接矩阵 $M$ 来表示图。$M_{ij} = 1$ 表示页面 $j$ 链接到页面 $i$，否则为 0。
为了处理出链页面,我们将 $M$ 的每一列除以其列和（即对应页面的出链数），得到转移矩阵 $G$，如果某页面没有出链（称为“悬挂节点”），我们将其对应列的所有元素设为 1/N，模拟随机跳转。
优化后的代码
import numpy as np
def matrix_pagerank(graph, damping_factor=0.85, epsilon=1e-6, max_iterations=100):
"""
使用 NumPy 矩阵运算实现的 PageRank 算法。
:param graph: 字典，表示网页链接图。
:param damping_factor: 阻尼系数 d。
:param epsilon: 收敛阈值。
:param max_iterations: 最大迭代次数。
:return: NumPy 数组，包含每个页面的最终 PageRank 值。
"""
pages = list(graph.keys())
num_pages = len(pages)
page_index = {page: i for i, page in enumerate(pages)}
# 1. 构建邻接矩阵 M
M = np.zeros((num_pages, num_pages))
for source, targets in graph.items():
for target in targets:
M[page_index[target], page_index[source]] = 1
# 2. 构建转移矩阵 G
# 计算每个页面的出链数
out_degree = np.sum(M, axis=0)
# 处理悬挂节点 (出链数为0的页面)
# 将这些页面的列替换为 1/N
dangling_nodes = out_degree == 0
G = np.zeros_like(M, dtype=float)
for j in range(num_pages):
if dangling_nodes[j]:
G[:, j] = 1.0 / num_pages
else:
G[:, j] = M[:, j] / out_degree[j]
# 3. 构建 PageRank 矩阵 A
# A = d * G + (1-d) * E
# E 是一个所有元素都为 1/N 的矩阵
E = np.ones((num_pages, num_pages)) / num_pages
A = damping_factor * G + (1 - damping_factor) * E
# 4. 迭代计算
# 初始化 PR 向量 v
v = np.ones(num_pages) / num_pages
for i in range(max_iterations):
v_new = A @ v # 矩阵-向量乘法
if np.linalg.norm(v_new - v, 1) < epsilon: # L1 范数检查收敛
print(f"在第 {i+1} 次迭代后收敛。")
break
v = v_new
return v
# --- 运行 ---
final_pagerank_matrix = matrix_pagerank(graph)
print("\n使用 NumPy 矩阵运算的最终 PageRank 值:")
for i, rank in enumerate(final_pagerank_matrix):
print(f"页面 {list(graph.keys())[i]}: {rank:.4f}")
优势
- 速度：NumPy 的底层是 C 语言实现的，矩阵运算比 Python 循环快几个数量级，尤其适合大规模数据。
- 简洁：
A @ v一行代码就完成了复杂的求和计算，代码更简洁，更符合数学思想。
使用专业库 networkx
在实际项目中,我们通常会使用成熟的图计算库，如 networkx，它不仅内置了 PageRank 算法，还提供了丰富的图分析功能。
安装 networkx
pip install networkx
networkx 实现
import networkx as nx
# 1. 创建一个有向图
G = nx.DiGraph()
# 2. 添加边 (链接关系)
# 从我们之前的 graph 字典添加
for source, targets in graph.items():
for target in targets:
G.add_edge(source, target)
# 3. 使用 networkx 的 pagerank 函数
# 它已经处理了所有细节，包括悬挂节点和收敛判断
nx_pagerank = nx.pagerank(G, alpha=0.85, max_iter=100, tol=1e-06)
print("\n使用 networkx 的最终 PageRank 值:")
for page, rank in sorted(nx_pagerank.items(), key=lambda item: item[1], reverse=True):
print(f"页面 {page}: {rank:.4f}")
# 你还可以轻松地可视化这个图
# import matplotlib.pyplot as plt
# pos = nx.spring_layout(G) # 布局算法
# nx.draw(G, pos, with_labels=True, node_size=1000, node_color='skyblue', font_size=15, font_weight='bold')
# plt.show()
优势
- 便捷：代码量最少，一行
nx.pagerank()即可完成。 - 健壮：库已经处理了各种边界情况（如悬挂节点、非连通图等）。
- 功能强大：除了 PageRank，
networkx还提供了数百种其他图算法和分析工具。
| 方法 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 从零实现 (字典) | 易于理解 PageRank 的基本原理 | 效率低，代码冗长 | 学习和教学目的 |
| 矩阵实现 (NumPy) | 高效，代码简洁，符合数学思想 | 需要理解线性代数 | 中小规模网络，或需要自己实现核心逻辑时 |
专业库 (networkx) |
极其便捷、健壮、功能强大 | 依赖外部库，对初学者来说像个“黑盒” | 绝大多数实际项目和工程应用 |
对于学习和理解,建议从从零实现开始；对于性能有要求的自定义项目，NumPy 矩阵实现是很好的选择；而在实际工作中，直接使用 networkx 是最高效、最可靠的做法。
