PageRank – 基本算法

基本思路

和HITS算法类似,PageRank的出发点也是网页之间的link所代表的“认可”:

PageRank importance is determined by “votes” in the form of links from other pages on the web. The idea is that votes (links) from important sites should carry more weight than votes (links) from less important sites ….

和HITS不同的是,首先,PageRank并不区分Authority和Hub,只是计算page的重要性;另外,PageRank计算的并不是某一次query的相关page的重要性,它计算的是整个web网络的每个page的重要性,是query-indepentent。

虽然大部分的文献中,都将PageRank解释成是基于”Random Surfer“模型,在随机游走的过程中,经常被访问到的page比很少被访问到的page更加的重要。但从随机的角度更难理解PageRank的计算公式。其实换个角度看,PageRank和HITS非常的类似。例如下面这张图:

graph2

节点X有两个inlinks,分别来自节点A,B。A除了指向X以外,还指向了其它3个节点,而B还指向了其它的2个节点。那么节点X的PageRank的值就等于:
PR(X) = PR(A) / 4 + PR(B) / 3
这个公式已经非常近似于HITS中计算Authority的方法,例如X的Authority等于:
Autority(X) = Hub(A) + Hub(B)
这两个公式的区别,就在于HITS仅仅是一个求和,而PageRank相加的是概率。

矩阵表示

和HITS类似,首先将Graph表示成一个矩阵,只是不再是邻接矩阵,而是转移概率矩阵

clipboard

概率转移矩阵是一个随机矩阵(stochastic matrix),理想情况下,每一列之和等于1。

PageRank的计算就变成了 clipboard[5]
又变成了计算矩阵的特征向量

到目前为止,PageRank和HITS还是处于同一水准的,两者差不多。

实践中的问题

现实中的web graph并不是一个强连通的有向图,而是一个”bowtie model”:

clipboard[7]

除了强连通的部分,还有些节点没有outlinks,有些节点没有inlinks,有些节点是孤立的,等等。

其中,有两种情况最影响到PageRank的计算:
Dead-Ends
所谓的”dead-ends”,就是没有outlinks的节点。当graph中存在”dead end”节点,则对应的转移概率矩阵将不再是随机矩阵(stochastic matrix)。导致的结果是无法正确计算出每个节点的PR值,如下图,最终所有节点的PR值收敛到0:

clipboard[9]

Spider-Traps
另外一种现象是,有一组节点,这些节点都不是”dead ends”,但是,这些节点和其它的节点之间没有outlinks,如下图的c节点:

clipboard[11]

graph中存在”spider traps”节点,导致的结果是概率转移矩阵变成了可约的(reducible):

clipboard[13]

在马尔科夫链中,转移概率矩阵必须是不可约的,才存在唯一性的稳态分布。当矩阵可约时,如上图,最终所有的游走都会集中到节点C上:

clipboard[15]

算法改进

解决”dead-ends”的方法,是将每个dead ends改造成,它能够等概率的游走到graph中的所有节点,如下图:

clipboard[17]

(上图中的转移矩阵P是上一小节中矩阵M的倒置。主要是因为两个图拷贝自不同的paper,两边的标准不一样,一个用的是行转移概率矩阵,一个用的是列。)
经过这样的转换,”dead-ends”所对应的行(或者列)的概率之后又变成了1。整个矩阵重新变为了stochastic matrix。

而为了解决”spider-traps”,PageRank改造了之前的随机游走的策略。每个节点,除了会顺着outlinks游走到其他的邻居节点,还有一定的概率,会跳到graph中的任意节点。这被称为”teleporting“。
转移概率矩阵就变成了:

clipboard[25]

其中,

clipboard[27]

α表示继续沿着节点的outlinks游走的概率,而1-α表示的就是”teleporting”的概率,一般1-α的取值在0.1~0.2之间。
示例如下图,α=0.1:

clipboard[29]

转移概率矩阵重新变回了”irreducible“。
又因为矩阵是不可约的,所以PageRank的马尔科夫链存在唯一的稳态分布。在计算的时候,不需要担心PageRank结果的收敛性和唯一性。

优缺点

经过改进后的PageRank已经明显比HITS更甚一筹。我个人认为最漂亮的是,PageRank是从理论的角度来解决实际碰到的问题,而不是经验型的解法(或者称为practical approach)。比如”dead-ends”问题映射到理论中,就是stochastic matrix不再成立,而”spider-traps”则对应到矩阵的是否可约。解决方案也很赞。
另外,还有一点优势是,改进后的PageRank是一个可调参的模型。可调节的参数包括 α 以及向量 E。所谓的topic-sensitive PageRank就是通过调节向量E实现的。而α的微调也可以显著的改变PR值的排名。
PageRank要比HITS更能抵抗spam,因为它只使用了inlinks而没有用到outlinks,而恰恰outlinks是最容易做假的。不过从我个人的实践看,多少还是会受到spam的影响,比HITS好的有限。
比HITS计算要快,因为不是每次query都需要计算。

所以,PageRank比HITS更成功,不仅仅是因为google的原因,从算法本身来说也是有更大的优势。

 

— Continue. —

Advertisements
相册 | 此条目发表在Link Analysis, Social Network分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s