【数据挖掘】十大算法之PageRank连接分析算法

1 基本概念

（1）简介

Pagerank算法是基本想法是互联网网页重要度的计算方法。PageRank可以定义在任意有向图上，后来被应用到社会影响力分析、文本摘要等多个问题。

PageRank算法的基本思想是在有向图上定义一个随机游走模型，即一阶马尔科夫链，描述随机游走者沿着有向图随机访问各个节点的行为。在一定的条件下，基线情况访问每个节点的概率收敛到平稳分布，这时各个节点的平稳概率值就是其PageRank值，表示节点的重要度。

（2）随机游走模型

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

$$M = \left[\begin{array}{ccc} m_{ij} \end{array}\right]_{n\times n}$$

第i行第j列的元素 m i j m_{ij} mij​取值规则如下：如果结点j有k个有向边连出，并且结点i是其连出的一个结点，则
$$\begin{equation} m_{ij} = \frac{1}{k} \end{equation}$$
否则
$$\begin{equation} m_{ij} = 0,1,j=1,2,...,n。 \end{equation}$$
注意转移矩阵具有性质：
$$\begin{equation} m_{ij} ≥0\end{equation}$$
$$\begin{equation} \sum_{i=1}^{n} m_{ij} = 1 \end{equation}$$

即每个元素非负，每列元素之和为1，即矩阵M为随机矩阵。在有向图上是随机游走形成马尔科夫链，也就是说，随机游走者每经一个单位时间转一个状态，如果当前时刻在第j个结点，那么下一个时刻在第i个结点的概率是m_ij​，这一概率只依赖于当前的状态，与过去无关，具有马尔科夫性。

在以上有向图上定义随机游走模型。结点A到B、C和D存在有向边。A以1/2的概率转移到B，100%的概率转移到C，B以1/3的概率转移到A，以1/2概率转移到D ，C以1/3的概率转移到A，1/2的概率转移到D，D以1/3的概率转移到A，1/2的概率转移到B。得到转移矩阵

随机游走在某个时刻t访问各个结点的概率分布就是马尔科夫链在时刻t的状态分布，可以用一个n维列向量 R_t表示，那么时刻t+1访问各个结点的概率分布 R_t+1​满足

R_t+1=MR_t

2 基本定义

给定一个包含n个结点的 v 1 , v 2 , . . , v n v_1,v2,..,v_n v1​,v2,..,vn​的强联通且非周期的有向图，在有向图上定义随机游走模型，即一阶马尔科夫链。随机游走的特点是从一个结点到有有向边的转移概率相等，转移矩阵为M，这个马尔科夫链具有平稳分布R。MR = R

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

3 一般定义

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

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

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

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

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

4 Pagerank的计算

4.1 迭代计算法

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

的极限向量R确定。

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

算法过程

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

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

（1）令t=0

（2）计算

（3）如果 R_t+1​与R_t​充分接近，令R = R_t=1​​，停止迭代。

（4）否则，令t = t+1，执行步骤（2）

举例：给定有向图，取d = 0.8，求图的PageRank。

解：从图21.4得知转移矩阵为

4.2 幂法

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

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

转移矩阵写作

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

算法过程

输入：含有n个结点的有向图，有向图的转移矩阵M，系数d，向量x₀​，计算精度 ϵ：

输出：有向图的PageRankR 。

例子：给定一个如图所示的有向图，取d = 0.85，求有向图的一般PageRank。

4. 3 代数算法