Google PageRank算法（转）

转载自：http://www.charlesgao.com/?p=157

 

 

Google应用PageRank算法给每个网站分配了一个从0～10的数字，它代表了一个网站的重要性。PageRank根据网页之间的超链接来确定一个页面的等级。大家在我博客的右边栏中搜索框的下方可以看到我博客的PageRank，也可以在一些信息查询网站上查询任意网站的PageRank。那么，这个数值是如何计算出来的呢？
其实，PageRank算法的计算过程可以形象的看作“投票”过程。比如我的网站上挂了Wikipedia的超链接，那么我就给Wikepedia投了一票，那么他的PageRank值就会升高。粗略的说，每个网站的PageRank值就是其他各个网站给它“投票”的总和。如果简单的把每一个网站所投的票都看成相同的，这样又会不公平。因为重要的网站所投的票应该有较大的分量。那么，如何确定哪个网站重要，哪个网站不重要呢？还是要根据PageRank。这就产生了一个看似矛盾的过程，我们需要用PageRank值来衡量一个网站的重要性，而它本身的计算中又需要用到PageRank值！
这听起来很像递归，或迭代。PageRank的算法正是基于这种思考产生的。
我们定义PR(A)为A网站的PageRank。为了叙述方便，我们不再使用google的0~10度量，而是使用0~1度量。这和概率的取值范围是一致的。事实上，PageRank就是一个概率(它反映了一个人在网络中不同的页面上随机点击链接会到达某个特定网站的概率)。只不过因为人们不太喜欢看小数，google才更改了度量。
在计算的开始，我们假设考虑的所有网站的PageRank是均匀分布的。这意味着，如果互联网上共有N个网站，那么每个网站的PageRank都是1/N。现在，假设我们仅仅考虑4个网站A,B,C,D组成的一个小网络。初始时，它们的PageRank都是1/4。假如B,C,D的网站上都有且仅有A的链接，那么它们每个人都为A贡献了0.25的PageRank。
（图1）
定义

则PR(A)=0.75
现在假设B网站上还有C的链接，网站D上有其它三个网站的链接。如下图所示：
（图2）
此时，对于B来讲，他把自己的总价值分散投给了两个网站A和C，那么每个网站就应该得到一半的PageRank，即0.125。只有1/3的PR(D)给了A。在这种情况下，

所以，按如此定义，一个网站X上有网站Y的链接，那么它给Y贡献的PageRank等于它的PageRank除以它网站的所有外部链接。（在这里我们做了一个假定，即X网站上对Y站的多个链接不重复计算。不难发现，这样的假定是很合理的。否则像http://worlds-highest-website.com/这样的一个网站上从头到尾全是www.charlesgao.com的链接，那我博客的PageRank就不会这么惨了。—–当然，这是不公平的。）
一个网站u的PageRank的普遍表达式为：

其中B_u是所有链接到u的网站的集合。v为相应网站所链接到的网站总数。
有一点值得注意的是：所有PageRank的计算是同时的。即在计算之前，类似上面的一个有向图已经确定了。然后所有网站的PageRank同时用上面这个公式计算。迭代过程如下：
初始：所有网站的PageRank均等
第一次迭代：每个网站得到了一个新的PageRank
第二次迭代：用这组新的PageRank再按上述公式迭代形成另一组新的PageRank
…
我们最关心的问题是：
如此迭代下去，这些网站的PageRank值最终会收敛么？
大家再回头看我们一开始提到的两个例子。对于图1所示的例子来说，很显然第二次迭代所有的PageRank就都是0了。过程如下：

	PR(A)	PR(B)	PR(C)	PR(D)
初始	0.25	0.25	0.25	0.25
第一次迭代后	0.75	0	0	0
第二次迭代后	0	0	0	0

图2所示的情况也将导致最后所有网站的PageRank变为0。因为没有网站链接到D，那么第一次迭代后PR(D)=0。这将导致PR(B)=0，继而导致PR(C)=0,and then PR(A)=0:

	PR(A)	PR(B)	PR(C)	PR(D)
初始	0.25	0.25	0.25	0.25
第一次迭代后	0.4583	0.0833	0.2083	0
第二次迭代后	0.25	0	0.0417	0
第三次迭代后	0.0417	0	0	0
第四次迭代后	0	0	0	0

咦？如果PageRank算法是这样的话，那岂不是每个网站的PR都是0了？
为了讨论上面情况发生的条件，我们暂时抛开网站，把问题抽象出来——研究有向图。
首先说明一点，对于如下这种不连通的图：

我们可以分别研究每一部分，而并不影响各个部分的收敛性。
设有向图G的顶点集合为V={V₁,V₂,…,V_n}，边的集合为E={Eij}。我们把有向图G的每个顶点都给定一个权值P(V_i)，即为它的PR值。有向边AB的权值定义为A为B贡献的PageRank，也即网站A链接到网站B的概率。这样，对于一个顶点，若它的出度大于0，则从它出去的权值和为1。
一个很显然的结论是，如果连通图中有一个顶点的出度是0，那么经过有限次迭代后所有顶点的PR值都将变为0。形象的说，这个顶点就像一个黑洞一样，把整体的PR值慢慢的“吸收”了。由于它不对外贡献任何PR，所以整体的PR总和在不断减少，最终减为0。
那么google如何防止这类图的产生呢？毕竟，一个网站没有外链是完全有可能的。这里有一种合理的解决方案(但谁知道google是怎么做的呢？)，即如果一个网站没有外链，那么就假定它对其余所有的网站都有链接。这样我们就避免了整体的PR被吸收的现象。
当一个连通图的每一个顶点的出度都大于0时，不难看出，PR值在内部流通，整体的PR是守恒的。有的朋友可能会问，如果存在一个顶点的入度为0会如何呢？通过一次迭代，它的PR就会变成0，而把它的那部分PR贡献给了图中剩余的部分。所以，最终入度为0的顶点的PR都将是0，而整体的PR仍然守恒。
那么，整体的PR守恒就能保证每个顶点的PR值最终会收敛么？
看下面一个简单的例子：

迭代过程如下：

	PR(A)	PR(B)	PR(C)	PR(D)
初始	0.25	0.25	0.25	0.25
第一次迭代后	0	0.375	0.25	0.375
第二次迭代后	0	0.375	0.375	0.25
第三次迭代后	0	0.25	0.375	0.375
第四次迭代后	0	0.375	0.25	0.375
第五次迭代后	0	…	…	…

上述过程将无限循环下去，而最终无法收敛。
其实我们同样可以用矩阵来表示这个问题，因为本质上有向图和矩阵是可以相互转化的。令A_ij表示从顶点i到达顶点j的概率，那么上图用矩阵来表示就是

如果我们给定初始向量

做第一次迭代，就相当于用初始向量乘以上面的矩阵。第二次迭代就相当于用第一迭代的结果再乘以上面的矩阵……实际上，在随机过程的理论中，上述矩阵被称为“转移概率矩阵”。这种离散状态按照离散时间的随机转移过程称为马氏链(或马尔可夫链,Markov chain)。设转移概率矩阵为P，若存在正整数N，使得P^N>0(每一个元素大于0)，这种链被称作正则链，它存在唯一的极限状态概率，并且与初始状态无关。(详见随机过程理论)

在这里，我们仅仅是非常简单的讨论了一下PageRank的原理，这与Google PageRank的实际算法相差甚远。域名数据，内容质量，用户数据，建站时间等等都有可能被考虑进去，从而形成一个完善的算法。这里最神奇的地方就是面对如此庞大的数据量和网页如此实时的变化，google却能在有限的时间内计算出所有网站的PR！这里面的学问可真不少呀！
参考资料：
http://en.wikipedia.org/wiki/PageRank
http://en.wikipedia.org/wiki/Markov_chain
《数学模型（第三版）》姜启源,谢金星,叶俊编, 高等教育出版社



其实不断迭代的状态变化都很好理解，就是投票过程，当一个人没有人投票时，那他状态票数就为零，当依赖于它的网页，如果只依赖于它，而当这个投票者票都变为零后，那它当然也没有人给它投了，因为唯一投它的网页都挂了，即票为零。