webdancer's Blog
计算PageRank
在上一篇文章中，介绍了PageRank算法的基本原理，这里讨论一下如何计算PageRank的值。我们还是使用上一篇使用的例子，系统结构图如下：
由PageRank的原理可以知道，一个页面的PageRank值主要是由系统的图结构(M)和阻尼因子（d）决定的。根据经验d的取值为0.85。
PageRank可以用Markov Chain的理论来解释，我们可以根据图的邻接矩阵$A$计算一个随机矩阵$M$。
由邻接矩阵得到随机矩阵具体的过程：
- 如果一行中没有1，全为0，则用$\frac{1}{N}$来代替0，其他的行如下处理；
- 每个1都除以这行中1的个数，即：$\frac{A_{i,j}}{\sum_j{A_{i,j}}}$;
- 用$d$乘以上面得到的矩阵;
- 在上面得到的矩阵的每个元素加上$\frac{1-d}{N}$，从而得到$M$;
上图的邻接矩阵可以表示为：
根据上面给出的算法，可以得到随机矩阵：
在随机矩阵中，stationary probability vector$\pi$是在随机矩阵的作用下值不变。其定义如下：
$\pi P = \pi$。
根据Perron–Frobenius theorem定理，随机矩阵总会存在一个stationary probability vector，而这个特征向量正好就是我们要求的PageRank。有很多的方法可以求解，最常用的是：power method.
算法描述如下：
- 初始化向量$x_0$；
- 计算$x_{(t+1)}=x_tM$；
- 判断是否$|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是怎么回事，刚好借此机会学习一下。