网页排序算法(二)迭代方法求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。





Fig. 1: PageRanks for a simple network (image from Wikipedia).

为了便于讨论,将图1下方的节点分别标上G, H, I, J, K,如下图所示:





Fig. 2: Label nodes in Fig. 1.

迭代方法

初始化节点PR值

如果没有给节点指定PR初始值,那么每个节点的PR初始化为1/N (N为节点数目),以图1为例,节点的PR初始值为1/11





Fig. 3: The graph with starting value of PageRank iteration for each node.

相应源代码如下:

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 --> AD --> B,所以他们的边权重都是0.5。源代码如下:

1
2
3
4
stochastic_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
11
dangling_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。

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器