本文结合实例介绍如何用代数方法求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: Draw Fig. 1 in NetworkX.

代数方法

根据1中的等式，把所有节点都放在一块，可以得到：

$$ \begin{bmatrix} PR(p_1) \\ PR(p_2) \\ \vdots \\ PR(p_3) \end{bmatrix} = \begin{bmatrix} {(1-d)/ N} \\ {(1-d) / N} \\ \vdots \\ {(1-d) / N} \end{bmatrix}

• d \begin{bmatrix} \ell(p_1,p_1) & \ell(p_1,p_2) & \cdots & \ell(p_1,p_N) \\ \ell(p_2,p_1) & \ddots & & \vdots \\ \vdots & & \ell(p_i,p_j) & \\ \ell(p_N,p_1) & \cdots & & \ell(p_N,p_N) \end{bmatrix} \begin{bmatrix} PR(p_1) \\ PR(p_2) \\ \vdots \\ PR(p_3) \end{bmatrix} $$

上述等式可以缩写为：

$$ \mathbf{R} = d \mathcal{M}\mathbf{R} + \frac{1-d}{N} \mathbf{1}. (**) $$

其中，1为N维的列向量，所有元素皆为1。以图1为例，该列向量为，

N = len(G.nodes())      # N = 11
column_vector = np.ones((N, 1), dtype=np.int)

[[1]
 [1]
 [1]
 [1]
 [1]
 [1]
 [1]
 [1]
 [1]
 [1]
 [1]]

Adjacency function

邻接函数（adjacency function）$\ell(p_1,p_2)$组成了矩阵M，

$$ \mathcal{M}_{ij} =\ell(pi,pj) = \begin{cases} 1 /L(p_j) , & \text{if }j\text{ links to }i ,\text{L(pj)是指从pj链出去的网页数目}\\ 0, & \text{otherwise} \end{cases} $$

这样矩阵每一行乘以R，就得到了新的PR值，比如第二行（图1的节点B），