IT博客汇 | 迭代方法求PageRank

迭代方法求PageRank

SparkandShine发表于 2017-02-17 13:57:15

本文介绍如何用迭代的方法计算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。

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

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

Fig. 2: Label nodes in Fig. 1.

2. 迭代方法

2.1 初始化节点PR值

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

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的随机图如下：

Fig. 4: The stochastic graph

比如，节点D有两条出链，D --> A和D --> 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可视化很弱）：

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，如下图：

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.