PageRank的秘密

PageRank的秘密

(2011-09-23 22:46:09)

from http://blog.sina.com.cn/s/blog_68ffc7a40100u88z.html

PageRank算法是Google于1998年提出来的，是早期搜索引擎的著名算法，这和Google的名人效益不无关系。作为一名软件工程师，这么有名的算法怎么能不知道呢？这篇博客就来仔细讲讲PageRank是怎么回事。

PageRank算法是用来对互联网网站进行排名，它将整个互联网上的网站看做一个个节点，很多网站都会有一些超链接，该超链接指向别的网站，这样的话整个互联网就抽象成了一个有向图的模型。PageRank算法的思想非常巧妙，它来自于社交网络中的投票，网站的外链接可以被视为对其它网站的投票，如果一个网站获得的票数越多，那么该网站的内容就被认为越权威，那么该网站的排名应该靠前。PageRank的思想就是这么简单，它其实借鉴了社交网络中的一些思想。

有了思想，接下来就是来看具体的算法了。先看几个定义：

网页i的In-link：别的网页链到网页i的链接。实际上就是网页i的入度

网页i的Out-link：网页i上的外部链接，这就是网页i的出度。

整个互联网模型可以表示为G=（V，E），V表示顶点，E表示边。顶点的个数为n，也就是网站的个数为n，就有n=|V|。我们的目标就是计算每个网站i的评分P（i），有了评分进行排序就可以得到网站的Rank。评分的公式定义如下：

公式1

表示网页j的出度个数。其实该公式的本质含义就是，一个网页i的分数实际上是所有给i投过票的网页j的分数之和，当然这不是简单的相加求和，每个分数还要乘个系数，这个系数就是该网页出度的倒数。这个也很好理解啦:网站j有种可能到别的网页，每种可能发生的概率都相等，所以分数就要除以一个啦。该公式是不是非常得make sense？

我们定义P，P是一个n维列向量，每个分量代表一个网页的PageRank的分数，如下：

那么根据公式1，我们可以定义整个互联网G的邻接矩阵A如下

那么评分公式公式1就可以表示成

公式2

看到这个公式，敏感的同学可能马上就意识到了，这么就是特征向量系统么，很显然P就是矩阵的一个特征向量，该特征向量对应的特征值为1。这是一个循环定义，迭代法可以解决类似的问题。如果公式2能够满足特定的条件，那么P就是的主特征向量，且其对应的特征值为1,1为最大的特征值，P是最大特征值对应的特征向量。那么一旦该条件满足，我们就可以使用幂迭代法来求得特征向量。下面来讨论下这些条件具体是什么。

三个条件

公式2要成立，那么必须满足3个条件：A是随机过程矩阵，A是不可化简的，A是非周期的。下面来详细讨论下。

条件1

A是随机过程矩阵。根据公式2，其实我们会联想到想到它其实是一个马尔科夫模型，每个网页就是一个状态，网页上的链接可以认为是一个转化，该转化使我们能够从一个网页以一定的概率跳转到另外一个状态。如果A是随机过程，那么矩阵中每一行中的元素一定是一个非负数，并且这些元素加起来的和一定是1。很显然，A并不满足。试想一下，有些网站可能没有任何链接，同时也没有任何其它的网页链接到该网页，这样A中某些行就是一个全0的行，这就违背了A是随机过程的特性。所以A并非一个随机过程矩阵。那么我们就要想办法把这个非随机过程矩阵变成随机过程矩阵，那该怎么做呢？把那全为0的那些元素的行里的元素的值全部变成1/n。这种做法其实也是很有道理的，一个页面如果没有任何链接链到其它页面，那么我们可以认为从该页面有可能跳到任何其它一个页面，跳转概率为1/n。举例子，比如下面这个转移矩阵

公式3

从第5行来看，该矩阵不是一个随机过程举证。那么按照前面的方法变一下如下：

公式4

这就变成了一个随机过程矩阵。

条件2

所谓A是不可化简的，其意义就是A代表的是一个强连通图（任意两点之间都有一条路径）。那么大部分情况下，A显然未必是一个强连通图。

条件3

A是非周期的。矩阵A的周期性是什么意思呢？这里解释一下，对于马尔科夫模型中的每一个状态i，从状态i经过一系列的路径可以又返回状态i，从状态i返回状态i并不是只有一条路径，可能有很多条不同的路径，这些路径有不同的长度，如果这些长度的数值存在一个最小公约数k，且k>1，那么我们就可以说状态i是周期性的，且周期是k。如果马尔科夫模型A中的所有状态都是周期性的，那么我们就可以说马尔科夫链A也是周期性的.给出一个周期性的例子，如下

实际上，一个周期性的马尔科夫转移矩阵往往是一个每一行和每一列只有一个1的矩阵，这个矩阵实际构成的是一个环。这种环在实际的网络拓扑模型中是经常出现的。所以A是非周期性的假设也是不成立的。

怎样确保条件2，条件3一定满足呢？PageRank对公式2进行了一个近似，其表达式如下

公式5

其中d是一个在0,1之间相对较大的参数，E是一个n*n的全1矩阵。其本质上是在的所有元素加上了一个很小的概率，这样就变成了一个没有0元素的矩阵，也就是一个全连通矩阵。一个全连通矩阵，也一定是一个非周期矩阵（这可能有一点难于理解，试着想象一下，一个全连通图，任意两点之间都有边，那么任意一点返回路径的长度会有1,2...n，这些长度显然找不到一个最小公约数，也就不是周期矩阵）。全连通矩阵显然也是一个强连通矩阵，这就不用再说了吧。

那么通过把公式2近似得变化成公式5，那么就圆满的解决了3个条件假设的问题，我们就可以用幂迭代法来求公式5的主特征向量。那么接下来的问题就是如何来求矩阵的特征向量？答案就是幂法求特征向量。下面就来回顾一下大学矩阵论的课程，如果来求一个矩阵的特征向量。

首先来看看特征向量的定义。定义：若数与非零向量x满足

则称为方阵A的特征值，x是A的特征向量。

A是n阶方阵，那么它有n个特征值，假设其特征值大小排列如下

公式7

其对应的n个无关的正交的特征向量为x1,x2,...xn，他们满足

好，我们取任意非零向量u0,从它出发，做下面的迭代

这个迭代过程产生了一个向量的序列{uk}.我们由上面的条件很容易得到下面的迭代公式

由于x1,x2,...xn线性无关，那么u0就可以由这些线性无关的向量表达，就有

那么

公式6

根据公式7，由于最大，那么有如果k充分大时，就有

公式8

由于x1是特征向量，uk是x1的常数倍，那么uk也是特征向量，可以近似得看成对应的特征向量。好了，问题解决了。通过从u0的不断迭代就可以得到最大特征值对应的特征向量。

根据公式8，你会发现，如果大于1(或小于1)时，在k充分大的情况下，uk的模就会过大（或过小），这往往会造成计算机出现上溢或下溢.那么如何解决这个问题呢？答案是对向量进行单位化处理。具体的推导请参考文献[1]的page 8。该文献给出了比较详细的推理证明，有兴趣的读者可以看一看。最终的算法伪码如下

对于pagerank，我们知道其矩阵A满足随机过程性，不可化简性，非周期性，因此公式5中的P对应的是矩阵A最大的特征值对应的特征向量，且这个特征值为1.由于最大的特征值为1，所以通用一般的幂迭代法不会造成计算机上下溢，因此不用单位化。其算法如下

 

好了，P求出来了，那么所有网站的评分也就得出来了，pagerank算法也就完成了。

pagerank的改进

最基本的pagerank算法是静态的，其评分只考虑网页的链接。但是仅仅这么考虑可能略有不足，如果加上时间因素可能这个模型就更加完备了。因为我们可能希望找到最新的高质量网站，一些网站链接的确比较多，质量比较高，但由于更新时间比较久远，可能也不希望它的分数那么高。于是Timed-PageRank就被提出来了。该算法的关健在于控制因子d，我们用f(t)来代替d，我们用f(t)来“惩罚”那些老网页。f(t)这里是一个关于时间的函数

f(ti)代表用户从页面i通过点击一条外部链接跳转出去的概率

1-f(ti)代表用户不通过外部链接，而是随机跳转到其它任意网页的概率。

因此我们为每一个网页定义一个合适的f(t)，如果该网页是比较老的网页，1-f(t)应该设置的比较大，这意味着这些网页比较过时，人们从不太会从这个网页上通过点击该网页上的外部链接来进行网页跳转。反之如果网页是比较新的网页，1-f(t)应该设置的比较小。对于一个完全新的网页，它可能没有任何的in-link，那么我们给这个新的网页一个该默认的评分，该评分是该网站过去的页面评分的平均值。这个做法非常make sense，因为一个生产过质量高的网页的网站新生产的网页的质量可能也比较高。

Timed-PageRank的核心思想就是选择合适的f(t)来代替d，其它和基本的pagerank算法是一样的。

pagerank算法其实也可以用来对社交网络进行rank，比如在facebook这样的社交网络中，我们可以用pagerankk找出那些最有影响力的那些人，也就是所谓的意见领袖。这是很有意义的。

参考文献

[1]辽宁工业大学数值分析 朱广振第三章 p5. http://wenku.baidu.com/view/ac84983987c24028915fc300.html?from=related

[2]The Top Ten Algorithm in Data Mining