Google的PageRank算法
在过去几年之内，Google成为了全世界被使用的最多的搜索引擎。与其它搜索引擎比较，除高性能和易用以外，一个决定性的因素是它的优秀的搜索结果。搜索结果的这质量极大地来源于PageRank——一个精密的排序网页文件等级的方式。
　　 本文的主要目的就是对PageRank的各个方面做一次广泛的勘测。本文内容主要依据Google创始人Lawrence Page和Sergey Brin在他们作为斯坦福大学研究生时的文章。
　　 经常被讨论的是，尤其是考虑到互联网的动态性，自从PageRank科学工作开始，许多时间被浪费了，因为他仍然可以是Google搜索引擎的等级等级的基本依据。毋庸置疑，在过去几年内有许多关于Google等级方法的调整和修改，但PageRank是Google成功的绝对关键，因此至少PageRank的根本概念在之后应该仍然不会改变的。
　　 从万维网的早期，搜索引擎开发不同的方法排序网页。实际上，直到今天，任一个搜索引擎对网页的排序，是根据搜索的词组短语在页面中的出现次数，并用页面长度和html标签的重要性提示等进行权重修订。
　　 为了得到更好的搜索结果，尤其是使搜索引擎自动抵制那些基于对详细等级标准页面（入口页）内容的分析而自动生成的网页，连接人气值的概念开始被开发了。根据这个概念，一个网页文件的入链数量通常表示此文件的重要程度。因此，一般地，如果从其他网页链接到一个网页的数量越多，那么这个网页就越重要。链接人气值的概念通常可以避免那些只被创造出来欺骗搜索引擎并且没有任何实际意义的网页得到好的等级，然而，许多网站管理员为了避免发生这种情况，他们从其他没有意义的网页创建大量入站链接，而不是从入口页（doorway pages）。
　　 与链接人气值向比较，PageRank的概念并不是简单地根据入站链接的总数。PageRank基本的方法是，越是重要的文件链接一个文件，则这个文件就越重要，但那些入站链接并不是被平等计算的。首先，如果其他高等级的文件连接到它，那么根据PageRank的规则，此文件的等级也高。
　　 如此, 在PageRank概念中，文件的等级由与它连接那些文件的等级决定的。它们的等级再由与他们连接文件的等级决定。因此, 文件的PageRank由其他文件的PageRank总递归之和确定。因为，即使是在边缘的少量链接，任一个文件的等级都会影响些其他文件的等级，概言之，PageRank的等级是由整个网的连接结构决定的。虽然这种方法似乎是非常宽泛和复杂的, Page和Brin已经能够通过一个微不足道的运算法则将它投入实践了。
　　 个人总结：PageRank绝对是个很科学的小创意。说他科学，你会在我以后的文章中看到Google是如何将数学（具体来说多数是统计学）理论淋漓尽致地发挥在搜索技术之中。说他“小”，因为这些理论对于搞数学的人来说实在太微不足道了，甚至稍微有些科学高数知识的人都能理解。
　 Lawrence Page和Sergey Brin在个别场合描述了PageRank最初的算法。这就是 PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) ——算法1
式中：
PR(A) :网页A页的PageRank值；
PR(Ti) :链接到A页的网页Ti的PageRank值；
C(Ti) :网页Ti的出站链接数量；
d :阻尼系数，0<d<1。
　　 可见，首先，PageRank并不是将整个网站排等级，而是以单个页面计算的。其次，页面A的PageRank值取决于那些连接到A的页面的PageRank的递归值。
　　 PR(Ti)值并不是均等影响页面PR(A)的。在PageRank的计算公式里，T对于A的影响还受T的出站链接数C(T)的影响。这就是说，T的出站链接越多，A受T的这个连接的影响就越少。
　　 PR(A)是所有PR(Ti)之和。所以，对于A来说，每多增加一个入站链接都会增加PR(A)。
　　 最后，所有PR(Ti)之和乘以一个阻尼系数d，它的值在0到1之间。因此，阻尼系数的使用，减少了其它页面对当前页面A的排序贡献。
随机冲浪模型
　　Lawrence Page和Sergey Brin为以上这个PageRank算法给出了一个非常简单直观的解释。他们将PageRank视作一种模型，就是用户不关心网页内容而随机点击链接。
　　 网页的PageRank值决定了随机访问到这个页面的概率。用户点击页面内的链接的概率，完全由页面上链接数量的多少决定的，这也是上面PR(Ti)/C(Ti)的原因。
　　 因此，一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。并且，阻尼系数d减低了这个概率。阻尼系数d的引入，是因为用户不可能无限的点击链接，常常因无聊而随机跳入另一个页面。
　　 阻尼系数d定义为用户不断随机点击链接的概率，所以，它取决于点击的次数，被设定为0-1之间。d的值越高，继续点击链接的概率就越大。因此，用户停止点击并随机冲浪至另一页面的概率在式子中用常数(1-d)表示。无论入站链接如何，随机冲浪至一个页面的概率总是(1-d)。(1-d)本身也就是页面本身所具有的PageRank值。
Lawrence Page和Sergey Brin在不同的刊物中发表了2个不同版本的PageRank的算法公式。在第二个版本的算法里，页面A的PageRank值是这样得到的：
PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) ——算法2
　　 这里的Ｎ是整个互联网网页的总数。这个算法2，并不是完全不同于算法1。随机冲浪模型中，算法2中页面的PageRank值就是在点击许多链接后到达这个页面页面的实际概率。因此，互联网上所有网页的PageRank值形成一个概率分布，所有RageRank值之和为1。
　　 相反地，第一种算法中随机访问到一个页面的概率受到互联网网页总数的影响。因此，算法2解得的PageRank值就是用户开始访问过程后，该页面被随机访问到的概率的期望值。如果互联网有100个网页，其中一个页面PageRank值为2；那么，如果他将访问互联网的过程重新开始100次（xdanger注：这句话具体含义是，该用户随机点击网页上的链接进入另一个页面，每点击一次都有一定概率因疲劳或厌倦或其他任何原因停止继续点击，这就是阻尼系数d的含义；每当停止点击后，即算作此次访问结束，然后随机给出一个页面让他开始另一次访问过程；让他将这样的“手续”重复进行100次），平均就有2次访问到该页面。
　　 就像前面所提到的，两种算法并非彼此是本质的不同。用算法2解得的PR(A)乘以互联网的总网页数N，即得到由算法1解得的PR(A)。Page和Brin在他们最著名的刊物《The Anatomy of a Large-Scale Hypertextual Web Search Engine》中调和了两种算法，文中声称算法1是将PageRank形成对于互联网网页的一个概率分布，其和为1。
　　接下来，我们将使用算法1。理由是算法1忽略了互联网的网页总数，使得更易于计算。