网页排序算法（二）迭代方法求PageRank
本文介绍如何用迭代的方法计算PageRank。
PageRank
博文《网页排序算法（一）PageRank》介绍了PageRank，计算PageRank可以用迭代的方法也可以用代数的方法，其背后的数学基本运算是一样的，即：
$$PR(pi)=\frac{1−d}{N}+d\sum{p_j\in B(p_i)}\frac{PR(pj)}{L(p_j)}$$
下文结合图1介绍如何用迭代方法求PageRank。
为了便于讨论，将图1下方的节点分别标上G, H, I, J, K，如下图所示：
迭代方法
初始化节点PR值
如果没有给节点指定PR初始值，那么每个节点的PR初始化为1/N (N为节点数目)，以图1为例，节点的PR初始值为1/11：
相应源代码如下：1
2
3# Step 1: Initiate PageRank
N = G.number_of_nodes() # N = 11
node_and_pr = dict.fromkeys(G, 1.0 / N)
创建随机图（stochastic graph）
随机图（stochastic graph）是一个有向带权图，边的权重被normalized，使得每个节点的outedges的权重加起来为1。事实上，边的权重即为$$1/L(p_j)$$，图1的随机图如下：
Fig. 4: The stochastic graph
比如，节点D有两条出链，D --> A和D --> B，所以他们的边权重都是0.5。源代码如下：1
2
3
4stochastic_graph = nx.stochastic_graph(G, weight=weight) # M = 1/L(pj)
print(stochastic_graph['D'])
{'A': {'Edge Id': u'5', 'weight': 0.5}, 'B': {'Edge Id': u'6', 'weight': 0.5}}
迭代计算
遍历所有节点，将每个节点的PR值平均分给其出链的节点，即$$\sun_{p_j\in B(p_i)}\frac{PR(p_j)}{L(p_j)}$$，乘以阻尼系数d，再加上(1−d)/N。源代码如下：1
2
3
4
5
6
7
8
9
10
11dangling_value = (1-d)/N
for _ in range(max_iter): # for each iteration
node_and_prev_pr = node_and_pr
node_and_pr = dict.fromkeys(node_and_prev_pr.keys(), 0)
for node in node_and_pr: # for each node
for out_node in stochastic_graph[node]: # node --> out_node
node_and_pr[out_node] += d * node_and_prev_pr[node] * stochastic_graph[node][out_node][weight] # PR(p_i) = d * PR(p_j)}/L(p_j)
node_and_pr[node] += dangling_value
第一次迭代结果如下图所示（有些箭头没显示出来，NetworkX可视化很弱）：
Fig. 5: PageRank after one ieration
那什么时候程序结束呢。将迭代后的PR值跟前一次比较，如果差别很少（如PR′(A)−PR(A)<1.0e−6PR′(A)−PR(A)<1.0e−6），就可以停止迭代了。源代码如下：1
2
3
4# check convergence, l1 norm
err = sum([abs(node_and_pr[node] - node_and_prev_pr[node]) for node in node_and_pr])
if err < N*tol:
return node_and_pr
在本例中，需要66次迭代，最后得到的PageRank，如下图：
wikipedia_pagerank_example_pr
Fig. 6: Stable PageRank values (66 iterations)
我在想一个问题，上面的方法，每次迭代都是基于上一次的PR值，能不能这样，迭代的时候使用最新的值，这样会不能减少迭代次数，如下所示：1
2
3
4
5
6
7# 初始值
PA(D) = 0.09
PA(B) = 0.09
# 第一次迭代
PA(D)/2 --> P(A), P(B) # 此时， PB(B)=0.045
PB(B) --> P(C) # 按上面的算法，PB(B)=0.09，那能不能使用刚更新的PR值0.045，这样会不会快一些？
NetworkX的pagerank
nx.pagerank跟章节2差不多，区别在于：1
2
3
4
5
6# 2中的算法
node_and_pr[node] += (1.0 - d)/N
# nx.pagerank
danglesum = d * sum(node_and_prev_pr[node] for node in dangling_nodes)
node_and_pr[node] += danglesum/N + (1.0 - d)/N # danglesum/N + (1-d)/N
nx.pagerank将图中所有悬挂节点（dangling nodes，没有出链的节点，图1只有节点A）的PR累加，并normalized，再加上(1.0–d)/N。