在上一篇文章中，介绍了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: 不知道为什么不能显示矩阵，只能转为图片了。

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