初识PageRank算法

http://www.datalab.sinaapp.com/?p=149

2012

一、简单PageRank计算

首先，我们将Web做如下抽象：1、将每个网页抽象成一个节点；2、如果一个页面A有链接直接链向B，则存在一条从A到B的有向边（多个相同链接不重复计算边）。因此，整个Web被抽象为一张有向图。

现在假设世界上只有四张网页：A、B、C、D，其抽象结构如下图，显然这个图是强连通的（从任一节点出发都可以到达另外任何一个节点）。

然后需要用一种合适的数据结构表示页面间的连接关系。PageRank算法是基于这样一种背景思想：被随机冲浪者访问越多的网页质量更可能高，而随机冲浪者在浏览网页时主要通过超链接进行页面跳转，因此我们需要通过分析超链接组成的图结构来推算每个网页被访问频率的高低。更直观的讲，一个网页的PangRank值越高，随机冲浪者浏览网页过程中，停留在该页面的概率越大，该网页越重要。

简单起见，我们可以假设当一个随机冲浪者停留在某页面时，跳转到页面上每个被链页面的概率是相同的。例如，上图中A页面链向B、C、D，所以一个用户从A跳转到B、C、D的概率各为1/3。设一共有N个网页，则可以组织这样一个N维矩阵：其中i行j列的值表示用户从页面j转到页面i的概率。这样一个矩阵叫做转移矩阵（Transition Matrix）。上图的四个网页对应的转移矩阵M如下:

然后，假定随机冲浪者出于n个页面的初始概率相等，那么初始的概率分布向量就是一个每维均为1/n的n维列向量V0。这里我们有4个网页，故V0-1 = [1/4 ， 1/4 ， 1/4 ， 1/4 ]。

这样，我们就可以从初始向量V0开始，不断的左乘转移矩阵M，用户在浏览网页时主要通过超链接进行i次跳转后，停留在每个页面的概率为：Mi*V。直到最后两轮迭代产生的结果向量差异很小时停止。实际中，对于Web而言，在错误控制在双精度的情况下，迭代50至75次已经足够收敛。

下面是前四次跳转过程中，每次迭代后每个页面的PageRank值：

可以看见，随着迭代次数的增加，网页A的PageRank值越来越大，趋近与它的极限概率3/9。这也说明了随机冲浪者停留在网页A上的概率相对于网页B、C、D来讲较大，该网页也较为重要。

二、问题1：终止点（DEAD ENDS）

终止点即为没有任何出链的点，如下图中的C。

如果我们不加处理，允许终止点存在的话，那么随着PageRank迭代次数的增加，各个网页的PageRank值会趋向于0，从而无法得到任何有关网页相对重要性的信息。

处理终止点的方法是将终止点及其入链从图中剔除。这样做之后可能会产生更所的终止点，继续迭代剔除终止点。但是最终我们会得到一个强连通子图，其中所有节点都非终止点。下面我们以左图为例，进行说明。左图按上述步骤剔除终止点之后，获得右图。

我们得到右图对应的转移矩阵，并计算图中A、B、C的PageRank值。

我们得到A、B、C的PageRank值分别为2/9、4/9，3/9，接下来按照刚才删除相反的顺序来计算C和E的PageRank值。由于C最后一个被删除，因而首先计算C的PageRank值。A有三条出链，因此它对C贡献了其1/3的PageRank值。D有三条出链，因此它对C贡献了其1/2的PageRank值。于是C的PageRank值为：

而E的入链就只有C，C的出链只有E，所以E的PageRank值与C相等。

需要注意的是，当前所有节点的PageRank值和已经超过1，因此不能代表随机冲浪者的概率分布，但他们仍然能够反映网页相对重要程度的合理估计值。

三、问题2：采集器陷阱（SPIDERTRAPS）

采集器陷阱是一系列节点集合，他们虽然没有一个是终止点，但是却没有出链指向该集合之外的其他节点。采集器陷阱导致在计算时将所有的PageRank值都分配给采集器陷阱以内的节点。

如下图所示，C为单节点构成的采集器陷阱及其转移矩阵。

随着迭代的进行，C的PageRank值不断趋向于1，其他非采集器陷阱内节点的PageRank值趋向于0。

处理采集器陷阱的做法是允许每个随机冲浪者以一个较小的跳转概率随机跳转到一个随机网页，而不一定要沿着当前网页上的出链前进。于是，根据前面的PageRank估计值V和转移矩阵M估计下一次迭代后的PageRank值V’的迭代公式变为：

其中，β是一个选定的常数，通常取值在0.8跟0.9之间。而e是一个分量都为1维数为n的向量，n是Web图中所有节点的个数。βMv表示随机冲浪者以概率β从当前网页选择一个出链前进的情况。(1?β)e/n是一个所有分量都是(1?β)/n的向量，它代表一个新的随机冲浪者已(1?β)的概率随机选择一个网页进行访问。

取β=0.8，上图的迭代公式变为：

下面是前几轮迭代的结果：

作为一个采集器陷阱，C获得了超过一半以上的PageRank值，但是这种效果受到了限制，其他每个节点也获得了一些PageRank值。

————————————————-

参考资料：《大数据：互联网大规模数据挖掘与分布式处理》及其对应的原版电子书《Mining of Massive Datasets》