webdancer's Blog

计算PageRank

在上一篇文章中,介绍了PageRank算法的基本原理,这里讨论一下如何计算PageRank的值。我们还是使用上一篇使用的例子,系统结构图如下:

由PageRank的原理可以知道,一个页面的PageRank值主要是由系统的图结构(M)和阻尼因子(d)决定的。根据经验d的取值为0.85。

PageRank可以用Markov Chain的理论来解释,我们可以根据图的邻接矩阵$A$计算一个随机矩阵$M$。

由邻接矩阵得到随机矩阵具体的过程:

  1. 如果一行中没有1,全为0,则用$\frac{1}{N}$来代替0,其他的行如下处理;
  2. 每个1都除以这行中1的个数,即:$\frac{A_{i,j}}{\sum_j{A_{i,j}}}$;
  3. 用$d$乘以上面得到的矩阵;
  4. 在上面得到的矩阵的每个元素加上$\frac{1-d}{N}$,从而得到$M$;

上图的邻接矩阵可以表示为:

根据上面给出的算法,可以得到随机矩阵:

在随机矩阵中,stationary probability vector$\pi$是在随机矩阵的作用下值不变。其定义如下:

$\pi P = \pi$。 

根据Perron–Frobenius theorem定理,随机矩阵总会存在一个stationary probability vector,而这个特征向量正好就是我们要求的PageRank。有很多的方法可以求解,最常用的是:power method.

算法描述如下:

  1. 初始化向量$x_0$;
  2. 计算$x_{(t+1)}=x_tM$;
  3. 判断是否$|x_{(t+1)}-x_t| < \epsilon$,如果是,停止;否则,跳到2.

参考:

1.http://en.wikipedia.org/wiki/PageRank

2.http://nlp.stanford.edu/IR-book/html/htmledition/the-pagerank-computation-1.html#pagerank

 

ps: 不知道为什么不能显示矩阵,只能转为图片了。

 

 

PageRank简介

今天去听了一个讲座,讲的是基于机器学习方法的rank算法,讲到了PageRank(google.com)和HITS(ask.com)算法,本来就像看看PageRank是怎么回事,刚好借此机会学习一下。

 
概念
 
PageRank是以google创始人Larry Page命名的一种链接分析算法,它根据网页的相关性和重要性来给网页赋予一个权重值。一个网页p的权重值通常被p的PageRank,记作: PageRank(p)。
 
原理
 
一个页面的“得票数”由所有链向它的页面的重要性来决定,到一个页面的超链接相当于对该页投票。一个页面的PageRank是由所有链向它的页面(“链入页面”)的重要性经过递归算法得到的。一个有较多链入的页面会有较高的等级,相反如果一个页面没有任何链入页面,那么它没有等级。简言之,“被越多优质的网页所指的网页,它是优质的概率就越大”。
 
看下面一个简单的例子,我们假设我们要处理的系统中含有四个页面(当然,实际的www有的页面数目要远远的大于这个数目),如下图所示。其中A,B,C,D四个节点代表了四个页面,其中B链接到了A,C,C链接到了A,D链接到了A,B,C。
 

 

现在我们来考虑一下PageRank的意思,假定我们有一个随机浏览者(random surfer),他在网上随机的浏览网页,现在他处于页面D,他有相同的概率去访问D链接到的页面,即概率为:$frac{1}{3}$,当他在页面上这样随机访问的时候,一些网页会比另外一些网页更经常的访问到。直觉上看,那些有更多链接指向他的页面要更容易被访问到。这也就是PageRank背后的思想:更经常访问的网站更重要。
 
下面计算A点的PageRank值。我们假设一个页面不能投票2次,所以B给每个页面半票,以同样的逻辑,D投出的票只有三分之一算到A的PageRank上。那么:
 
$PR(A) = \frac{PR(B)}{2} + PR(C) + \frac{PR(D)}{3}$
 
设L(p)为从页面p链接到的页面数目,则上面的式子可以写为:
 
$PR(A) = \frac{PR(B)}{L(B)} + \frac{PR(C)}{L(C)} + \frac{PR(D)}{L(D)}$
 
我们可以得到一般情况下,任意页面p的PageRank式子:
 
$PR(p_i) = \sum_{p_j \in M(p_i)} \frac{PR(p_j)}{L(p_j)}$
 
一个页面不能投票两次比较很理解,例如在上面的例子中,如果B,C页面的PR值不平均开,那么A链接的PR值肯定会超过B,C,如果A是一个新网站,而B,C都是经典网站,显然这种情况就有问题,而且平均开更符合我们的直觉:如果从B页面上随机的点击的话,那么B页面上每个链接的概率都是一样的,它的PR值也应该是平均开的。
 
对于那些没有链出的页面,比如例子中的A节点,没有链出,我们引入阻尼系数d(damping factor )的概念后,原来可能被分割的网络就变得连通起来,今天听那个老师讲这样最后的PageRank值最后就会收敛,从而用来进行排序。这样计算的公式变为:
 
$PR(p_i) = \frac{d}{N}+ d (\sum_{p_j \in M(p_i)} \frac{PR(p_j)}{L(p_j)})$
 
其中,N为链接到$p_i$的总的页面数目。
 
计算
常用的两种方法就是:数值迭代和线性代数的方法。后面在好好分析一下吧!

 




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee