pageRank计算公式的由来

经常看到各种介绍pagerank的文章，但是少有文章能够讲清楚pagerank的思想是如何产生的，事实上这还是要归结到数学原理，这篇文章是讲得让我理解最深刻的：http://www.changhai.org/articles/technology/misc/google_math.php。

 

pagerank产生思想源于论文引用数，引用次数越高的论文影响力越大。它原则有两点：1，网页被链接的越多，重要性就越高；2，网页被重要性高的网页链接，就越重要。

 

p_n = Hⁿp₀ 是该想法的出发点，计算出最终各个网页的pageRank值。但是H^{n}矩阵必须保证满足三点要求，也就是三个问题：

1. 极限 lim_n→∞p_n 是否存在？
2. 如果极限存在， 它是否与 p₀ 的选取无关？
3. 如果极限存在， 并且与 p₀ 的选取无关， 它作为网页排序的依据是否真的合理？

第三个问题：用p_n = Hⁿp_0造成第3个问题的不合理情况，因为悬挂网页的存在，有些网页没有链接其他网页，会造成“网页黑洞”。(背后的数学问题是，存在H矩阵的某一列之和为0，不能构成概率之和为1的特点)

解决办法：通过S = H + ae^T/N，加入随机矩阵，模拟用户访问到没有链接的网页时，会随机选择互联网的一个网页作为其链接。

前两个问题：如果不能收敛的话，就得不到pagerank值。

 

解决办法： 假定虚拟用户在每一步都有一个小于 1 的几率 α 访问当前网页所提供的链接， 同时却也有一个几率 1-α 不受那些链接所限， 随机访问互联网上的任何一个网站。用数学语言来说 (请读者自行证明)， 这相当于是把上述 S 矩阵变成了一个新的矩阵 G：G = αS + (1-α)ee^T/N。

（ 因为随机过程理论中有一个所谓的马尔可夫链基本定理 (Fundamental Theorem of Markov Chains)， 它表明在一个马尔可夫过程中， 如果转移矩阵是素矩阵， 那么上述前两个问题的答案就是肯定的。而G矩阵是素矩阵）

 

这样，PageRank的计算公式就确定了，可以看到,在最终收敛后，p=G^*p，即p是矩阵G中特征值为1的特征向量。其余的特征值lambda满足|lambda|<=alpha