Python实现简易PageRank与NetworkX结果不符，请求错误排查

你在实现简易PageRank时，发现自己的代码输出和NetworkX的pagerank函数结果不一致，以下是你的原始代码：

import networkx, numpy.matlib, numpy.linalg

nodes = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
edges = [(1, 3, 1), (1, 9, 1), (2, 9, 1), (2, 10, 1), (3, 7, 1), (3, 9, 1), (4, 2, 1), (4, 8, 1), (4, 10, 1), (5, 6, 1), (5, 8, 1), (6, 1, 1), (6, 5, 1), (6, 8, 1), (6, 10, 1), (7, 1, 1), (7, 9, 1), (8, 5, 1), (8, 6, 1), (8, 7, 1), (9, 4, 1), (9, 8, 1), (10, 7, 1)]

DG = networkx.DiGraph()
DG.add_weighted_edges_from(edges)

pr = networkx.pagerank(DG)
for n in nodes:
    print(n, pr[n])

A = networkx.adjacency_matrix(DG, nodes).todense()
stochasticA = A / A.sum(axis = 0)

d = 0.85
epsilon = 1e-6
M = d * stochasticA + (1 - d) / len(nodes)
old_page_rank_vector = numpy.matlib.ones((len(nodes), 1)) / len(nodes)
new_page_rank_vector = M * old_page_rank_vector
while (numpy.linalg.norm(old_page_rank_vector - new_page_rank_vector) > epsilon):
    old_page_rank_vector = new_page_rank_vector
    new_page_rank_vector = M * old_page_rank_vector

page_rank_vector = new_page_rank_vector/sum(new_page_rank_vector)
print(page_rank_vector)

错误点解析 #

• 邻接矩阵方向错误：
  NetworkX的adjacency_matrix生成的矩阵中，行代表源节点，列代表目标节点（即A[i][j]表示从节点nodes[i]到nodes[j]有边）。但PageRank的转移矩阵要求M[i][j]表示从节点j转移到节点i的概率，所以需要先将邻接矩阵转置，再做归一化。
• 未处理悬挂节点（出度为0的节点）：
  如果某个节点没有出边，A.sum(axis=0)会得到0，导致stochasticA中出现NaN。NetworkX的pagerank会自动将这类节点的转移概率设为均匀分配到所有节点，你的代码缺少这个处理。
• 多余的归一化操作：
  正确构造的转移矩阵迭代后，PageRank向量本身已经是归一化的，最后再除以总和会引入不必要的误差。

修正后的代码 #

import networkx
import numpy as np

nodes = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
edges = [(1, 3, 1), (1, 9, 1), (2, 9, 1), (2, 10, 1), (3, 7, 1), (3, 9, 1), (4, 2, 1), (4, 8, 1), (4, 10, 1), (5, 6, 1), (5, 8, 1), (6, 1, 1), (6, 5, 1), (6, 8, 1), (6, 10, 1), (7, 1, 1), (7, 9, 1), (8, 5, 1), (8, 6, 1), (8, 7, 1), (9, 4, 1), (9, 8, 1), (10, 7, 1)]

DG = networkx.DiGraph()
DG.add_weighted_edges_from(edges)

# 打印NetworkX的结果
pr = networkx.pagerank(DG)
for n in nodes:
    print(f"NetworkX PageRank for {n}: {pr[n]:.6f}")

# 构造邻接矩阵并转置，转换为列代表源节点，行代表目标节点
A = networkx.adjacency_matrix(DG, nodes).todense().T
n_nodes = len(nodes)

# 计算每个节点的出度，处理出度为0的情况（悬挂节点）
out_degrees = A.sum(axis=0)
# 对出度为0的节点，设置出度为n_nodes（模拟均匀转移到所有节点）
out_degrees[out_degrees == 0] = n_nodes

# 构造随机转移矩阵
stochasticA = A / out_degrees

d = 0.85
epsilon = 1e-6
# 构造带阻尼因子的转移矩阵
M = d * stochasticA + (1 - d) / n_nodes

# 初始化PageRank向量
old_pr = np.ones((n_nodes, 1)) / n_nodes
new_pr = M @ old_pr

# 迭代直到收敛
while np.linalg.norm(old_pr - new_pr) > epsilon:
    old_pr = new_pr
    new_pr = M @ old_pr

# 打印自定义实现的结果
print("\nCustom PageRank results:")
for idx, n in enumerate(nodes):
    print(f"{n}: {new_pr[idx, 0]:.6f}")

内容的提问来源于stack exchange，提问作者Lessness Randomness