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

1 基本概念

（1）简介

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

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

（2）随机游走模型

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

M = [ m i j ] n × n M = [m_{ij}]_{n×n} M=[mij​]n×n​

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

注意转移矩阵具有性质：

m i j ≥ 0 m_{ij} \geq 0 mij​≥0

∑ i = 1 n m i j = 1 \sum_{i=1}^n m_{ij} = 1 ∑i=1n​mij​=1

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

在以上有向图上定义随机游走模型。结点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 R_t Rt​表示，那么时刻t+1访问各个结点的概率分布 R t + 1 R_{t+1} Rt+1​满足

R t + 1 = M R t R_{t+1} =MR_{t} Rt+1​=MRt​

2 基本定义

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

平稳分布R称为这个有向图的PageRank，R的各个分量称为各个结点的PageRank值。 R = [ P R ( v 1 ) P R ( v 2 ) . . . P R ( v n ) ] (3) R = \left[ \begin{matrix} PR(v_1) \\ PR(v_2) \\ ...\\ PR(v_n) \end{matrix} \right] \tag{3} R=⎣⎢⎢⎡​PR(v1​)PR(v2​)...PR(vn​)​⎦⎥⎥⎤​(3) 其中 P R ( v i ) , i = 1 , 2 , . . , n PR(v_i),i= 1,2,..,n PR(vi​),i=1,2,..,n，表示结点 v i v_i vi​的PageRank值。显然有 P R ( v i ) ≥ 0 , i = 1 , 2 , . . , n ∑ ｉ = 1 n ＝ 1 P R ( v i ) = ∑ v j ∈ M ( v j ) P R ( v j ) L ( v j ) , i = 1 , 2 , 3 , . . . , m PR(v_i) \geq 0,i=1,2,..,n\\ \sum_{ｉ=1}^n＝1\\ PR(v_i) = \sum_{v_j \in M(v_j) }\frac{PR(v_j)}{L(v_j)},i= 1,2,3,...,m PR(vi​)≥0,i=1,2,..,nｉ=1∑n​＝1PR(vi​)=vj​∈M(vj​)∑​L(vj​)PR(vj​)​,i=1,2,3,...,m

这里的 M ( v i ) M(v_i) M(vi​)表示结点 v i v_i vi​的结点集合， L ( v j ) L(v_j) L(vj​)表示结点 v j v_j vj​连出的有向边的个数。

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

3 一般定义

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

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

一般PageRank的定义 P R ( v i ) = d ( ∑ v j ∈ M ( v i ) P R ( v j ) L ( v j ) ) + 1 − d n , i = 1 , 2 , . . , n PR(v_i) = d(\sum_{v_j\in M(v_i)} \frac{PR(v_j)}{L(v_j)})+ \frac{1-d}{n},i= 1,2,..,n PR(vi​)=d(vj​∈M(vi​)∑​L(vj​)PR(vj​)​)+n1−d​,i=1,2,..,n

这里的 M ( v i ) M(v_i) M(vi​)是指向结点 v i v_i vi​的结点集合， L ( v j ) L(v_j) L(vj​)是结点 v j v_j vj​连出的边的个数。

第二项称为平滑项，由于采用平滑项，所有结点的pagerank值都不会为0，具有以下性质。 P R ( v i ) > 0 , i = 1 , 2 , 3 , . . . , n ∑ i = 1 n P R ( v i ) = 1 PR(v_i) >0,i=1,2,3,...,n\\ \sum_{i=1}^n PR(v_i) = 1 PR(vi​)>0,i=1,2,3,...,ni=1∑n​PR(vi​)=1 一般Pagerank的定义意味着互联网浏览者，按照以下方法在网上随机游走：

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

4 Pagerank的计算 4.1 迭代计算法

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

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

算法过程

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

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

（1）令t=0

（2）计算 R t + 1 = d M R t + 1 − d n 1 R_{t+1} =dMR_t + \frac{1-d}{n}1 Rt+1​=dMRt​+n1−d​1 （3）如果 R t + 1 R_{t+1} Rt+1​与 R t R_t Rt​充分接近，令 R = R t = 1 R = R_{t=1} R=Rt=1​，停止迭代。

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

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

解：从图21.4得知转移矩阵为 R = [ 0 1 / 2 0 0 1 / 3 0 0 1 / 2 1 / 3 0 1 1 / 2 1 / 3 1 / 2 0 0 ] (3) R = \left[ \begin{matrix} 0 & 1/2 & 0 & 0 \\ 1/3 & 0 & 0 & 1/2 \\ 1/3 & 0 & 1 & 1/2\\ 1/3 & 1/2 & 0 & 0\\ \end{matrix} \right] \tag{3} R=⎣⎢⎢⎡​01/31/31/3​1/2001/2​0010​01/21/20​⎦⎥⎥⎤​(3)

4.2 幂法

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

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

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

算法过程

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

输出：有向图的PageRankR 。

（1）令t=0，选择初始向量 x 0 x_0 x0​

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

A = d M + 1 − d n E A = dM +\frac{1-d}{n}E A=dM+n1−d​E

（3）迭代并规范化结果向量 y t + 1 = A x t x t + 1 = y t + 1 ∣ ∣ y t + 1 ∣ ∣ y_{t+1} =Ax_t x_{t+1} = \frac{y_{t+1}}{|| y_{t+1} ||} yt+1​=Axt​xt+1​=∣∣yt+1​∣∣yt+1​​ （4）当 ∣ ∣ x t + 1 − x t ∣ ∣ ϵ ||x_{t+1}- x_t|| \epsilon ∣∣xt+1​−xt​∣∣ϵ时，令R= x，停止迭代。

（5）否则，令t = t+1，执行步（3）

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

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

4. 3 代数算法

代数算法通过一般转移矩阵的逆矩阵计算求有向图的一般PageRank。按照一般PageRank的定义 R = d M R + 1 − d n 1 R = dMR +\frac{1-d}{n}1 R=dMR+n1−d​1

于是， ( I − d M ) R = 1 − d n 1 R = ( I − d M ) − 1 1 − d n 1 (I - dM)R = \frac{1-d}{n}1 \\ R = (I-dM)^{-1}\frac{1-d}{n}1 (I−dM)R=n1−d​1R=(I−dM)−1n1−d​1 这里I是单位矩阵，当 0 < d < 1 0