迭代方法求PageRank

本文介绍如何用迭代的方法计算PageRank。

1. PageRank

博文《网页排序算法PageRank》介绍了PageRank,计算PageRank可以用迭代的方法也可以用代数的方法,其背后的数学基本运算是一样的,即:

$$
PR(p_i) = \frac{1-d}{N} + d \sum_{p_j \in B(p_i)} \frac{PR(p_j)}{L(p_j)}
$$

下文结合图1介绍如何用迭代方法求PageRank。

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

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

wikipedia_pagerank_example
Fig. 2: Label nodes in Fig. 1.

2. 迭代方法

2.1 初始化节点PR值

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

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

相应源代码如下:

# Step 1: Initiate PageRank
N = G.number_of_nodes()                     # N = 11
node_and_pr = dict.fromkeys(G, 1.0 / N)

2.2 创建随机图(stochastic graph)

随机图(stochastic graph)是一个有向带权图,边的权重被normalized,使得每个节点的outedges的权重加起来为1。事实上,边的权重即为\(1/L(p_j)\),图1的随机图如下:

wikipedia_pagerank_example_stochastic_graph
Fig. 4: The stochastic graph

比如,节点D有两条出链,D --> AD --> B,所以他们的边权重都是0.5。源代码如下:

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}}

2.3 迭代计算

遍历所有节点,将每个节点的PR值平均分给其出链的节点,即\(\sum_{p_j \in B(p_i)} \frac{PR(p_j)}{L(p_j)}\),乘以阻尼系数\(d\),再加上\((1-d)/N\)。源代码如下:

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可视化很弱):

wikipedia_pagerank_example_iteration_1
Fig. 5: PageRank after one ieration

那什么时候程序结束呢。将迭代后的PR值跟前一次比较,如果差别很少(如\(PR'(A)-PR(A)<1.0e-6\)),就可以停止迭代了。源代码如下:

# 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值,能不能这样,迭代的时候使用最新的值,这样会不能减少迭代次数,如下所示:

# 初始值
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,这样会不会快一些?

3. NetworkX的pagerank

nx.pagerank跟章节2差不多,区别在于:

# 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\)。

本文涉及到的源代码已经分享到我的GitHub,pagerank目录下的pagerank_iterative.py.

专题: 网页排序算法PageRank (2/3)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

2 thoughts on “迭代方法求PageRank