第21章 PageRank算法

习题21.1

  假设方阵A是随机矩阵，即其每个元素非负，每列元素之和为1，证明$A^k$仍然是随机矩阵，其中$k$是自然数。

解答：

解答思路：

1. 给出随机矩阵定义；
2. 证明随机矩阵的乘积仍然是随机矩阵；
3. 证明$A^k$仍然是随机矩阵。

解答步骤：

第1步：给出随机矩阵定义

  根据书中第21.1.2节的随机矩阵定义：

转移矩阵是一个$n$阶矩阵$M$

$$$$

即每个元素非负，每列元素之和为1，即矩阵$M$为随机矩阵。

  根据题意：随机矩阵$A$满足以下性质：
  （1）是方阵；
  （2）每个元素非负；
  （3）每列元素之和为1。

第2步：证明随机矩阵的乘积仍然是随机矩阵
  假设随机矩阵$A \in R^{n \times n}$与随机矩阵$B \in R^{n \times n}$相乘为矩阵$C$，即

  $\because$ A、B均是随机矩阵
  $\therefore A_{ik} \geqslant 0，B_{ik} \geqslant 0$
  $\therefore$ 显然，$C_{ij}$非负

  $\because A$ 是随机矩阵
  $\therefore \displaystyle \sum_{i=1}^n A_{ik} = 1$
  $\therefore \displaystyle \sum_{i=1}^n C_{ij} = \sum_{k=1}^n B_{kj}$
  $\because B$ 是随机矩阵
  $\therefore \displaystyle \sum_{k=1}^n B_{kj} = 1$
  $\therefore \displaystyle \sum_{i=1}^n C_{ij} = 1$

  矩阵$C$满足：
  （1）是方阵；
  （2）每个元素非负；
  （3）每列元素之和为1。
  $\therefore$ 矩阵$C$为随机矩阵，即随机矩阵的乘积仍为随机矩阵

第3步：证明$A^k$仍然是随机矩阵
  根据第2步的推导，随机矩阵的乘积仍然为随机矩阵，可得$A^k$仍然是随机矩阵

习题21.2

  例21.1中，以不同的初始分布向量$R_0$进行迭代，仍然得到同样的极限向量$R$，即PageRank。请验证。

解答：

解答思路：

1. 给出PageRank的基本定义
2. 自编程实现基本定义的PageRank的迭代求解算法
3. 使用例21.1中的转移矩阵，设置不同的初始分布向量$R_0$，验证可得到相同的极限向量$R$

解答步骤：

第1步：PageRank的基本定义

  根据书中第21.1.3节的定义21.3的PageRank的基本定义：

定义21.3（PageRank的基本定义） 给定一个包含$n$个结点$v_1, v_2, \cdots, v_n$的强连通且非周期性的有向图，在有向图上定义随机游走模型，即一阶马尔可夫链。随机游走的特点是从一个结点到有向边连出的所有结点的转移概率相等，转移矩阵为$M$，这个马尔科夫链具有平稳分布$R$

$$$$

其中$P R(v_i), i=1,2,\cdots, n$，表示结点$v_i$的PageRank值。

第2步：实现基本定义的PageRank的迭代求解算法

import numpy as np

def page_rank_basic(M, R0, max_iter=1000):
    """
    迭代求解基本定义的PageRank
    :param M: 转移矩阵
    :param R0: 初始分布向量
    :param max_iter: 最大迭代次数
    :return: Rt: 极限向量
    """
    Rt = R0
    for _ in range(max_iter):
        Rt = np.dot(M, Rt)
    return Rt

第3步：设置不同的初始分布向量$R_0$，验证可得到相同的极限向量$R$

# 使用例21.1的转移矩阵M
M = np.array([[0, 1 / 2, 1, 0],
              [1 / 3, 0, 0, 1 / 2],
              [1 / 3, 0, 0, 1 / 2],
              [1 / 3, 1 / 2, 0, 0]])

# 使用5个不同的初始分布向量R0
for _ in range(5):
    R0 = np.random.rand(4)
    R0 = R0 / np.linalg.norm(R0, ord=1)
    Rt = page_rank_basic(M, R0)
    print("R0 =", R0)
    print("Rt =", Rt)
    print()

R0 = [0.24051216 0.26555451 0.22997054 0.26396279]
Rt = [0.33333333 0.22222222 0.22222222 0.22222222]

R0 = [0.0208738  0.60050438 0.26292553 0.11569629]
Rt = [0.33333333 0.22222222 0.22222222 0.22222222]

R0 = [0.31824487 0.19805355 0.27130894 0.21239265]
Rt = [0.33333333 0.22222222 0.22222222 0.22222222]

R0 = [0.16258713 0.37625269 0.18512522 0.27603496]
Rt = [0.33333333 0.22222222 0.22222222 0.22222222]

R0 = [0.27067789 0.16907504 0.31245762 0.24778945]
Rt = [0.33333333 0.22222222 0.22222222 0.22222222]

​

  我们可以发现，使用不同的初始分布向量$R_0$进行迭代求解，仍然得到同样的极限向量$R$。

习题21.3

  证明PageRank一般定义中的马尔科夫链具有平稳分布，即式(21.11)成立。

解答：

解答思路：

1. 给出PageRank的一般定义
2. 给出马尔科夫链平稳分布定理
3. 证明PageRank一般定义中的马尔科夫链符合平稳分布定理的条件

解答步骤：

第1步：PageRank的一般定义

  根据书中第21.1.4节的定义21.4的PageRank的一般定义：

定义21.4（PageRank的一般定义） 给定一个含有$n$个结点的任意有向图，在有向图上定义一个一般的随机游走模型，即一阶马尔科夫链。一般的随机游走模型的转移矩阵由两部分的线性组合组成，一部分是有向图的基本转移矩阵$M$，表示从一个结点到其连出的所有结点的转移概率相等，另一部分是完全随机的转移矩阵，表示从任意一个结点到任意一个结点的转移概率都是$1/n$，线性组合系数为阻尼因子$d(0 \leqslant d \leqslant 1)$。这个一般随机游走的马尔可夫链存在平稳分布，记作$R$。定义平稳分布向量$R$为这个有向图的一般PageRank。$R$由公式

$$$$

这里$M(v_i)$是指向结点$v_i$的结点集合，$L(v_j)$是结点$v_j$连出的边的个数。

  根据书中第21.1.4节的一般PageRank的定义的解释：

  一般PageRank的定义意味着互联网游览器，按照以下方法在网上随机游走：在任意一个网页上，浏览者或者以概率$d$决定按照超链接随机跳转，这时以等概率从链接出去的超链接跳转到下一个网页；或者以概率$(1 - d)$决定完全随机跳转，这时以等概率$1 / n$跳转到任意一个网页。第二个机制保证从没有连接出去的超链接的网页也可以跳转出。这样可以保证平稳分布，即一般PageRank的存在，因而一般PageRank适用于任何结构的网络。

第2步：写出马尔科夫链平稳分布定理

  根据书中第21.1.3节的定理21.1：

定理21.1 不可约且非周期的有限状态马尔科夫链，有唯一平稳分布存在，并且当时间趋于无穷时状态分布收敛于唯一的平稳分布。

  根据书中第21.2.2节的公式(21.22)：

一般PageRank的转移矩阵可以写作

$$$$

A^T \boldsymbol{1} = 1 \cdot \boldsymbol{1}

A^T \boldsymbol{v} = \lambda \boldsymbol{v}

\sum_{j=1}^n {A^T}{ij} v{j} = \lambda v_{i} \leqslant v_k