PageRank算法详解

简介

转载于：PageRank算法详解。

在实际应用中许多数据都以图（graph）的形式存在，比如，互联网、社交网络都可以看作是一个图。图数据上的机器学习具有理论与应用上的重要意义。 PageRank 算 法是图的链接分析（link analysis）的代表性算法，属于图数据上的无监督学习方法。

PageRank算法最初作为互联网网页重要度的计算方法，1996 年由Page和Brin提出，并用于谷歌搜索引擎的网页排序。事实上，PageRank 可以定义在任意有向图上，后来被应用到社会影响力分析、文本摘要等多个问题。

PageRank算法的基本想法是在有向图上定义一个随机游走模型，即一阶马尔可夫链，描述随机游走者沿着有向图随机访问各个结点的行为。在一定条件下，极限情况访问每个结点的概率收敛到平稳分布，这时各个结点的平稳概率值就是其PageRank值，表示结点的重要度。PageRank 是递归定义的，PageRank 的计算可以通过迭代算法进行。

本文第1节给出PageRank 的定义，第2节叙述PageRank的计算方法，包括常用的幕法 （power method）。

PageRank的定义

基本想法

历史上，PageRank算法作为计算互联网网页重要度的算法被提出。PageRank是定义在网页集合上的一个函数，它对每个网页给出一个正实数，表示网页的重要程度，整体构成一个向量，PageRank值越高，网页就越重要，在互联网搜索的排序中可能就被排在前面。

假设互联网是一个有向图，在其基础上定义随机游走模型，即一阶马尔可夫链，表示网页浏览者在互联网上随机浏览网页的过程。假设浏览者在每个网页依照连接出去的超链接以等概率跳转到下一个网页，并在网上持续不断进行这样的随机跳转，这个过程形成一阶马尔可夫链。PageRank表示这个马尔可夫链的平稳分布。每个网页的PageRank值就是平稳概率。

图1表示一个有向图，假设是简化的互联网例，结点$A$，$B$，$C$，$D$表示网页，结点之间的有向边表示网页之间的超链接，边上的权值表示网页之间随机跳转的概率。假设有一个浏览者，在网上随机游走。如果浏览者在网页$A$，则下一步以$1/3$的概率转移到网页$B$，$C$，$D$。如果浏览者在网页$B$，则下一步以$1/2$的概率转移到网页$A$和$D$。如果浏览者在网页$C$，则下一步以概率$1$，则下一步以概率$A$。如果浏览者在网页$D$，则下一步以$1/2$的概率转移到网页$B$和$C$。

直观上，一个网页，如果指向该网页的超链接越多，随机跳转到该网页的概率也就越高，该网页的PageRank值就越高，这个网页也就越重要。一个网页，如果指向该网页的PageRank值越高，随机跳转到该网页的概率也就越高，该网页的PageRank值就越高，这个网页也就越重要。PageRank值依赖于网络的拓扑结构，一旦网络的拓扑(连接关系)确定，PageRank值就确定。

PageRank 的计算可以在互联网的有向图上进行，通常是一个迭代过程。先假设一个初始分布，通过迭代，不断计算所有网页的PageRank值，直到收敛为止。

下面首先给出有向图及有向图上随机游走模型的定义，然后给出PageRank的基本定义，以及PageRank的一般定义。基本定义对应于理想情况，一般定义对应于现实情况。

有向图和随机游走模型

有向图

定义1 (有向图) 有向图（directed graph）记作 $G=(V,E)$，其中$V$和$E$分别表示结点和有向边的集合。比如，互联网就可以看作是一个有向图，每个网页是有向图的一个结点，网页之间的每一条超链接是有向图的一条边。从一个结点出发到达另一个结点，所经过的边的一个序列称为一条路径 （path） , 路径上边的个数称为路径的长度。如果一个有向图从其中任何一个结点出发可以到达其他任何一个结点，就称这个有向图是强连通图 （strongly connected graph） 。 图1中的有向图就是一个强连通图。

假设$k$是一个大于$1$的自然数，如果从有向图的一个结点出发返回到这个结点的路径的长度都是$k$的倍数，那么称这个结点为周期性结点。 如果一个有向图不含有周期性结点，则称这个有向图为非周期性图 （aperiodic graph），否则为周期性图。图2是一个周期性有向图的例子。从结点$A$出发返回到$A$，必须经过路径$A-B-C-A$，所有可能可能的路径的长度都是$3$的倍数，所以结点$A$是周期性结点。 这个有向图是周期性图。

随机游走模型

定义2（随机游走模型）给定一个含有$n$个结点的有向图，在有向图上定义随机游走（ random walk）模型，即一阶马尔可夫链，其中结点表示状态，有向边表示状态之间的转移，假设从一个结点到通过有向边相连的所有结点的转移概率相等。具体地，转移矩阵是一个$n$阶矩阵$M$

$$M=\left[m_{i j}\right]_{n \times n}$$

第$i$行第$j$列的元素$m_{ij}$取值规则如下：如果结点$j$有$k$个有向边连出，并且结点$i$是其连出的一个结点，则$m_{ij}=1/k$；否则$m_{i j}=0, i, j=1,2, \cdots \cdots, n$。

注意转移矩阵具有性质：

$$m_{i j} \geq 0$$ $$\sum_{i=1}^n m_{i j}=1$$

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

在有向图上的随机游走形成马尔可夫链。也就是说，随机游走者每经一个单位时间转移一个状态，如果当前时刻在第$j$个结点（状态），那么下一个时刻在第$i$个结点（状态）的概率是$m_{ij}$这一概率只依赖于当前的状态，与过去无关，具有马尔可夫性。

在图1的有向图上可以定义随机游走模型。结点$A$到结点$B$，$C$和$D$存在有向边，可以以概率$1/3$从$A$分别转移到$B$，$C$和$D$，并以概率$0$转移到$A$，于是可以写出转移矩阵的第$1$列。结点$B$到结点$A$和$D$存在有向边，可以以概率$1/2$从$B$分别转移到$A$和$D$，并以概率$0$分别转移到$B$和$C$，于是可以写出矩阵的第$2$列，等等。于是得到转移矩阵

$$M=\left[\begin{array}{cccc} 0 & 1 / 2 & 1 & 0 \\ 1 / 3 & 0 & 0 & 1 / 2 \\ 1 / 3 & 0 & 0 & 1 / 2 \\ 1 / 3 & 1 / 2 & 0 & 0 \end{array}\right]$$

随机游走在某个时刻$t$随机游走在某个时刻$t$的状态分布，可以用一个$n$维列向量 $R_t$表示，那么在时刻$t+1$访问各个结点的概率分布$R_{t+1}$满足

$$R_{t+1}=M R_t$$

PageRank 的基本定义

给定一个包含$n$个结点的强连通且非周期性的有向图，在其基础上定义随机游走模型。假设转移矩阵为$M$， 在时刻$0,1,2, \cdots, t, \cdots$访问各个结点的概率分布为

$$R_0, M R_0, M^2 R_0, \cdots, M^t R_0, \cdots$$

则极限

$$\lim _{t \rightarrow \infty} M^t R_0=R$$

存在，极限向量$R$表示马尔可夫链的平稳分布，满足

$$M R=R$$

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

$$M R=R$$

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

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

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

显然有

$$P R\left(v_i\right) \geqslant 0, \quad i=1,2, \cdots, n$$ $$\sum_{i=1}^n P R\left(v_i\right)=1$$ $$P R\left(v_i\right)=\sum_{v_j \in M\left(v_i\right)} \frac{P R\left(v_j\right)}{L\left(v_j\right)}, \quad i=1,2, \cdots, n$$

这里$M\left(v_i\right)$表示指向结点$v_i$的结点集合，$L\left(v_j\right)$表示结点$v_j$连出的有向边的个数。

PageRank的基本定义是理想化的情况，在这种情况下，PageRank存在，而且可以通过不断迭代求得PageRank值。

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

根据马尔可夫链平稳分布定理，强连通且非周期的有向图上定义的随机游走模型（马尔可夫链） ，在图上的随机游走当时间趋于无穷时状态分布收敛于唯一的平稳分布。

PageRank 的一般定义

PageRank 一般定义的想法是在基本定义的基础上导入平滑项。

给定一个含有 $n$ 个结点 $v_i, \quad i=1,2, \cdots, n$，的任意有向图，假设考虑一个在图上随机游走模型，即一阶马尔可夫链，其转移矩阵是$M$，从一个结点到其连出的所有结点的转移概率相等。这个马尔可夫链未必具有平稳分布。 假设考虑另一个完全随机游走的模型，其转移矩阵的元素全部为 $1/n$， 也就是说从任意一个结点到任意一个结点的转移概率都是$1/n$。 两个转移矩阵的线性组合又构成一个新的转移矩阵，在其上可以定义一个新的马尔可夫链。 容易证明这个马尔可夫链一定具有平稳分布，且平稳分布满足

$$\begin{aligned} R & =\left(d M+\frac{1-d}{n} E\right) R \\ & =d M R+\frac{1-d}{n} 1 \end{aligned}$$

式中$d(0 \leq d \leq 1)$是系数，称为阻尼因子（damping factor），$E$是全为1的矩阵，$R$是$n$维向量，$1$是所有分量为$1$的$n$维向量。$R$表示的就是有向图的一般PageRank。

式（10）中第一项表示（状态分布是平稳分布时）依照转移矩阵$M$访问各个结点的概率，第二项表示完全随机访问各个结点的概率。阻尼因子$d$取值由经验决定，例如$d=0.85$。当$d$接近$1$时，随机游走主要依照转移矩阵$M$进行；当$d$接近$0$时，随机游走主要以等概率随机访问各个结点。

可以由式 (10) 写出每个结点的 PageRank，这是一般 PageRank 的定义。

$$P R\left(v_i\right)=d\left(\sum_{v_j \in M\left(v_i\right)} \frac{P R\left(v_j\right)}{L\left(v_j\right)}\right)+\frac{1-d}{n}, \quad i=1,2, \cdots, n$$

第二项称为平滑页，由于采用平滑项，所有结点的 PageRank 值都不会为 0，具有以下性质：

$$P R\left(v_i\right)>0, \quad i=1,2, \cdots, n$$ $$\sum_{i=1}^n P R\left(v_i\right)=1$$

下面给出 PageRank 的一般定义。

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

$$R=d M R+\frac{1-d}{n} 1$$

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

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

PageRank 的计算

PageRank 的定义是构造性的，即定义本身就给出了算法。本节列出 PageRank 的 计算方法包括法代算法、幂法、代数算法。常用的方法是幂法。

迭代算法

给定一个含有$n$个结点的有向图，转移矩阵为$M$，有向图的一般 PageRank 由迭代公式（14）的极限向量$R$确定。PageRank 的迭代算法，就是按照这个一般定义进行选代，直至收敛。

算法 1 （PageRank 的迭代算法）

输入：含有$n$个结点的有向图，转移矩阵$M$， 阻尼因子$d$ ， 初始向量$R_0$；

输出：有向图的 PageRank 向量$R$。

（1）令$t=0$

（2）计算

$$R=d M R+\frac{1-d}{n} 1$$

（3）如果$R_{t+1}$与$R_t$充分接近，令$R=R_{t+1}$停止迭代。

（4）否则$t=t+1$$，执行（2）

算法2 （计算一般 PageRank 的幂法）

输入：含有$n$个结点的有向图，转移矩阵$M$， 阻尼因子$d$ ， 初始向量$x_0$，计算精度$\varepsilon$；

输出：有向图的 PageRank 向量$R$。

（1）令$t=0$，选择初始向量$x_0$

（2）计算有向图的一般转移矩阵$A$

$$A=d M+\frac{1-d}{n} E$$

（3）迭代并规范化结果向量

$$\begin{aligned} & y_{t+1}=A x_t \\ & x_{t+1}=\frac{y_{t+1}}{\left\|y_{t+1}\right\|} \end{aligned}$$

（4） 当$\left|x_{t+1}-x_t\right|<\varepsilon$时，令$R=x_t$，停止迭代。

（5）否则，令$t=t+1$， 执行步 (3)。

（6）对$R$进行规范化处理，使其表示概率分布。

算法3 （代数算法）

代数算法通过一般转移矩阵的逆矩阵计算求有向图的一般 PageRank。

按照一般 PageRank 的定义式（14），于是，

$$(I-d M) R=\frac{1-d}{n} 1$$ $$R=(I-d M)^{-1} \frac{1-d}{n} 1$$

这里$I$是单位矩阵。当$0<d<1$时，线性方程组（15）的解存在且唯一。这样，可以通过求逆矩阵$(I-d M)^{-1}$得到有向图的一般PageRank。

参考文献

统计学习方法第二版 李航