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

PageRank

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

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

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

0.png

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

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

1.png

Fig. 2: Label nodes in Fig. 1.

迭代方法

初始化节点PR值

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

2.png

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)

创建随机图（stochastic graph）

随机图（stochastic graph）是一个有向带权图，边的权重被normalized，使得每个节点的outedges的权重加起来为1。事实上，边的权重即为

1/L(pj)