数据挖掘十大经典算法（六）-----PageRank

简介

PageRank，网页排序；通过网络浩瀚的超链接关系来确定一个页面的等级。借鉴依靠文章的引用情况判断学术论文的质量的相关思想。

网页排序的核心思想：

（1）如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是pageRank值会相对较高；

（2）如果一个pagerank值很高的网页链接到一个其他的网页，那么链接到的网页的pageRank值会相应的因此提高；

计算

每个网页PR值的定义：一个网页的排名等于所有链接到该网页的网页的加权排名之和：,其中代表第i个网页的PageRank值，用来衡量网页的排名。排名越高，则PR值越大。网页之间的链接关系可以表现为一个有向图,边（ j , i ）代表网页 j 链接到了网页 i ；为网页j的出度，也看做网页 j 的外链数。

假设为 n 维PageRank值向量，A 为有向图 G 所对应的转移矩阵，, (表示由网页 i 跳到网页 j 的概率)，n 个等式可以写成矩阵相乘：。由于当前网页的PR值由其依赖网页的PR值计算的出，针对此问题采用power iteration来解决；即先给定P一个初始值（假设现共有N个网页，则初始阶段用户访问每个网页的概率为，初始向量则为（，，......,）），然后通过多轮迭代求解：，最后收敛于，即差别小于某个阈值。其中为一个特征方程，并且P是当特征值为1 时的特征向量，为了满足方程是有解的，则转移矩阵A必须满足以下三个条件：

• 随机矩阵：所有，且所有列向量元素的和为1；
• 不可约：即A所对应的图是强连通的，即图中任何一个结点都可以到其他的一个结点；
• 非周期：即每个结点存在自回路；

终止点：一个网页没有链接到其他任何网页，即在概率转移矩阵上其中一列元素的值全部为0；如下图点C；

陷阱：一个网页只链接到自己，在概率转移矩阵的主对角线上，存在有一个元素为1的情况；如下图点C；

一般情况下，矩阵A这三个性质都不满足，为了解决陷阱和终止点的问题，假设用户在点击网页时，遇到陷阱或者终止点，会以一定的概率不点击网页中的链接而是在地址栏中输入新的网址来“逃离”当前网页，于是对转移矩阵进行修正：,其中为点击当前网页中的链接的概率，而为用户通过地址栏“逃离”的概率。的值不能太大，因为的大小与算法的收敛速度成反比；同时的值也不能太小，因为PR值的精华就在式中的前半部分，故的值被定位0.85。

算法优点：（1）是与查询无关的静态算法，所有网页的PR值都是离线计算好的；（2）有效减少了在线查询时的计算量，减少了查询的响应时间；

算法缺点：（1）没有区分站内导航链接；很多网站的首页都有很多对站内其他页面放入链接，成为站内导航链接，这些链接与不同网站之间的链接相比，后者更能体现PR值的传递关系；（2）没有过滤广告链接和功能链接（分享链接）；这些链接通常没有什么价值，前者链接到广告页面，而后者常常链接到某一个社交网站的首页；（3）对新网页不友好；一个新的网页的一般链入数相对较少，即使它的内容质量很高，要成为一个高PR值的网页仍需要很长时间的推广；