第21章 PageRank算法

习题21.1

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

解答：

解答思路：

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

解答步骤：

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

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

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

$$\begin{array}{}\text{(21.1)}& M=[m_{ij}{]}_{n\times n}\end{array}$$

满足以下性质：

$$\begin{array}{}\text{(21.2)}& m_{ij}⩾0\text{(21.3)}& {\displaystyle \sum _{i=1}^m{m}_{ij}=1}\end{array}$$

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

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

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

$$C_{ij}=\sum _{k=1}^n{A}_{ik}{B}_{kj}$$

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

$$\begin{array}{rl}\sum _{i=1}^n{C}_{ij}& =\sum _{i=1}^n\sum _{k=1}^n{A}_{ik}{B}_{kj}\\ & =\sum _{k=1}^n{B}_{kj}\sum _{i=1}^n{A}_{ik}\end{array}$$

  $\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$

$$\begin{array}{}\text{(21.6)}& MR=R\end{array}$$

平稳分布$R$称为这个有向图的PageRank。$R$的各个分量称为各个结点的PageRank值。

$$R=\left[\begin{array}{c}PR(v_1)\\ PR(v_2)\\ ⋮\\ PR(v_n)\end{array}\right]$$

其中$PR(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⩽d⩽1)$。这个一般随机游走的马尔可夫链存在平稳分布，记作$R$。定义平稳分布向量$R$为这个有向图的一般PageRank。$R$由公式

$$\begin{array}{}\text{(21.10)}& R=dMR+\frac{1-d}{n}\mathbf{1}\end{array}$$

决定，其中$\mathbf{1}$是所有分量为1的$n$维向量。

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

$$\begin{array}{}\text{(21.11)}& PR(v_i)=d\left(\sum _{v_j\in M(v_i)}\frac{PR(v_j)}{L(v_j)}\right)+\frac{1-d}{n},i=1,2,\cdots ,n\end{array}$$

这里$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的转移矩阵可以写作

$$\begin{array}{}\text{(21.22)}& R=(dM+\frac{1-d}{n}\mathit{E})R=AR\end{array}$$

其中$d$是阻尼因子，$\mathit{E}$ 是所有元素为1的$n$阶方阵。

  结合定理21.1，需证明PageRank一般定义中的马尔科夫链的转移矩阵$A$满足以下条件：

1. $A$非负；
2. $A$不可约；
3. $A$非周期；
4. $A$有限。

第3步：证明PageRank一般定义中的马尔科夫链符合平稳分布定理的条件

1. $A$非负
   基本转移矩阵$M$每个元素都非负，所以显然$A$中每个元素也非负。
2. $A$不可约
   如果有一个非零概率从任何状态过渡到任何其它状态，即图是强连通的，则被称为不可约。因为定义了完全随机的转移矩阵，所以$A$是不可约的。
3. $A$非周期
   因为定义了完全随机的转移矩阵，所以每个点都有指向自己的边，即从每个点出发再返回，都有长度为1的路径，所以$A$是非周期的。
4. $A$有限
   结合一般PageRank的定义，可知网页是有限的，则$A$是有限的。

习题21.4

  证明随机矩阵的最大特征值为1。

解答：

解答思路：

1. 证明1是随机矩阵的特征值
2. 使用反证法，证明1是最大的特征值

解答步骤：

第1步：证明1是随机矩阵的特征值

  假设随机矩阵$A\in R^{n\times n}$，其转置为$A^T$，则$A^T$的行和为1。显然全1向量$\mathbf{1}$是$A^T$的一个特征向量，对应特征值为1，即：

$$A^T\mathbf{1}=1\cdot \mathbf{1}$$

  $\because$ $A$与$A^T$互为转置向量，它们有相同的特征值
  $\therefore$ 1也是$A$的特征值

第2步：使用反证法，证明1是最大的特征值

   假设存在特征值$\lambda$大于1，有：

$$A^T\mathit{v}=\lambda \mathit{v}$$

  设$v_k$是$\mathit{v}$中的最大元素。因为$A^T$的每个元素非负，且行和为1，则$\lambda \mathit{v}$中的每个元素都是$\mathit{v}$中元素的凸组合。

凸组合的概念
设向量$\{x_i\},i=1,2,\cdots ,n$，如有实数${\lambda }_i⩾0$，且${\displaystyle \sum _{i=1}^n{\lambda }_i=1}$，则称${\displaystyle \sum _{i=1}^n{\lambda }_i{x}_i}$为向量$\{x_i\}$的一个凸组合（凸线性组合）。

  所以$\lambda \mathit{v}$中的元素都小于等于$v_k$，即：

$$\sum _{j=1}^n{A^T}_{ij}{v}_j=\lambda v_i⩽v_k$$

  若$\lambda >1$，则会有$\lambda v_k>v_k$，和上式矛盾，所以特征值$\lambda$大于1的假设不成立。

  所以$A^T$的最大特征值为1，也就是$A$的最大特征值为1。

参考文献

【1】凸组合的概念：https://baike.baidu.com/item/凸组合/18999826?fr=aladdin