PageRank初探

搜索引擎架构

  在进入PageRank之前,我们先看一下一个典型的搜索引擎架构是长啥样的。下图是98年google创始人拉里●佩奇提出的原始的google的架构。

  分布式的爬虫从URL Server得到URL列表,然后爬取或者说下载网页放到store server里面。接着store server压缩后,又把它送到Repository里。Indexer执行了一序列操作,从Repository读取数据,进行解压,并且进行解析,顺便把每个页面根据网址都编上索引,我们叫索引为docID。而且它为以后的网页的相关性和重要性排序进行了准备。对于相关性的准备,它把网页进行了分词操作,而且还记录了词出现的位置,大小写甚至字体大小等等一些参数,然后把他扔到Barrels里面。根据这些词生成更新字典,Lexicon。对于重要性的准备,它提取了该页面所有的链接和一些重要信息,比如链接是从哪儿链接到哪儿,链接对应的描述等,保存到anchor file里面,也就是上图的anchors。URLresolver所承当的工作比较简单,对anchor file里面的相对路径转换为绝对路径,并且根据链接建立哪个页面跟哪个页面链接的数据库,当然页面是用docID标示的。这个数据库就是后面用来计算PageRank的关键。这就是搜索引擎的大概的架构。

采用PageRank的原因

  我们可以假设如果没有PageRank,会怎么样。
  如果把上图的PageRank相关的模块都删除,那么那个seacher得到的结果中相关性的权重就会很大。比如把每个搜索的关键字11作为一个hit,然后对barrels里的东西进行匹配,匹配的程度越高,最后的显示结果的排名也就越高。
  举个例子,比如现在我在google里搜索中美关系。如果A网页出现了5次中美关系,B网页出现了两次中美关系,那么A网页就应该排在B网页前面。咋眼一看,好像挺有道理的样子。可是我去搜索个东西,我希望的是对我越有用的排在越前面。可是如果有个C网页,它在一个div里面写了100次中美关系,那么这个网页是不是就会排的很靠前??而且这个div还可以设置不可见。那么也就是说可能C网页其实是个卖六合彩,跟中美关系一点关系都没有。再者说就算没人做这些spam,但是中美关系重复多次的也不一定是我想要的,像这类的搜索,一般wiki才是最需要的。让我们看一下google的搜索结果。


  是不是觉得这个排序还不错的?BBC那个可能是它SEO做得特别好吧↖(^ω^)↗

PageRank介绍

  从前面两节可以知道PageRank算法是个重要性排序,跟相关性的关系不大。那么它是怎么实现的呢?

it makes use of the link structure of the Web to calculate a quality ranking for each web page. This ranking is called PageRank.

  这句话出自The anatomy of a large-scale hypertextual web search engine。也就是说PageRank是基于web的链接架构的,这也在我们前面典型搜索引擎架构图里体现。OK,那我们就把link structure of web画出来。假设每个网页作为一个节点。从网页A到网页B的链接用从A到B的有向边来进行表示。我们先考虑一个仅仅四个网页的一个简单网络,那么拓扑图如下图所示。


  PageRank是算网页的quality,那么假设用每个节点的权重来表示quality,于是上图的每个节点的权重又应该怎么进行计算呢?
  既然PageRank仅仅跟链接相关,那么就从链接出发。显而易见,链接一共可以分为两种:

  • 出去的链接,也就是从本网页链接到其他网页的链接。
  • 进入的链接,也就是从其他网页链接到本网页的链接。

  假设我是网页A的站长,那么我能管理的就是网页A到其他网页的链接。所以出去的链接不应该对网页A的权重造成影响,否则站长就能轻易地控制它了。而我并不能控制其他网页,那么如果存在其他网页对网页A的链接,那么就说明网页A对该网页是有用的,不然就不会存在这么一个引用。所以网页的权重应该是和进入的链接紧密相关。
  由上图所示,网页D对网页A有个链接。一般而言网页D不是我能控制。如果它能链接我的网页,就说明我的网页比较重要,至少有用。并且如果网页D越重要,那么我的网页就越重要。
  这就比如,我认识习近平,李长春等等人,这不代表我很重要,全国人民只要看新闻就能认识他们。但是如果李长春认识我,那我的身价就不低,如果习近平认识我,那更加不得了了。
  那么如何量化它呢?佩奇就提出了一个很简单的办法。假设网页D的权重为PR(D),由可知,网页D有三条出去的链接那么每条链接的权重就是PR(D)/3。以此类推,如果把这图看成状态转移图,那么当它平衡的时候,每个点的权重就是最终每个页面的质量或者说权重。此时:

PR(A) = PR(D)/3
PR(B) = PR(D)/3
PR(C) = PR(A) + PR(B) + PR(D)/3
PR(D) = PR(C)

  假设总权重为1,那么就可以得到PR(A)=PR(B)=0.125,PR(C)=PR(D)=0.375。

利用矩阵计算PageRank

  上一节对PageRank算法作了简单的说明,但上一节的方法明显不适合计算机进行计算。所以这一节对利用矩阵进行PageRank计算进行简单的描述。
  如果把上图看成一个状态转移图,A、B、C、D用1、2、3、4来进行表示,那么就可以得到转移矩阵如下,假设第i行第j列表示从网页i到网页j的链接的权重,那么网页i有$N$条出去的链接,该值就为$1 \over N$。如果从网页i到网页j的链接,那么该值就为0

  现在转移矩阵已经有了,那么初始矩阵呢??我们目的是对网页进行排序,那么也就是说只要相对权重就行。于是初始矩阵就可以随便设,反正最后经过状态转移矩阵的平衡,最后都会平衡的。于是就设初始矩阵为全一矩阵如下,第i列代表网页i。

  若设$W^*$为$W$的下一状态,那么可得如下公式

  如果原先拓扑不变态的话,一直乘下去,最后$W$会收敛,也就是说最终会$W^*=W$。那么公式$\eqref{eq1}$可以写为

  在上式中$PR$代表最终每个页面的权重,是个四维行向量。然后这个行向量的模为1是个可选条件,仅仅是为了方便排序而已,其实为多少都无所谓。具体来说:

  可以轻易地解出

  这就是利用矩阵进行PageRank计算的方法。比较简单但也很有效。

PageRank对特殊拓扑的计算

  前面对简单网络拓扑的PageRank计算进行了分析,但是其实如今的互联网上的网页拓扑应该是个稀疏矩阵,而且极为复杂,很容易出现各种奇葩情况。下面对可能出现的特殊情况进行分析

孤岛拓扑

  因为如今的互联网上的网页拓扑应该是个稀疏矩阵,很可能出现孤岛,也就是说某个网页只进不出,没有任何外链。这种情况就对PageRank算法提出了挑战。因为前面不断和转移矩阵相乘直到权重收敛,很大程度上是依赖转移矩阵的每一行的和为1,但是这种孤岛,或者说dead end的情况,所对应的行是全零的,这样就会导致了最后权重行向量不收敛。
  我们这次把上图的C到D的链接改成了A到D的链接,破坏原先拓扑的强连通性,那么,如今网络拓扑如下:


  此时,可以很明显得看出节点C只进不出,是个dead end,这也导致了我们的拓扑不再是一个强连通拓扑。状态转移矩阵$H$根据可以写为

  如果直接用公式$\eqref{eq2}$进行计算,那么可以得到:

  这根本就不符合我们的预期。那么对解决孤岛问题,我们可以先拿掉孤岛,这样就回归我们上一节讨论的简单拓扑。比如我们把中的节点C拿掉,可以得到拓扑如下:


  此时,节点B又成孤岛,我们再去掉节点B。又得到新拓扑如下


  上图可以很明显地看出$ PR_A = PR_D $。假设总权重为1,那么$ PR_A = PR_D = \frac{1}{2} $。这时把$ PR_A = PR_D = \frac{1}{2} $代入去孤岛C网络拓扑”中,明显可以看到节点A和节点B近似对称,节点的权重应该一样。可以得到$ PR_B = \frac{1}{2} $ 。然后又继续恢复拓扑,把$PR_A PR_B PR_D $的权重都代入孤岛网络拓扑我们就可以得到$ PR_C = \frac{11}{12}$。于是

  但上面的这种方法有个很大的缺陷,需要分析拓扑的对称关系等,这就导致了计算机使用不是那么方便。那么有没有什么更方便的方法呢?
  既然C点没有外链,那么我们就人为地给它“创造”外链。为了公平,有N个节点,那么就设节点到每个节点的概率为$1 \over N$。在孤岛网络拓扑图上就可以认为节点C到每个节点的概率都是$1 \over 4$。于是就能得到转移矩阵如下:

  然后采用公式$\eqref{eq2}$进行计算,可以得到

  这个结果和前面的那个去节点的结果相比,比例以及相对大小极为相近。而且对于计算机来说,计算十分方便。

存在自环拓扑和孤立网络块拓扑

  有时候会存在一个网页没有外链,只有指向自己的链接,比如好多博客都是这样的。没有参考文献,只有一句转载请注明XXXXX。这种拓扑我们用下图作为示例


  上图,就是把孤岛拓扑的节点C加了一个自己指向自己的链接,可以称为一个自环。那么这会出现什么情况呢?
  我们先把状态转移矩阵$H$写出来。

  然后采用公式$\eqref{eq2}$进行计算,可以得到

  也就是说节点$C$变成1了,而其他节点变成0。节点C最重要是符合我们预期的,但是其他节点都为0,就没法排序了,属于无效数据。
  但前面我们假设节点$C$去每个节点的概率相等,但这个拓扑就没法这么假设,因为节点$C$有个指向自己的链接,那么按理来说就算会到处跳网页,自己转自己的网页的概率也会比去其他网页的概率高。但是高多少呢??
  现在我们再看一个拓扑。


  在上图中$A、B$和$C、D$是不相连的。这在实际网络中极易出现这种情况。比如说伟大的GFW横跨中间。那么这时候如何判断独立的网络中的节点在整个互联网中的权重呢??比如网络区域$\alpha$和$\beta$是两块不相连的网络。其中节点A是网络块$\alpha$中的权重最大的节点,节点B是网络块$\beta$中的权重最大的节点。那么这时候节点$A$和$B$哪个权重大??
  为了解决这类问题,就引入了一个“心灵转移概率”$\beta$。它表示有$\beta$的概率不走正常路,也就是说不是按照拓扑所给出的链接进行跳转,而是随机去任何一个网页。因为不是按照链接走的,所以称为“心灵转移概率”。这个值为经验值,一般为0.1到0.2.这样的话可写如下PageRank公式

  上式中的$\vec e$就是一个全一的向量,维数等于页面的总个数$N$。
  现在就用$\beta = 0.2$来计算有自环的网络拓扑,当权重向量的范数小于0.00001时,可以得到:

  公式$ \eqref {eq4} $还可以算其他的拓扑,如计算孤岛拓扑。可得

  可以看到,这个结果的顺序和前面我们的方法得到的结果是一致的,这也验证了正确性和合理性。

PageRank的缺陷

  在工程上不存在完美的算法,每个算法总是有各种各样的缺陷。PageRank也是一样的。PageRank的大的缺点有三个:

  • 忽视了用户的话题偏好。比如说我是一个程序员,你搜苹果,如果你前面给我一堆苹果(水果)的网页,就不符合我的预期。所以就应该把网页按照话题进行分类。于是就在PageRank上做了改进,变成了Topic-Specific PageRank算法。

  • 测量模型过于单一。这是它的优点方便计算,但是也是缺点,仅仅关注了链接。于是有许多新的权重算法,比如Hubs-and-Authorities

  • 易受Link Spam 的攻击。Link Spam就是攻击者自己做了一堆站点,特定了这些站点的链接。让他能控制的站点(支持站点)给想要提高排名的站点(目标站点)链接。我们在前面的PageRank算法的分析中,可以得到,被链接的站点可以分享给它链接站点的权重,于是就通过这个来拉高排名。也可以大量投放推广链接到论坛,贴吧等地方制造链接。这也可以调高目标站点的排名。这是PageRank最大的缺陷,于是google已经基本放弃了继续维护PageRank算法,而是采用它的改进型——TrustRank算法。

附录

PageRank的参考算法(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
package test;
import Jama.Matrix;
public class Test {
public static void main(String[] args) throws InterruptedException {
double [][] h = {{0,0,0.5,0.5},
{0,0,1,0},
{0,0,0,0},
{0.333333333333333333333333,
0.333333333333333333333333,
0.333333333333333333333333,0},};
Matrix hMatrix = new Matrix(h);
double [][] e = {{1,1,1,1}};
Matrix eMatrix = new Matrix(e);
double [][] w = {{1,1,1,1}}; //网页权重
Matrix wMatrix = new Matrix(w);
double [][] wLast = {{0,0,0,0}};
Matrix wLastMatrix = new Matrix(wLast);
int N = 4; //网页个数
double beta = 0.2; //心灵转移概率
double error = 0.00001; //收敛误差
while (wLastMatrix.minus(wMatrix).times(wLastMatrix.minus(wMatrix)
.transpose()).get(0, 0) > error) {
wLastMatrix = (Matrix) wMatrix.clone();
wMatrix = wMatrix.times(hMatrix).times(1 - beta).plus(eMatrix.times(1 * beta / N));
}
wMatrix.print(3,6);
}
}

参考文献