1 PageRank 算法简介

PageRank 算法是由拉里·佩奇和谢尔盖·布林于 1998 年提出并发表，该算法是一个非常经典的 Web 页面排名算法。凭借着 PageRank 算法的基本思想与成功的商业经营，Google已经成为全球非常优秀的互联网企业。之后，许多学者提出了许多PageRank 改进算法。PageRank算法的思想主要是基于网络结构的分析，Web页面之间的链接关系构成了一个网络生态系统，每个页面都有自己的职能、地位等。

PageRank 最初作为互联网网页重要度的计算方法，并应用于谷歌搜索引擎的网页排序。不过，其也可以定义在任意有向图上，后来应用到社会影响力分析，文本摘要等多个问题。

2 PageRank 基本思想

PageRank 认为当某个页面里有个链接(URL)，那么该页面就对这个 URL 指向页面的内容认可或者肯定，那么这个 URL 页面内容的权威性会有所增加。例如网页 A 上有网页 B 的链接，那么网页 A 认为网页 B 的内容是有价值。由此推出，如果有许多网页中有网页 B 的链接（URL)，那么表明网页 B 的内容被许多个网页认可，表明了页面 B 的内容具有很高的价值，PageRank 算法认为网页 B 内容具有权威性或者极大价值。PageRank 算法还有一个优点在于，它不仅仅统计网页被链接的数量，还衡量了链接该网页的 URL 本身权值。如果一个网页被权威很高的网页指向，比被一般网页指向，它得到更高的权值。这点类似于社交网络分析中等级权威的观念。

在 PageRank 算法中，表示每个网页权威性的值称为 PR 值，每个网页的 PR 值不仅仅取决于被链接网页的数量，还受到指向该网页的URL的质量和重要程度影响。PageRank 算法认为每个网页的 PR 值都被均匀的分配到它指向的网页，如此迭代下来，网络中每个页面的 PR 值达到稳定、收敛状态。

PageRank 的计算一般是在有向图上进行，通常是一个基于随机游走的迭代过程。下面首先给出有向图及有向图上的随机游走模型的定义，然后给出 PageRank 的基本定义，以及 PageRank 的一般定义。基本定义对应于理想情况、一般定义对应于现实情况。

3 有向图和随机游走模型

3.1 有向图

有向图（directed graph）记作 $G=(V,E)$ ，其中 $V$ 和 $E$ 分别表示节点和有向边的集合。

例如，互联网就可以看作是一个有向图，每个网页是有向图的一个结点，网页之间的每一条超链接是有向图的一条边。

从一个结点出发到达另一个结点，所经过的边的一个序列称为一条路径（path），路径上边的个数称为路径的长度。如果一个有向图从其中任何一个结点出发可以到达其他任何一个结点，就称这个有向图是强连通图（strongly connected graph）。

假设 $k$ 是一个大与 1 的自然数，如果从有向图的一个结点出发返回到这个结点的路径的长度都是 $k$ 的倍数，那么称这个结点为周期性结点。如果一个有向图不含有周期性结点，则称这个有向图为非周期性图（aperiodic graph），否则为周期性图。

3.2 随机游走模型

给定一个含有 $n​$ 个结点的有向图，在有向图上定义随机游走（random walk）模型，即一阶马尔可夫链。其中结点表示状态，有向边表示状态之间的转移，并假设从一个结点到所有结点的转移概率相等。具体地，转移矩阵是一个 $n​$ 阶矩阵 $M​$
$$
M = [m_{ij}]_{n\times n}
$$
第 $i$ 行第 $j$ 列的元素 $m_{ij}$取值规则如下：如果结点 $j$ 有 $k$ 个有向边练出，并且结点 $i$ 是其练出的一个结点，则 $m_{ij} = \frac1k$；否则 $m_{ij} = 0,\ i,j=1,2,\cdots,n$。

并且，转移矩阵具有性质：
$$
m_{ij} \ge 0
$$

$$
\sum_{i=1}^nm_{ij} = 1
$$

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

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

4 PageRank 的基本定义

给定一个包含 $n$ 个结点的强连通且非周期性的有向图，在其基础上定义随机游走模型。假设转移矩阵为 $M$，在时刻 $0,1,2,\cdots,t,\cdots$ 访问各结点的概率分布为：
$$
R_0, MR_0,M^2R_0,\cdots,M^tR_0,\cdots
$$
则极限
$$
\lim_{t\to\infty}M^tR_0 = R
$$
存在，极限向量 $R$ 表示马尔可夫链的平稳分布，满足
$$
MR=R
$$
而给定一个包含 $n$ 个结点 $v_1,v_2,\cdots,v_n$ 的强连通且非周期的有向图，在有向图上定义随机游走模型，即一阶马尔科夫链。随机游走的特点是从一个结点到有有向边连出的所有结点的转移概率相等，转移矩阵为 $M$ ，这个马尔可夫链具有平稳分布 $R$
$$
MR=R
$$
平稳分布 $R$ 称为这个有向图的 PageRank，$R$ 的各个分量称为各个结点的 PageRank 值。
$$
R=
\left[
\begin{matrix}
PR(v_1)\\
PR(v_2)\\
\vdots\\
PR(v_n)
\end{matrix}
\right]其中 $PR(v_i),i=1,2,\cdots,n$ 表示结点 $v_i$ dde
$$
其中 $PR(v_i),i=1,2,\cdots,n$ 表示结点 $v_i​$ 的 PageRank 值。

显然有
$$
PR(v_i)\ge0,\ i=1,2,\cdots,n
$$

$$
\sum_{i=1}^nPR(v_i)=1
$$

$$
PR(v_i)=\sum_{v_j\in M(v_i)}\frac{PR(v_j)}{L(v_j)},\ i=1,2,\cdots,n
$$

这里 $M(v_i)$ 表示指向结点 $v_i$ 的结点集合， $L(v_j)$ 表示结点 $v_j$ 连出的有向边的个数。根据马尔可夫平稳分布定理，强连通且非周期的有向图上定义的随机游走模型（马尔可夫链），在图上的随机游走当时间趋于无穷时状态分布收敛于唯一的平稳分布。即 PageRank 存在，而且可以通过不断迭代求得 PageRank 值。

但一般的有向图未必满足强连通且非周期性的条件。例如互联网中，大部分网页没有链接出去的超链接，也就是说从这些网页中无法跳转到其他网页。表现到基本定义中就是，随着时间推移，转移矩阵各个结点的概率皆变为 0。所以 PageRank 基本定义不适用。

5 PageRank 的一般定义

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

给定一个含有 $n$ 个结点 $v_i,\ i=1,2,\cdots, n$ ，的任意有向图，假设考虑一个在图上随机游走模型，即一阶马尔可夫链，其转移矩阵是 $M$，从一个结点到其连出的所有结点的转移概率相等，这个马尔科夫链未必具有平稳分布。假设考虑另一个完全随机游走的模型，其转移矩阵的元素全部为 $1/n$，也就是说从任何一个结点到任意一个结点的转移概率都是 $1/n $。两个转移矩阵的线性组合又构成一个新的转移矩阵，在其上可以定义一个新的马尔科夫链。容易证明这个马尔科夫链一定具有平稳分布，且平稳分布满足
$$
R = dMR+\frac{1-d}{n}1
$$
其中 $d(0\le d\le 1)​$ 是系数，称为阻尼因子（damping factor），$R​$ 是 $n​$ 维向量，$1​$ 是所有分量为 1 的 $n​$ 维向量。$R​$ 表示的就是有向图的一般 PageRank。
$$
R=
\left[
\begin{matrix}
PR(v_1)\\
PR(v_2)\\
\vdots\\
PR(v_n)
\end{matrix}
\right]
$$
其中 $PR(v_i),i=1,2,\cdots,n$ 表示结点 $v_i$ 的 PageRank 值。

进而可得一般定义下的 PageRank 中每个结点的 PR 值：
$$
PR(v_i) = d\Big(\sum_{v_j\in M(v_i)}\frac{PR(v_j)}{L(v_j)}\Big)+\frac{1-d}{n},\ i=1,2,\cdots,n
$$
这里 $M(v_i)​$ 表示指向结点 $v_i​$ 的结点集合， $L(v_j)​$ 表示结点 $v_j​$ 连出的有向边的个数。

第二项称为平滑项，由于采用平滑项，所有结点的 PageRank 值都不会为 0，具有以下性质：
$$
PR(v_i)\ge0,\ i=1,2,\cdots,n
$$

$$
\sum_{i=1}^nPR(v_i)=1
$$

综上，可得 PageRank 的一般定义：

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

一般 PageRank 的定义意味着互联网浏览者，按照以下方法在网上随机游走：

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

6 PageRank 的计算

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

6.1 迭代算法

给定一个含有 $n$ 个结点的有向图，转移矩阵为 $M$，有向图的一般 PageRank 由迭代公式
$$
R_{t+1} = dMR_t + \frac{1-d}{n}1
$$
的极限向量 $R$ 确定。

PageRank 的迭代算法就是按照这个一般定义进行迭代，直至收敛，具体步骤如下：

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

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

(1) 令 $t=0$

(2) 计算
$$
R_{t+1} = dMR_t + \frac{1-d}{n}1
$$
(3) 如果 $R_{t+1}$ 与 $R_t$ 充分接近，令 $R = R_{t+1}$，停止迭代

(4) 否则，令 $t=t+1$ ，执行步 (2)

6.2 幂法

幂法（power method）是一个常用的 PageRank 计算方法，通过近似计算矩阵的主特征值和主特征向量求得有向图的一般 PageRank。幂法详见文章 幂法介绍。

使用幂法计算一般 PageRank 时，可以将转移矩阵写作
$$
R = (dM+\frac{1-d}{n}\Bbb E)R = AR
$$
其中 $\Bbb E$ 是所有元素均为 1 的 $n$ 阶方阵。根据 Perron-Frobenius 定理，一般 PageRank 的向量 $R$ 矩阵 $A$ 的主特征向量，主特征值是 1，因此可以使用幂法近似计算一般 PageRank。

一般 PageRank 的幂法计算：

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

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

(1) 令 $t=0$，选择初始向量 $x_0$

(2) 计算有向图的一般转移矩阵 $A$
$$
A = dM+\frac{1-d}{n}\Bbb E
$$
(3) 迭代并规范化结果向量
$$
y_{t+1} = Ax_t
$$

$$
x_{t+1} = \frac{y_{t+1}}{||y_{t+1}||}
$$

(4) 当 $||x_{t+1}-x_t||\lt \epsilon$ 时，令 $R=x_t$，停止迭代

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

(6) 对 $R$ 尽心规范化处理，使其各分量之和为1，以能够表示概率分布。

6.3 代数算法

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

按照一般 PageRank 的定义式
$$
R = dMR + \frac{1-d}{n}1
$$
于是，
$$
(I-dM)R = \frac{1-d}{n}1
$$

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

这里 $I$ 是单位矩阵。当 $0\lt d\lt 1$ 时，上述线性方程组的解存在且唯一。这样，可以以通过求逆矩阵 $I-dM^{-1}$ 得到有向图的一般 PageRank。