PageRank算法实例详解
郝伟 2021/02/26

PageRank(下称PR)算法是Google于1998/01/29提出的用于计算网页价值的一种算法，具有算法原理简单，可以离线计算等优点，能够有效地减少在线查询时间，极大降低了查询的响应时间。虽然PR也存在一些问题，比如不考虑主题的相关性，所以查询结果与主题的相关性较低；及存在时间长的页面通过等级比新页面要高，这是因为存在时间久的网页更容易被别的网页引用，所以新网页的价值容易被低估（人们往往会更喜欢关注新的网页）。但是通过相关算法的补充进行解决，PR仍然是非常有效的网页评估算法，比如截止2016年11月，PR仍然是Google搜索的核心算法[3]。

研究目的

为漏洞知识图谱的搜索算法提供思路。

PageRank算法基本原理

PageRank本质上是一个马可夫模型，通过一个状态转移矩阵对节点的重要性进行不断迭代，以实现对节点重要性的准确评估。下面通过一个实例来理解其算法。

假设有A, B, ..., E 五个网络，其链接指向关系如下图所示：

graph TD A --> B A --> C B --> D C --> D C --> E D --> E E --> A

我们可以建立节点转移矩阵
$p =\begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix}$

进一步，我们可以得到矩阵的概率转移矩阵，即对每行正则化，每项表示为： $L(p_{i})= {a_{i,j} \over sum(a_j)} \tag 1$ 比如 L(A) = 1, 最终整个矩阵可得：

$P_0 =\begin{bmatrix} 0 & 0.5 & 0.5 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0.5 & 0.5 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \tag 2$

所以 $P^T_0 =\begin{bmatrix} 0 & 0 & 0 & 0 & 1 \\ 0.5 & 0 & 0 & 0 & 0 \\ 0.5 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0.5 & 0 & 0 \\ 0 & 0 & 0.5 & 1 & 0 \\ \end{bmatrix} \tag 2$

在实际应用中，有两点注意事项：

从一个节点到另一个节点的点击实际上都是会递减，即越向后点击的几率越低；
不应该有完全独立的节点，它不指向任何网页任何网页也不指向它。

基于这两点，算法对状态转移矩阵进行了修改，加上了一个系数0.85和一个最小值(1-0.85)/N，N为项数。在加上了两个量以后得：

$P^T=0.85*P^T_0+0.03=\begin{bmatrix} 0.03 & 0.03 & 0.03 & 0.03 & 0.88 \\ 0.455 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.455 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.03 & 0.88 & 0.455 & 0.03 & 0.03 \\ 0.03 & 0.03 & 0.455 & 0.88 & 0.03 \\ \end{bmatrix}$

由于V的初始化状态经过迭代后总会达到最终稳定状态（即迭代后不再变化），所以初始化值可以是固定值或随机值。以下取的是随机值，得到 $V_0$ 如下所示：
$V_0=\begin{bmatrix} 0.19747884 \\ 0.12491352 \\ 0.31185529 \\ 0.23442488 \\ 0.13132746 \\ \end{bmatrix}$

$PR(A) = q ({PR(B) \over L(B)} + {PR(C) \over L(C)} + {PR(D) \over L(D)} + {PR(E) \over L(E)}) + (1-q) \tag 4$ 其中，函数L(X)表示节点X出边的数量。

进一步抽象，一般表达式的每个节点的PR值可以表示为以下：
$PR(p_{j+1})= q\sum_{j=1}^N{PR(p_j) \over L(p_j) } + {1-q \over N} \tag 1$

根据状态转移矩阵和 $V_0$ ，即可通过 $V_{i+1} = P^TV_i$ 进行迭代计算，过程如下所示：

$V_1=P^TV_0=\begin{bmatrix} 0.03 & 0.03 & 0.03 & 0.03 & 0.88 \\ 0.455 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.455 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.03 & 0.88 & 0.455 & 0.03 & 0.03 \\ 0.03 & 0.03 & 0.455 & 0.88 & 0.03 \\ \end{bmatrix} \begin{bmatrix} 0.19747884 \\ 0.12491352 \\ 0.31185529 \\ 0.23442488 \\ 0.13132746 \\ \end{bmatrix}= \begin{bmatrix} 0.14162834 \\ 0.11392851 \\ 0.11392851 \\ 0.26871499 \\ 0.36179965 \\ \end{bmatrix}$

$V_2=P^TV_1=\begin{bmatrix} 0.03 & 0.03 & 0.03 & 0.03 & 0.88 \\ 0.455 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.455 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.03 & 0.88 & 0.455 & 0.03 & 0.03 \\ 0.03 & 0.03 & 0.455 & 0.88 & 0.03 \\ \end{bmatrix} \begin{bmatrix} 0.14162834 \\ 0.11392851 \\ 0.11392851 \\ 0.26871499 \\ 0.36179965 \\ \end{bmatrix}= \begin{bmatrix} 0.3375297 \\ 0.09019205 \\ 0.09019205 \\ 0.17525885 \\ 0.30682736 \\ \end{bmatrix}$
...
$V_{100}=P^TV_{99}=\begin{bmatrix} 0.03 & 0.03 & 0.03 & 0.03 & 0.88 \\ 0.455 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.455 & 0.03 & 0.03 & 0.03 & 0.03 \\ 0.03 & 0.88 & 0.455 & 0.03 & 0.03 \\ 0.03 & 0.03 & 0.455 & 0.88 & 0.03 \\ \end{bmatrix} \begin{bmatrix} 0.25419178\\ 0.13803151\\ 0.13803151\\ 0.20599017\\ 0.26375504\\ \end{bmatrix}= \begin{bmatrix} 0.25419178\\ 0.13803151\\ 0.13803151\\ 0.20599017\\ 0.26375504\\ \end{bmatrix}$

通过以上计算，最终得到了计算好的向量 $V=\begin{bmatrix} 0.25419178\\ 0.13803151\\ 0.13803151\\ 0.20599017\\ 0.26375504\\ \end{bmatrix}$ 其中第一行代表一个对应网页的PR值。

实现代码

#encoding=utf-8
"""
创建日期：Wed Feb 24 06:48:58 2021
作者信息：郝伟老师pc
功能简介：
==== [[Python (programming language)|Python]] ====
PageRank algorithm with explicit number of iterations.

Returns
-------
ranking of nodes (pages) in the adjacency matrix

①x: 表示矩阵（也可以是一维）
②ord：范数类型
    向量的范数：
       ||x||= sum(x_i ^ 2)^0.5    
    矩阵的范数：
    ord=1：列和的最大值
    ord=2：|λE-ATA|=0，求特征值，然后求最大特征值得算术平方根
    ord=∞：行和的最大值
    ord=None：默认情况下，是求整体的矩阵元素平方和，再开根号。（注意.None不是求2范数）
③axis：处理类型
    axis=1表示按行向量处理，求多个行向量的范数
    axis=0表示按列向量处理，求多个列向量的范数
    axis=None表示矩阵范数。
④keepdims：是否保持矩阵的二维特性，避免出现shape = (5, )这样的形状
    True表示保持矩阵的二维特性，False相反

Ref: 
[1] PageRank algorithm, https://en.wikipedia.org/wiki/PageRank
[2] numpy.linalg.norm(), https://docs.scipy.org/doc/numpy-1.15.1/reference/generated/numpy.linalg.norm.html
[3] PageRank算法, https://blog.csdn.net/hguisu/article/details/7996185
[4] The Anatomy of a Large-Scale Hypertextual Web Search Engine, http://infolab.stanford.edu/~backrub/google.html, 1998, Stanford
"""

import numpy as np

def show(title, obj):
    print((' ' + title + ' ').center(60, '*'))
    print(obj)

def pagerank(M, num_iterations: int = 100, d: float = 0.85):
    """ The trillion dollar algorithm.
    Parameters
    ----------
    M : numpy 矩阵
        使用邻接矩阵表示，其中 M_i,j 表示从页面 'j' to 'i', 
        并且对于所有的 'j' sum(i, M_i,j) = 1
    num_iterations : int, optional
        迭代次数, 默认值为 100
    d : float, optional
        损失因子，默认值为 0.85

    Returns
    -------
    numpy array
       一个表示PR的矢量，其中 v_i 是第 i个等级，范围 [0, 1],
       对 v 求和应等于1
    """
    N = M.shape[1] # N=5
    v = np.random.rand(N, 1) # such as [[0.59428688 0.91597221 0.82584001 0.69436602 0.79111371]]
    show('v', v)
    show('(np.linalg.norm(v))', (np.linalg.norm(v)))
    show('(np.linalg.norm(v, ord=1))', (np.linalg.norm(v, ord=1))) # max(sum(abs(x), axis=0))
    show('v.sum()', v.sum())
    v = v / np.linalg.norm(v, 1) 
    show('np.linalg.norm(v, 1)', np.linalg.norm(v, ord=1))
    matrix_trans = d * M + (1 - d) / N
    show('matrix_trans', matrix_trans)
    # 本示例中13次即可达到比较理想的值
    for i in range(num_iterations):
        v1 = matrix_trans @ v # @ equals to np.dot(matrix_trans, v)
        show('v i='+str(i), v)
        v=v1
    return v

# 概率转移矩阵
M = np.array([[  0, 0,   0, 0, 1],
              [0.5, 0,   0, 0, 0],
              [0.5, 0,   0, 0, 0],
              [  0, 1, 0.5, 0, 0],
              [  0, 0, 0.5, 1, 0]])
result = pagerank(M, 10, 0.85)
show('result', result.T)

# [[0.25419178 0.13803151 0.13803151 0.20599017 0.26375504]]
# [[0.43300166 0.23512905 0.23512905 0.35089288 0.44929214]]
def test():
    x = np.array([[0, 3, 4], [1, 6, 4]])
    #默认参数ord=None，axis=None，keepdims=False
    print("默认参数(矩阵整体元素平方和开根号，不保留矩阵二维特性)：",np.linalg.norm(x))
    print("矩阵整体元素平方和开根号，保留矩阵二维特性：",np.linalg.norm(x,keepdims=True))
    print("矩阵每个行向量求向量的2范数：",np.linalg.norm(x,axis=1,keepdims=True))
    print("矩阵每个列向量求向量的2范数：",np.linalg.norm(x,axis=0,keepdims=True))
    print("矩阵1范数：",np.linalg.norm(x,ord=1,keepdims=True))
    print("矩阵2范数：",np.linalg.norm(x,ord=2,keepdims=True))
    print("矩阵∞范数：",np.linalg.norm(x,ord=np.inf,keepdims=True))
    print("矩阵每个行向量求向量的1范数：",np.linalg.norm(x,ord=1,axis=1,keepdims=True))

参考资料

[1] The Anatomy of a Large-Scale Hypertextual Web Search Engine, Stanford University, http://infolab.stanford.edu/~backrub/google.html
[2] PageRank算法简介, https://blog.csdn.net/hguisu/article/details/7996185
[3] The Google PageRank Algorithm, https://web.stanford.edu/class/cs54n/handouts/24-GooglePageRankAlgorithm.pdf
[4] 谷歌背后的数学, https://www.changhai.org/articles/technology/misc/google_math.php
[5] PageRank (III): Examples, http://pagerank.suchmaschinen-doktor.de/index/examples.html
[6] Chapter 11: Markov Chains & PageRank, https://disco.ethz.ch/courses/fs16/ti2/lecture/chapter11.pdf
[7] Google’s PageRank Explained, https://webworkshop.net/pagerank/