进击数据挖掘十大算法(七):PageRank

引言

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

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

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

一、随机游走模型

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

$$M=[m_{ij}{]}_{n\times n}$$

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

注意转移矩阵具有性质：

$$m_{ij}\ge 0 且 \sum _{i=1}^n{m}_{ij}=1$$

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

随机游走在某个时刻 $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$$

则极限

$$\underset{t\to \mathrm{\infty }}{lim}{M}^t{R}_0=R$$

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

$$MR=R$$

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

$$MR=R$$

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

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

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

显然有

$$PR(v_i)\ge 0，i=1,2,\cdots ,n$$

$$\sum _{i=1}^{n}PR(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$ 连出的有向边的个数。

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

三、PageRank的一般定义

一般的有向图未必满足强连通且非周期性的条件。比如在互联网，大部分网页没有连接出去的超链接，也就是说从这些网页无法跳转到其他网页，所以$PageRank$ 的基本定义不适用（因为这种情况下某结点状态转移全为0，导致收敛结果全是0）。

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

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

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

式中 $d(0\le d\le 1)$ 是系数，称为阻尼因子，$R$ 是 $n$ 维向量，$1$ 是所有分量为1的 $n$ 维向量。$R$ 表示的就是有向图的一般 $PageRank$。

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

$PageRank$ 的一般定义由于采用平滑项，所有结点的PageRank值都不会为0，具有以下性质：

$$PR(v_i)>0，i=1,2,\cdots ,n$$

$$\sum _{i=1}^{n}PR(v_i)=1$$

四、PageRank的计算

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

4.1 迭代算法

给定一个含有 $n$ 个结点的有向图，转移矩阵为 $M$，有向图的一般 $PageRank$ 由迭代公式

$$R_{t+1}=dM{R}_t+\frac{1-d}{n}1$$

的极限向量 $R$ 确定。

$PageRank$ 的迭代算法，就是按照这个一般定义进行迭代，直至收敛。

算法4.1      ($PageRank$ 的迭代算法)

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

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

• 1. 令 $t=0$
• 2. 计算

  $$R_{t+1}=dM{R}_t+\frac{1-d}{n}1$$

• 3. 如果$R_{t+1}$ 与 $R_t$ 充分接近，令 $R=R_{t+1}$，停止迭代。
• 4. 否则，令 $t=t+1$，执行步骤(2)。

4.2 幂法

幂法(power method)是一个常用的 $PageRank$ 计算方法，通过近似计算矩阵的主特征值和主特征向量求得有向图的一般 $PageRank$。

幂法主要用于近似计算矩阵的主特征值和主特征向量。主特征值是指绝对值最大的特征值，主特征向量是其对应的特征向量。注意特征向量不是唯一的，只是其方向是确定的，乘上任意系数还是特征向量。

假设要求 $n$ 阶矩阵 $A$ 的主特征值和主特征向量，采用下面的步骤。

首先，任取一个初始的 $n$ 维向量 $x_0$，构造如下的一个 $n$ 维向量序列

$$x_0,x1=A{x}_0,x2=A{x}_1,\cdots ,x_k=A{x}_{k-1}$$

然后，假设矩阵 $A$ 有 $n$ 个特征值，按照绝对值大小排列

$$|{\lambda }_1|\ge |{\lambda }_2|\ge \cdots \ge |{\lambda }_n|$$

对应的 $n$ 个线性无关的特征向量为

$$u_1,u_2,\cdots ,u_n$$

这 $n$ 个特征向量构成 $n$ 维空间的一组基。

于是，可以将初始向量 $x_0$ 表示为 $u_1,u_2,\cdots ,u_n$ 的线性组合

$$x_0=a_1{u}_1+a_2{u}_2+\cdots +a_n{u}_n$$

得到

$$x_1=A{x}_0=a_{1}A{u}_1+a_{2}A{u}_2+\cdots +a_{n}A{u}_n$$

$$⋮$$

$$x_k=A^k{x}_0=a_1{A}^k{u}_1+a_2{A}^k{u}_2+\cdots +a_n{A}^k{u}_n$$

$$=a_1{\lambda }_1^k{u}_1+a_2{\lambda }_2^k{u}_2+\cdots +a_n{\lambda }_n^k{u}_n$$

接着，假设矩阵 $A$ 的主特征值 ${\lambda }_1$ 是特征方程的单根，由上式得

$$x_k=a_1{\lambda }_1^k[u_1+\frac{a_2}{a_1}(\frac{{\lambda }_2}{{\lambda }_1}{)}^k{u}_2+\cdots +\frac{a_n}{a_1}(\frac{{\lambda }_n}{{\lambda }_1}{)}^k{u}_n]$$

由于 $|{\lambda }_1|>|{\lambda }_j|,j=2,\cdots ,n$，当 $k$ 充分大时有

$$x_k=a_1{\lambda }_1^k[u_1+{ϵ}_k]$$

这里 ${ϵ}_k$ 是当 $k\to \mathrm{\infty }$ 时的无穷小量， ${ϵ}_k\to 0(k\to \mathrm{\infty })$。即

$$x_k\to a_1{\lambda }_1^k{u}_1(k\to \mathrm{\infty })$$

说明当 $k$ 充分大时向量 $x_k$ 与特征向量 $u_1$ 只相差一个系数。由上式可知

$$x_k\approx a_1{\lambda }_1^k{u}_1$$

$$x_{k+1}\approx a_1{\lambda }_1^{k+1}{u}_1$$

于是主特征值 ${\lambda }_1$ 可表示为

$${\lambda }_1\approx \frac{x_{k+1,j}}{x_{k,j}}$$

其中 $x_{k,j}$ 和 $x_{k+1,j}$分别是 $x_k$ 和 $x_{k+1}$ 的第 $j$ 个分量。

在实际计算时，为了避免出现绝对值过大或过小的情况，通常在每步迭代后即进行规范化，将向量除以范数，即

$$y_{t+1}=A{x}_t$$

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

现在回到计算一般 $PageRank$。

转移矩阵可以写作

$$R=(dM+\frac{1-d}{n}E)R=AR$$

其中 $d$ 是阻尼因子，E是所有元素为1的 $n$ 阶方阵。根据 Perron-Frobenius 定理，一般 $PageRank$ 的向量 $R$ 是矩阵 $A$ 的主特征向量，主特征值是1。所以可以使用幂法近似计算一般 $PageRank$。

算法4.2      (计算一般$PageRank$ 的幂法)

输入：含有 $n$ 个结点的有向图，有向图的转移矩阵 $M$，系数 $d$，初始向量 $x_0$，计算精度 $ϵ$；

输出：有向图的 $PageRankR$

• 1. 令 $t=0$，选择初始向量 $x_0$
• 2. 计算有向图的一般转移矩阵 $A$

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

• 3. 迭代并规范化结果向量

  $$y_{t+1}=A{x}_t$$

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

• 4. 当 $||x_{t+1}-x_t||<ϵ$时，令 $R=x_t$，停止迭代
• 5. 否则，令 $t=t+1$，执行步(c)
• 6. 对 $R$ 进行规范化处理，使其表示概率分布

4.3 代数算法

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

按照一般 $PageRank$ 的定义式

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

于是，

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

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

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

五、Reference

• 李航《统计学习方法》