PR值：PagePank算法

一、基本算法

1、基本步骤

PagePank算法的基本思想是：WWW上一个页面的重要性取决于指向它的其它页面的数量和质量。针对一般的有向网络，基本的PagePank算法可叙述如下：
（1）初始步：给定所有节点的初始PagePank
值PR${}_i$（0），i=1，2，，，N，满足${\sum }_1^N$PR${}_i$（0）=1。
（2）基本的PagePank校正规则：把每个节点在第k-1步时的PR值平分给它所指向的节点。也就是说，如果节点i的出度为k${}_i^{out}$，那么节点i所指向的每一个节点分得的PR值为PR${}_i$（k-1）/k${}_i^{out}$。如果一个节点的出度为0，那么它就始终把PR值只给自己。每个节点的新的PR值校正为它所分得的PR值之和，即有

注意在上述算法中，所有节点的PR值之和总是不变的，因此，无需向HITS算法一样每一步都做归一化处理。
上式表明，一个节点的重要性是指向它的节点的重要性的加权组合。
在有向网络的邻接矩阵A=（a${}_{ij}$）${}_{N\times N}$基础上定义基本Google矩阵$\bar{A}$=（${\bar{a}}_{ij}$）${}_{N\times N}$如下：

那么，基本的PagePank校正规则可以写为如下的校正形式：

上式就是求解矩阵$\bar{A}$的与模最大的特征值对应的主特征向量的幂法，并且有：


上图所示的网络对应的基本Google矩阵$\bar{A}$为：

假设每个节点初始的PR值均为1/8，当迭代步数增加时每个节点的PR值会趋于上上图中每个节点旁边的分数所示的稳态PR值。

2、算法缺陷

我们从复杂网络上的随机行走的观点来解释基本的PagePank算法，从而发现它存在的问题：首先，完全随机的选择一个初始节点；然后，每次都是从当前节点出发，在从该节点指出去的边中随机选择一条边并沿着这条边到达另一个节点。可以证明，随机行走k步后位于节点i的概率就等于应用基本PagePank算法k步后所得到的节点i的PR值。
上述行走规则的缺陷在于：一旦到达某个出度为0的节点，就会永远停留在该节点而无法在走出来。出度为0的节点也称为悬挂节点，这些节点的存在会使得基本的PagePank算法失效。
更为一般的，如果网络中存在一些没有指出边的子图，那么这些子图中的节点有可能”吸尽“网络中所有的PR值。

3、缺陷处理

对于悬挂节点的处理有一种简单的办法：假设一旦到达一个出度为0的页面，那么就以相同概率1/N随机访问网络中的任一页面。从数学上看，这相当于把基本Google矩阵$\bar{A}$中的全零行替换为每个元素均为1/N的行。我们称这种修正为随机性修正，因为修正后的Google矩阵是每一行的元素之和都为1的行随机矩阵，其元素为：

二、PagePank算法

1、PagePank算法收敛性问题

上述针对悬挂节点的随机性修正并没有完全解决基本的PagePank算法收敛性问题。事实上，即使网络上没有出度为0的悬挂节点，甚至即使网络是强连通的，基本的PagePank算法也仍然有可能失效。

例如上图中由5个节点组成的环状网络，对应的基本Google矩阵满足：


从上表可以看出，如果初始PR的值取为PR(0)=[1,0,0,0,0]${}^T$,那么经过5次迭代后PR值又回到了初值，也就是说，算法将不停的循环而无法收敛。

2、收敛性问题的解决

解决基本的PagePank算法收敛性的有效办法是：从当前页面出发，不管该页面是否为悬挂页面，都允许以一定概率随机选取网络中的任一页面作为下一步要浏览的页面。
针对一般的有向网络，相应有如下的修正的随机行走规则：
完全随机地选择一个初始节点。如果当前所在节点的出度大于零，那么以概率s(0<s<1)在指出去的边中随机选择一条边并沿着该边到达下一个节点，以概率1-s在整个网络上完全随机选择一个节点作为下一步要到达的节点。如果当前所在节点的出度等于零，那么完全随机选择一个节点作为下一步要到达的节点。

3、修正后的PagePank算法

基于上述修正的随机行走思想，修正的PagePank算法如下：
（1）（1）初始步：给定所有节点的初始PagePank
值PR${}_i$（0），i=1，2，，，N，满足${\sum }_1^N$PR${}_i$（0）=1。
（2）修正的PagePank校正规则：给定一个标度常数s$\in$（0，1）。首先按照基本的PagePank校正规则计算各个节点的PR值，然后把每个节点的PR值通过比列因子s进行缩减。这样，所有节点的PR值之和也就缩减为s，再把1-s平均分给每个节点PR值，以保持网络总的PR值为1，即有

可以证明：基于修正的随机行走规则行走k步后位于节点i的概率就等于应用PagePank校正规则k步后所得的节点i的PR值。
PagePank校正规则的矩阵形式如下：

其中，

注意到不管网络连通性如何，$\bar{A}$是一个非负矩阵，从而$\tilde{A}$是一个正矩阵。根据矩阵论理中的Perron-Frobenius定理，我们有如下结论：
（1）矩阵$\tilde{A}$的模最大的特征值为实特征值${\lambda }_i$>0，且有${\lambda }_i$>|${\lambda }_i$|，i=2，3，，N。
（2）与特征值${\lambda }_i$对应的单位特征向量PR${}^{\ast }$(||PR${}^{\ast }$||${}_1$=1)的元素全为正。
（3）如果矩阵$\bar{A}$是行随机矩阵，那么$\tilde{A}$也是行随机矩阵。在此情形，${\lambda }_1$=1，对于任意的非零和非负的单位初始向量，PagePank校正规则计算得到的PR(k)当k->$\infty$时收敛得到PR${}^{\ast }$。

三、排序鲁棒性及网络结构

通过分析网络结构对PagePank算法计算得到的PR值得影响，发现均匀得随机网络中节点的PR值的影响，发现均匀的随机网络中节点的PR值排序对网络扰动较为敏感，而非均匀的无标度网络中会涌现个别超稳定的PR值最大的节点，它们在按照PR值排序中的位置对于网络扰动具有很高的鲁棒性。这项研究考虑的是在保持每个节点的度值不变的情况下。

总结

以上是生活随笔为你收集整理的PR值：PagePank算法的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。