基于Google算法的有向图PageRank计算结果异常求助

问题描述 #

手动实现Google PageRank算法计算有向图节点权重时，得到的结果与图结构明显不符，需要排查错误并修正。

错误根源 #

核心问题出在转移概率矩阵P的构建逻辑错误：

1. 矩阵行/列对应关系颠倒：PageRank转移矩阵中，第j行应表示节点j的出边转移概率（从j出发到各节点的概率），但原矩阵行对应目标节点、列对应源节点，完全搞反了逻辑。
2. 悬挂节点（节点1）处理错误：正确做法是给悬挂节点补充到所有节点的均匀转移概率，但原矩阵错误地将该逻辑写成了第一行，而非修正节点1的出边行。

修正方案 #

1. 正确构建转移概率矩阵P #

根据图的边结构，按“行对应源节点，列对应目标节点”的规则重新构建矩阵，确保每行概率和为1：

import numpy as np
import sys

# 节点顺序：1,2,3,4,5,6,7,8,9,10,11（对应索引0到10）
P = np.zeros((11, 11), dtype=float)

# 节点1（索引0）：悬挂节点，均匀转移到所有节点
P[0] = np.ones(11) / 11

# 节点2（索引1）：出边到3，转移概率全给节点3（索引2）
P[1, 2] = 1.0

# 节点3（索引2）：出边到2，转移概率全给节点2（索引1）
P[2, 1] = 1.0

# 节点4（索引3）：出边到1、2，各占1/2
P[3, 0] = 1/2
P[3, 1] = 1/2

# 节点5（索引4）：出边到2、4、6，各占1/3
P[4, 1] = 1/3
P[4, 3] = 1/3
P[4, 5] = 1/3

# 节点6（索引5）：出边到2、5，各占1/2
P[5, 1] = 1/2
P[5, 4] = 1/2

# 节点7（索引6）：出边到2、5，各占1/2
P[6, 1] = 1/2
P[6, 4] = 1/2

# 节点8（索引7）：出边到2、5，各占1/2
P[7, 1] = 1/2
P[7, 4] = 1/2

# 节点9（索引8）：出边到2、5，各占1/2
P[8, 1] = 1/2
P[8, 4] = 1/2

# 节点10（索引9）：出边到5，概率为1
P[9, 4] = 1.0

# 节点11（索引10）：出边到5，概率为1
P[10, 4] = 1.0

2. 复用正确的迭代计算逻辑 #

原迭代代码逻辑符合PageRank公式，直接复用即可：

n = P.shape[0]
beta = 0.85
epsilon = 10**-6

r = np.ones(n)*(1/n)
max_iteration = 100
count = 0
localErr = sys.maxsize

while count < max_iteration and localErr > epsilon:
    r_old = r.copy()
    r = beta * np.dot(P.transpose(), r) + ((1 - beta) * (1 / n))
    localErr = np.absolute(r - r_old).sum()
    count += 1

print("PageRank值：")
print(r)
rank = np.argsort(-r)
# 转换为原始节点编号（索引+1）
rank_nodes = [idx + 1 for idx in rank]
print("节点排名（从高到低）：")
print(rank_nodes)

3. 结果验证 #

修正后的结果会贴合图结构：

• 节点2、3因互相指向，权重会处于高位
• 节点5被多个节点指向，权重也会较高
• 悬挂节点1的权重符合随机跳转的预期

额外验证：用NetworkX内置函数对比 #

可以用NetworkX的nx.pagerank函数验证结果一致性：

import networkx as nx

G = nx.DiGraph()
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11])
G.add_edges_from([(4,1),(4,2),(2,3),(3,2),(7,2),(8,2),(9,2),(6,2),(5,2),(5,4),(5,6),(7,5),(8,5),(9,5),(10,5),(11,5),(6,5)])

# 参数保持与手动实现一致
nx_ranks = nx.pagerank(G, alpha=0.85, tol=1e-6)
print("\nNetworkX计算结果：")
sorted_nx_ranks = sorted(nx_ranks.items(), key=lambda x: -x[1])
for node, score in sorted_nx_ranks:
    print(f"节点{node}: {score:.6f}")

该结果应与手动修正后的计算结果完全匹配。

内容的提问来源于stack exchange，提问作者Pravin Poudel