The Google Pagerank Algorithm
一、 Google和PageRank算法介绍
首先介绍一下Pagerank的来源，背景，pagerank作为一个被现在大型搜索引擎goolge所采用的算法，最初是来自于stanford大学计算机科学系的 sergey brin and lawrance page的博士论文，既The Anatomy of a Large-Scale Hypertextual Web Search Engine （一个大型超文本搜索引擎的解析）通俗的说，pagerank algorithm是搜索引擎google使用的一种网页重要性的评估方式，pagerank的值决定了网页在搜索结果中的排名。
大家现在对pagerank有了一个基本的了解。下面来介绍一下：
二．Google 简介特征及其系统结构、工作原理
1、google的简介：
大家都用过goolge来查询很多我们需要的资料，她是一个大型的搜索引擎，我们都知道现在有很多的中文搜索引擎，包括有百度(baidu)，yahoo的一搜（yisou），说句题外话，yahoo的一搜在前两天已经深情谢幕了，也就是说她已经不存在了，取而带之的，yahoo本身作为了一个搜索引擎出现在我们的面前了，你可以打开yahoo的首页，就会发现她已经改变了，除了上面这些我们还知道有sohu的sougou，她一个中文搜索引擎。
GOOGLE最初作为一个实验品在stanford大学产生，并随着发展成为当今世界最著名的搜索引擎，当然有一定的过程，但是她的工作原理也决定了她能成为最好的搜索引擎。
搜索引擎技术随着互联网的增长已经显著的提高了，在1994年，美国最早搜索引擎wwww，the world wide web worm，这个搜索引擎索引了11万个网页和可利用文档。在1997年11月，搜索引擎watch宣称已经索引了200万个网页,而在2000年，一个复杂的全球网页索引将包含超过1亿的文档。正是因为有如此巨大的网页数据，所以我们找到自己想要的网页数据就非常的困难，这也是GOOGLE产生的原因。GOOGLE的设计目的就在于改善搜索质量和提高搜索速度，并且作用于学术的搜索引擎的研究。
2、下面来介绍一下GOOGLE的系统特征：google有两个最重要的特征，正是这两个特征决定了google能产生出高精确度的搜索结果。
第一个是利用WEB的连接结构来为每一个网页计算一个质量排序值，也就是我们前面提到的pagerank值。第二个是google利用链接来改善搜索结果。
3、下面来讲一下GOOGLE的体系结构总揽及其工作原理（首先来看一张图）
(图一)
在这部分，我们将给出一个高层次的整个GOOGLE的系统工作图。(如图一)
GOOGLE工作大致可以分为这么几部分：
第一部分，文件抓取过程。
大家看，这里有一个URL 服务器，用于给crawler，我们在这里将其称为抓取器或下载器，提供url地址的列表。可能有些同学对url不太明白，我顺便说一下，url全称是universal resourse location，即全球资源定位管理，我们都知道每个网站都有自己的服务器，也就是我们知道的所存放着网页文档的服务器。当然每个服务器都有自己的IP地址。URL服务器就是用于给抓取器提供这些网站服务器的IP地址。当IP地址给到抓取器后，抓取器就开始抓取或者下载这个服务器上的所有的WEB文档。当然我们在抓取的时候可以并行的抓取，上面我们列出了三个抓取器来并行的抓取网页。我们将抓取到的网页都存入到store sever，即存储服务器上。这个存储服务器再将网页压缩并且把他们存入数据仓库（repository）,这个数据仓库存储着每个网页的HTML也就是她的源代码。每个网页通过ZLIB压缩技术来进行压缩,在这个数据仓库中，每个网页文档都被一个接一个的存储，并且都加上了docid,lenghth,和URL地址等前缀。我们可以看一下它的数据存储结构图二
Figure 2. Repository Data Structure
图二：
第二部分，文件索引过程。
在GOOGLE系统中，文件索引保持了每个文件的全部信息，他采取的是一个固定的宽广ISAM（索引顺序存取法）。索引程序被两个服务器所执行，就是我们在上面看到的Indexer和sorter，为了区别这两个服务器，我们将indexer命名为索引器或分度器，而sorter为反索引起或反分度器。索引器将执行一系列的程序，他从repository（数据仓库）中读出文件，并将其解压缩，然后解析他们。每个文件被转换称一组字事件，我们字事件为采样数。这个采样数记录了文字，以及文字在文档中的位置，文字大小的近似值，他们的大小写。这个索引器就将这些采样数分布到一系列的数据桶(barrels)中，并且制造出一个部分前向的分类索引目录。在这里索引器indexer还要执行另一个重要的程序，即他要解析出每个网页的所有的链接，并把他们存入到一个锚文件anchors当中。这个锚文件中包含了每个连接的文本，和每个连接所指向的地址，每个链接出处的地址。Sorter也就是反索引器，就是要把前向索引目录经过加工变为反相索引目录。URL RESOLVER也就是URL分解器将从锚文件当中读出数据，并将相对的URL转换成一个绝对的URL。他将锚文本也就是链接文本插入到前项索引当中，结合着这个链接所指向的docID。这个URL分解器将产生一个连接数据库，这个数据库是每条记录由一对docID。这个链接数据库被用来计算所有网页的pagerank值。
第三部分，文件搜索过程
文件搜索的目的是为了有效的提供高质量的搜索结果。许多大的商业搜索引擎看起来已经取得了某种程度上的进步。因此GOOGLE花费了更多的时间来研究在搜索质量。当我们在GOOGLE中输入一个关键词进行查询的时候，GOOGLE首先会解析关键词并且在索引中查找我们关键词所对应的序号，找到与其匹配的内容，然后计算匹配网页的PAGERANK值，然后列出经过PAGERANK排序的网页序列，返回到浏览器给用户查看。
以上就是GOOGLE的大致的工作原理。当然其中还有一些细节问题没有谈到，但是这个不是我们今天要讲的主要内容，我们要讲的就是如何通过pagerank算法来给网页进行优化的排序。通过前面的介绍，我相信大家对pagerank算法有了一些具体的了解，明白了pagerank算法的用途和应用。
三、Pagerank算法：
那么什么是pagerank呢？
简单的说pagerank就是一个网页被互联网上所有的其他的网页投票所得到的投票数，它表明了一个网页的重要程度。一个指向某个网页的链接就被看做一个支持者的投票。如果没有链接指向那个网页，那么这个网页就没有支持者，也就没有投票数。（当然这里的投票是有节制的，不是一个投票对应着一个网页。
下面我们来看看在GOOGLE中用到的pagerank算法在最初是如何定义的：
我们假定网页A有T1。。。。Tn个网页指向它（或者页可以说有T1。。。。Tn个网页引用它）。变量d是一个衰减因子，它的取值范围在0到1之间。一般情况下，我们将衰减因子d设置为0.85。我们定义C（A）作为网页A所指向外部的链接的个数，也就是网页A里面的所有的链接个数。那么网页A的pagerank值可以这样得到：
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
注意到所有的pagerank值形成了一个概率分布，所以所有网页的pagerank的平均值将是一。
当然这样做还不够清楚，让我们把它分为几部分来详细解释一下：
1． PR（Tn）代表了每一个引用网页本身的pagerank值，PR（T1）就代表了第一个引用网页的pagerank值，而PR（Tn）代表了最后一个引用网页的pagerank值。
2． C（Tn） 表示Tn这个网页里面所包含的链接的个数。
3． PR（Tn）/C（Tn） 如果网页A有一个来自于网页tn的链接，网页A将从tn中得到一个共享的比例分数PR（Tn）/C（Tn）
4． d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 所有的分数被加在一起，但是为了制止其他网页有太多的影响，我们给它乘上了一个衰减因子d用来降低总的投票数，我们取d为0.85。
5． （1-d） 这部分是一个概率上的数学戏法。它意味着如果一个网页没有链接指向它，那么它仍然会有一个很小的pagerank值0.15（也就是1-0.85）
那么Pagerank是如何被计算的呢？
这正是问题有趣的地方，每一个网页的PR（也就是PAGERANK值，以后我们统一用PR来表示）依赖于指向它的网页的PR。但是我们并不知道那些网页的PR直到我们知道指向他们的其他网页的PR值，这样我们就陷入了一个死循环当中，我们就无法进行PR的计算了。
但是实际上并不是那样的，通过简单的迭代算法我们能够计算出PR的值，并且符合web的规格化链接矩阵的主要特征向量。我们能够继续进行计算一个网页的PR在不知道其他网页的PR值的时候。看起来很奇怪，但是，我们每一次运行计算都会得到一个近似的估计值，我们需要记下每一次计算后的估计值，然后重复多次计算直到这个估计值不在变动为止，这样得到的最后结果就是我们要求的PR。
让我们做一个最简单的例子：两个网页，每个网页都有一个网页引用，并且每个网页都只有一个连接指向外部。因为只有一个连接指向外部，所以：C(A)=1 ,C(B)=1.
让我们来推测一下：
假设1：
我们并不知道这两个网页的PR，所以我们假设他们都为1.0，然后做一些计算。
d = 0.85
PR(A) = (1 – d) + d(PR(B)/1)
PR(B) = (1 – d) + d(PR(A)/1)
就等于了
PR(A) = 0.15 + 0.85 * 1
= 1
PR(B) = 0.15 + 0.85 * 1
= 1
我们发现PR(A),PR(B)经过计算并没有改变，它与我们的假设一致，我们看来非常幸运，一次就得到了稳定的结果，也就是我们要求的值。
假设2
问题看起来太简单了，也许我们出错了。好的，让我们开始重新假设他们的PR都为0,然后重新计算：
PR(A) = 0.15 + 0.85 * 0
= 0.15
PR(B) = 0.15 + 0.85 * 0.15
= 0.2775 注意我们在前面算出了一个更好PR(A)的近似值，所以我们在这里用到了它。
然后再进行计算：
PR(A) = 0.15 + 0.85 * 0.2775
= 0.385875
PR(B) = 0.15 + 0.85 * 0.385875
= 0.47799375
再次计算：
And again
PR(A) = 0.15 + 0.85 * 0.47799375
= 0.5562946875
PR(B) = 0.15 + 0.85 * 0.5562946875
= 0.622850484375
我们这样一直计算下去的话，那么他们的PR值就会不断的增加。但是他们的PR会不会增加到1后就停止呢？这两个网页的PR会不会超过1呢？
让我们来看看下一个假设
假设3
让我们重新假设这两个网页的PR值,我们假设他们都能于40。然后我们来做一些循环测试：
PR(A)=40
PR(B)=40
第一次计算：
PR(A) = 0.15 + 0.85 * 40
= 34.25
PR(B) = 0.15 + 0.85 * 0.385875
= 29.1775
第二次：
PR(A) = 0.15 + 0.85 * 29.1775
= 24.950875
PR(B) = 0.15 + 0.85 * 24.950875
= 21.35824375
我们发现，这些数字，也就是两个网页的PR近似值再直线下降。如果我们继续计算下去，我们会发现他们将到达1并且停止改变。
这里有一段代码用于计算这个例子中的假设2：请大家看一下代码：（代码1）
#!/usr/bin/perl
print "Content-Type: text/html\n\n
大家再看一下代码的运行结果。（结果1）
I've rounded to 5 decimal places to make the output easier to read
a: 0.00000 b: 0.00000
a: 0.15000 b: 0.27750
a: 0.38588 b: 0.47799
a: 0.55629 b: 0.62285
a: 0.67942 b: 0.72751
a: 0.76838 b: 0.80313
a: 0.83266 b: 0.85776
a: 0.87909 b: 0.89723
a: 0.91265 b: 0.92575
a: 0.93689 b: 0.94635
a: 0.95440 b: 0.96124
a: 0.96705 b: 0.97200
a: 0.97620 b: 0.97977
a: 0.98280 b: 0.98538
a: 0.98757 b: 0.98944
a: 0.99102 b: 0.99237
a: 0.99351 b: 0.99449
a: 0.99531 b: 0.99602
a: 0.99661 b: 0.99712
a: 0.99755 b: 0.99792
a: 0.99823 b: 0.99850
a: 0.99872 b: 0.99891
a: 0.99908 b: 0.99922
a: 0.99933 b: 0.99943
a: 0.99952 b: 0.99959
a: 0.99965 b: 0.99970
a: 0.99975 b: 0.99979
a: 0.99982 b: 0.99985
a: 0.99987 b: 0.99989
a: 0.99991 b: 0.99992
a: 0.99993 b: 0.99994
a: 0.99995 b: 0.99996
a: 0.99996 b: 0.99997
a: 0.99997 b: 0.99998
a: 0.99998 b: 0.99998
a: 0.99999 b: 0.99999
a: 0.99999 b: 0.99999
a: 0.99999 b: 0.99999
a: 0.99999 b: 1.00000
a: 1.00000 b: 1.00000
Average pagerank = 1.0000
注意：这里有一个原则，无论你如何开始你的假设，一旦这个pagerank计算公式被设定，那么所有网页的PAGERANK的平均值将是1.0。
我们可以不直到其他网页的PR而求得我们所需要的PR值。但是这样经过了很多次的循环迭代运算。如何才能快速的得到我们要求的PR值呢？
对于一个大型网络来说，我们要重复计算多少次才能得出pagerank的值呢？这是一个比较难的问题，象互联网这样大的网络来说它肯能需要几千万次的重复计算。其中，d的取值，也就是衰减因子需要非常的巧妙的。如果它太高的话可能需要几个世纪PR才能被确定下来，如果太低的话，你也将重复的过了头，无论d的取值是过高还是过低，那么，这些数字将象钟摆一样不断的晃动而永远不会停止下来。
选择计算的次序将对我们有所帮助，答案将总是会出现，无论你选择什么样的次序，但是一些次序将使你更快的得到我们想要的结果。在下面的例子中，为了清晰我们用了非常简单的代码，大约需要20到40次的重复计算就能得到结果。
例1：
在这里不做重复的计算了，大家可以看一下这个程序：（代码2）
#!/usr/bin/perl
print "Content-Type: text/html\n\n
再来看一下结果。（结果2）
a: 0.00000 b: 0.00000 c: 0.00000 d: 0.00000
a: 0.15000 b: 0.21375 c: 0.39544 d: 0.15000
a: 0.48612 b: 0.35660 c: 0.78721 d: 0.15000
a: 0.81913 b: 0.49813 c: 1.04904 d: 0.15000
a: 1.04169 b: 0.59272 c: 1.22403 d: 0.15000
a: 1.19042 b: 0.65593 c: 1.34097 d: 0.15000
a: 1.28982 b: 0.69818 c: 1.41912 d: 0.15000
a: 1.35626 b: 0.72641 c: 1.47136 d: 0.15000
a: 1.40065 b: 0.74528 c: 1.50626 d: 0.15000
a: 1.43032 b: 0.75789 c: 1.52959 d: 0.15000
a: 1.45015 b: 0.76632 c: 1.54518 d: 0.15000
a: 1.46341 b: 0.77195 c: 1.55560 d: 0.15000
a: 1.47226 b: 0.77571 c: 1.56257 d: 0.15000
a: 1.47818 b: 0.77823 c: 1.56722 d: 0.15000
a: 1.48214 b: 0.77991 c: 1.57033 d: 0.15000
a: 1.48478 b: 0.78103 c: 1.57241 d: 0.15000
a: 1.48655 b: 0.78178 c: 1.57380 d: 0.15000
a: 1.48773 b: 0.78228 c: 1.57473 d: 0.15000
a: 1.48852 b: 0.78262 c: 1.57535 d: 0.15000
a: 1.48904 b: 0.78284 c: 1.57576 d: 0.15000
a: 1.48940 b: 0.78299 c: 1.57604 d: 0.15000
a: 1.48963 b: 0.78309 c: 1.57622 d: 0.15000
a: 1.48979 b: 0.78316 c: 1.57635 d: 0.15000
a: 1.48990 b: 0.78321 c: 1.57643 d: 0.15000
a: 1.48997 b: 0.78324 c: 1.57649 d: 0.15000
a: 1.49001 b: 0.78326 c: 1.57652 d: 0.15000
a: 1.49004 b: 0.78327 c: 1.57655 d: 0.15000
a: 1.49007 b: 0.78328 c: 1.57656 d: 0.15000
a: 1.49008 b: 0.78328 c: 1.57657 d: 0.15000
a: 1.49009 b: 0.78329 c: 1.57658 d: 0.15000
a: 1.49009 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49010 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49010 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49010 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49010 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49011 b: 0.78329 c: 1.57660 d: 0.15000
a: 1.49011 b: 0.78330 c: 1.57660 d: 0.15000
a: 1.49011 b: 0.78330 c: 1.57660 d: 0.15000
a: 1.49011 b: 0.78330 c: 1.57660 d: 0.15000
a: 1.49011 b: 0.78330 c: 1.57660 d: 0.15000
Average pagerank = 1.0000
所以这个例子中正确的PR为：
大家通过程序的执行结果可以看出，大约经过了20次的重复后这些PR值被确定下来
大家看看上面这个图中的PageD，也就时网页D，即使没有任何一个网页有链接指向它，它仍然得到了0.15的PR，这个正确吗？
让我们来亲手算一下，对于PageD，没有链接指向它，那么根据公式它的PR应该为：
PR(D) = (1-d) + d * (0)
= 0.15
无论做多少次你都会得到这个结果。
说明：每一个网页的最小PR值将为0.15。但是这个可能仅仅是在理论上的。因为有人说GOOGLE会把那些没有链接指向的页面从索引中删除。也就是说如果你的网页没有链接指向，那么它就不会出现在GOOGLE的搜索引擎当中了。
例2：
一个简单的有等级的网络结构：
大家再看一下程序。（程序3）
#!/usr/bin/perl
print "Content-Type: text/html\n\n
这个是结果（结果3）
a: 0.00000 b: 0.00000 c: 0.00000 d: 0.00000 e: 0.00000 f: 0.00000 g: 0.00000 h: 0.00000
a: 0.15000 b: 0.19250 c: 0.19250 d: 0.19250 e: 0.18273 f: 0.18273 g: 0.18273 h: 0.18273
a: 0.50998 b: 0.29449 c: 0.29449 d: 0.29449 e: 0.20006 f: 0.20006 g: 0.20006 h: 0.20006
a: 0.70070 b: 0.34853 c: 0.34853 d: 0.34853 e: 0.20925 f: 0.20925 g: 0.20925 h: 0.20925
a: 0.80176 b: 0.37716 c: 0.37716 d: 0.37716 e: 0.21412 f: 0.21412 g: 0.21412 h: 0.21412
a: 0.85530 b: 0.39233 c: 0.39233 d: 0.39233 e: 0.21670 f: 0.21670 g: 0.21670 h: 0.21670
a: 0.88366 b: 0.40037 c: 0.40037 d: 0.40037 e: 0.21806 f: 0.21806 g: 0.21806 h: 0.21806
a: 0.89869 b: 0.40463 c: 0.40463 d: 0.40463 e: 0.21879 f: 0.21879 g: 0.21879 h: 0.21879
a: 0.90666 b: 0.40689 c: 0.40689 d: 0.40689 e: 0.21917 f: 0.21917 g: 0.21917 h: 0.21917
a: 0.91088 b: 0.40808 c: 0.40808 d: 0.40808 e: 0.21937 f: 0.21937 g: 0.21937 h: 0.21937
a: 0.91311 b: 0.40872 c: 0.40872 d: 0.40872 e: 0.21948 f: 0.21948 g: 0.21948 h: 0.21948
a: 0.91430 b: 0.40905 c: 0.40905 d: 0.40905 e: 0.21954 f: 0.21954 g: 0.21954 h: 0.21954
a: 0.91493 b: 0.40923 c: 0.40923 d: 0.40923 e: 0.21957 f: 0.21957 g: 0.21957 h: 0.21957
a: 0.91526 b: 0.40932 c: 0.40932 d: 0.40932 e: 0.21958 f: 0.21958 g: 0.21958 h: 0.21958
a: 0.91543 b: 0.40937 c: 0.40937 d: 0.40937 e: 0.21959 f: 0.21959 g: 0.21959 h: 0.21959
a: 0.91553 b: 0.40940 c: 0.40940 d: 0.40940 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91558 b: 0.40941 c: 0.40941 d: 0.40941 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91560 b: 0.40942 c: 0.40942 d: 0.40942 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91562 b: 0.40942 c: 0.40942 d: 0.40942 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91562 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
Average pagerank = 0.3778
象你所想象的那样，homepage页就是我们所说的主页有最高的PR，毕竟，它有最多的网页引用，有最多的链接指向它，但是怎么平均的PR变为了0.378了呢？这跟上面我们说所有网页的PR平均值等于1是不是有所冲突呢？是不是我们上面的结论是错误的呢？
当然不是。一切都是正确的，请大家看看这个External site 网页，他们的PR发生了什么呢？他们没有传递他们的PR，因为他们没有指向任何的网页，可以说他们浪费了他们的投票权，浪费了他们的PR。
注意这里的External Site不同于前面的pageD，前面的pageD是没有网页指向它，但是它有连接指向别的网页，所以它的PR值为最小值0.15，而这里的External Site页是没有指向别的页面的连接，但是却有别的页面指向它。
例3：让我们把那些外部网站指回到我们的首页中来，我们就可以看到平均值的变化：
大家看一下程序（程序4）
#!/usr/bin/perl
print "Content-Type: text/html\n\n
结果（4）
a: 0.00000 b: 0.00000 c: 0.00000 d: 0.00000 e: 0.00000 f: 0.00000 g: 0.00000 h: 0.00000
a: 0.15000 b: 0.19250 c: 0.19250 d: 0.19250 e: 0.18273 f: 0.18273 g: 0.18273 h: 0.18273
a: 1.13124 b: 0.47052 c: 0.47052 d: 0.47052 e: 0.22999 f: 0.22999 g: 0.22999 h: 0.22999
a: 1.81183 b: 0.66335 c: 0.66335 d: 0.66335 e: 0.26277 f: 0.26277 g: 0.26277 h: 0.26277
a: 2.28388 b: 0.79710 c: 0.79710 d: 0.79710 e: 0.28551 f: 0.28551 g: 0.28551 h: 0.28551
a: 2.61130 b: 0.88987 c: 0.88987 d: 0.88987 e: 0.30128 f: 0.30128 g: 0.30128 h: 0.30128
a: 2.83840 b: 0.95421 c: 0.95421 d: 0.95421 e: 0.31222 f: 0.31222 g: 0.31222 h: 0.31222
a: 2.99591 b: 0.99884 c: 0.99884 d: 0.99884 e: 0.31980 f: 0.31980 g: 0.31980 h: 0.31980
a: 3.10517 b: 1.02980 c: 1.02980 d: 1.02980 e: 0.32507 f: 0.32507 g: 0.32507 h: 0.32507
a: 3.18094 b: 1.05127 c: 1.05127 d: 1.05127 e: 0.32872 f: 0.32872 g: 0.32872 h: 0.32872
a: 3.23350 b: 1.06616 c: 1.06616 d: 1.06616 e: 0.33125 f: 0.33125 g: 0.33125 h: 0.33125
a: 3.26996 b: 1.07649 c: 1.07649 d: 1.07649 e: 0.33300 f: 0.33300 g: 0.33300 h: 0.33300
a: 3.29524 b: 1.08365 c: 1.08365 d: 1.08365 e: 0.33422 f: 0.33422 g: 0.33422 h: 0.33422
a: 3.31278 b: 1.08862 c: 1.08862 d: 1.08862 e: 0.33507 f: 0.33507 g: 0.33507 h: 0.33507
a: 3.32494 b: 1.09207 c: 1.09207 d: 1.09207 e: 0.33565 f: 0.33565 g: 0.33565 h: 0.33565
a: 3.33338 b: 1.09446 c: 1.09446 d: 1.09446 e: 0.33606 f: 0.33606 g: 0.33606 h: 0.33606
a: 3.33923 b: 1.09612 c: 1.09612 d: 1.09612 e: 0.33634 f: 0.33634 g: 0.33634 h: 0.33634
a: 3.34329 b: 1.09727 c: 1.09727 d: 1.09727 e: 0.33654 f: 0.33654 g: 0.33654 h: 0.33654
a: 3.34611 b: 1.09806 c: 1.09806 d: 1.09806 e: 0.33667 f: 0.33667 g: 0.33667 h: 0.33667
a: 3.34806 b: 1.09862 c: 1.09862 d: 1.09862 e: 0.33676 f: 0.33676 g: 0.33676 h: 0.33676
a: 3.34941 b: 1.09900 c: 1.09900 d: 1.09900 e: 0.33683 f: 0.33683 g: 0.33683 h: 0.33683
a: 3.35035 b: 1.09927 c: 1.09927 d: 1.09927 e: 0.33688 f: 0.33688 g: 0.33688 h: 0.33688
a: 3.35101 b: 1.09945 c: 1.09945 d: 1.09945 e: 0.33691 f: 0.33691 g: 0.33691 h: 0.33691
a: 3.35146 b: 1.09958 c: 1.09958 d: 1.09958 e: 0.33693 f: 0.33693 g: 0.33693 h: 0.33693
a: 3.35177 b: 1.09967 c: 1.09967 d: 1.09967 e: 0.33694 f: 0.33694 g: 0.33694 h: 0.33694
a: 3.35199 b: 1.09973 c: 1.09973 d: 1.09973 e: 0.33695 f: 0.33695 g: 0.33695 h: 0.33695
a: 3.35214 b: 1.09977 c: 1.09977 d: 1.09977 e: 0.33696 f: 0.33696 g: 0.33696 h: 0.33696
a: 3.35224 b: 1.09980 c: 1.09980 d: 1.09980 e: 0.33697 f: 0.33697 g: 0.33697 h: 0.33697
a: 3.35232 b: 1.09982 c: 1.09982 d: 1.09982 e: 0.33697 f: 0.33697 g: 0.33697 h: 0.33697
a: 3.35237 b: 1.09984 c: 1.09984 d: 1.09984 e: 0.33697 f: 0.33697 g: 0.33697 h: 0.33697
a: 3.35240 b: 1.09985 c: 1.09985 d: 1.09985 e: 0.33697 f: 0.33697 g: 0.33697 h: 0.33697
a: 3.35243 b: 1.09985 c: 1.09985 d: 1.09985 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35244 b: 1.09986 c: 1.09986 d: 1.09986 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35245 b: 1.09986 c: 1.09986 d: 1.09986 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35246 b: 1.09986 c: 1.09986 d: 1.09986 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35247 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35247 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35247 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35248 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35248 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
Average pagerank = 1.0000
通过结果我们发现了现在整个网络的平均PR又回到了1.0
例4，5，6，7，8，9．10，11，12，13
以下还有几个例子，在这里由于时间关系就不给大家一一讲解了，感兴趣的话大家可以跟我探讨一下。
结束语：
最后我想补充说一下，其实pagerank算法并不难，除了它有一个看起来令人感到害怕的公式，但是我们上面讲解的都是小系统中的PAGERANK的计算，当这个算法被应用于整个互联网，并且进行几百亿次的计算才能得出结果的时候，那么就非常的复杂了。
总而言之，pagerank就是网页评估的重要的方式，要想你的网页得到很好的PR值，我们还是有必要进行PR算法的研究的。
首先介绍一下Pagerank的来源，背景，pagerank作为一个被现在大型搜索引擎goolge所采用的算法，最初是来自于stanford大学计算机科学系的 sergey brin and lawrance page的博士论文，既The Anatomy of a Large-Scale Hypertextual Web Search Engine （一个大型超文本搜索引擎的解析）通俗的说，pagerank algorithm是搜索引擎google使用的一种网页重要性的评估方式，pagerank的值决定了网页在搜索结果中的排名。
大家现在对pagerank有了一个基本的了解。下面来介绍一下：
二．Google 简介特征及其系统结构、工作原理
1、google的简介：
大家都用过goolge来查询很多我们需要的资料，她是一个大型的搜索引擎，我们都知道现在有很多的中文搜索引擎，包括有百度(baidu)，yahoo的一搜（yisou），说句题外话，yahoo的一搜在前两天已经深情谢幕了，也就是说她已经不存在了，取而带之的，yahoo本身作为了一个搜索引擎出现在我们的面前了，你可以打开yahoo的首页，就会发现她已经改变了，除了上面这些我们还知道有sohu的sougou，她一个中文搜索引擎。
GOOGLE最初作为一个实验品在stanford大学产生，并随着发展成为当今世界最著名的搜索引擎，当然有一定的过程，但是她的工作原理也决定了她能成为最好的搜索引擎。
搜索引擎技术随着互联网的增长已经显著的提高了，在1994年，美国最早搜索引擎wwww，the world wide web worm，这个搜索引擎索引了11万个网页和可利用文档。在1997年11月，搜索引擎watch宣称已经索引了200万个网页,而在2000年，一个复杂的全球网页索引将包含超过1亿的文档。正是因为有如此巨大的网页数据，所以我们找到自己想要的网页数据就非常的困难，这也是GOOGLE产生的原因。GOOGLE的设计目的就在于改善搜索质量和提高搜索速度，并且作用于学术的搜索引擎的研究。
2、下面来介绍一下GOOGLE的系统特征：google有两个最重要的特征，正是这两个特征决定了google能产生出高精确度的搜索结果。
第一个是利用WEB的连接结构来为每一个网页计算一个质量排序值，也就是我们前面提到的pagerank值。第二个是google利用链接来改善搜索结果。
3、下面来讲一下GOOGLE的体系结构总揽及其工作原理（首先来看一张图）
(图一)在这部分，我们将给出一个高层次的整个GOOGLE的系统工作图。(如图一)
GOOGLE工作大致可以分为这么几部分：
第一部分，文件抓取过程。
大家看，这里有一个URL 服务器，用于给crawler，我们在这里将其称为抓取器或下载器，提供url地址的列表。可能有些同学对url不太明白，我顺便说一下，url全称是universal resourse location，即全球资源定位管理，我们都知道每个网站都有自己的服务器，也就是我们知道的所存放着网页文档的服务器。当然每个服务器都有自己的IP地址。URL服务器就是用于给抓取器提供这些网站服务器的IP地址。当IP地址给到抓取器后，抓取器就开始抓取或者下载这个服务器上的所有的WEB文档。当然我们在抓取的时候可以并行的抓取，上面我们列出了三个抓取器来并行的抓取网页。我们将抓取到的网页都存入到store sever，即存储服务器上。这个存储服务器再将网页压缩并且把他们存入数据仓库（repository）,这个数据仓库存储着每个网页的HTML也就是她的源代码。每个网页通过ZLIB压缩技术来进行压缩,在这个数据仓库中，每个网页文档都被一个接一个的存储，并且都加上了docid,lenghth,和URL地址等前缀。我们可以看一下它的数据存储结构图二
Figure 2. Repository Data Structure
图二：
第二部分，文件索引过程。
在GOOGLE系统中，文件索引保持了每个文件的全部信息，他采取的是一个固定的宽广ISAM（索引顺序存取法）。索引程序被两个服务器所执行，就是我们在上面看到的Indexer和sorter，为了区别这两个服务器，我们将indexer命名为索引器或分度器，而sorter为反索引起或反分度器。索引器将执行一系列的程序，他从repository（数据仓库）中读出文件，并将其解压缩，然后解析他们。每个文件被转换称一组字事件，我们字事件为采样数。这个采样数记录了文字，以及文字在文档中的位置，文字大小的近似值，他们的大小写。这个索引器就将这些采样数分布到一系列的数据桶(barrels)中，并且制造出一个部分前向的分类索引目录。在这里索引器indexer还要执行另一个重要的程序，即他要解析出每个网页的所有的链接，并把他们存入到一个锚文件anchors当中。这个锚文件中包含了每个连接的文本，和每个连接所指向的地址，每个链接出处的地址。Sorter也就是反索引器，就是要把前向索引目录经过加工变为反相索引目录。URL RESOLVER也就是URL分解器将从锚文件当中读出数据，并将相对的URL转换成一个绝对的URL。他将锚文本也就是链接文本插入到前项索引当中，结合着这个链接所指向的docID。这个URL分解器将产生一个连接数据库，这个数据库是每条记录由一对docID。这个链接数据库被用来计算所有网页的pagerank值。
第三部分，文件搜索过程
文件搜索的目的是为了有效的提供高质量的搜索结果。许多大的商业搜索引擎看起来已经取得了某种程度上的进步。因此GOOGLE花费了更多的时间来研究在搜索质量。当我们在GOOGLE中输入一个关键词进行查询的时候，GOOGLE首先会解析关键词并且在索引中查找我们关键词所对应的序号，找到与其匹配的内容，然后计算匹配网页的PAGERANK值，然后列出经过PAGERANK排序的网页序列，返回到浏览器给用户查看。
以上就是GOOGLE的大致的工作原理。当然其中还有一些细节问题没有谈到，但是这个不是我们今天要讲的主要内容，我们要讲的就是如何通过pagerank算法来给网页进行优化的排序。通过前面的介绍，我相信大家对pagerank算法有了一些具体的了解，明白了pagerank算法的用途和应用。
三、Pagerank算法：
那么什么是pagerank呢？
简单的说pagerank就是一个网页被互联网上所有的其他的网页投票所得到的投票数，它表明了一个网页的重要程度。一个指向某个网页的链接就被看做一个支持者的投票。如果没有链接指向那个网页，那么这个网页就没有支持者，也就没有投票数。（当然这里的投票是有节制的，不是一个投票对应着一个网页。
下面我们来看看在GOOGLE中用到的pagerank算法在最初是如何定义的：
我们假定网页A有T1。。。。Tn个网页指向它（或者页可以说有T1。。。。Tn个网页引用它）。变量d是一个衰减因子，它的取值范围在0到1之间。一般情况下，我们将衰减因子d设置为0.85。我们定义C（A）作为网页A所指向外部的链接的个数，也就是网页A里面的所有的链接个数。那么网页A的pagerank值可以这样得到：
PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
注意到所有的pagerank值形成了一个概率分布，所以所有网页的pagerank的平均值将是一。
当然这样做还不够清楚，让我们把它分为几部分来详细解释一下：
1． PR（Tn）代表了每一个引用网页本身的pagerank值，PR（T1）就代表了第一个引用网页的pagerank值，而PR（Tn）代表了最后一个引用网页的pagerank值。
2． C（Tn） 表示Tn这个网页里面所包含的链接的个数。
3． PR（Tn）/C（Tn） 如果网页A有一个来自于网页tn的链接，网页A将从tn中得到一个共享的比例分数PR（Tn）/C（Tn）
4． d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn)) 所有的分数被加在一起，但是为了制止其他网页有太多的影响，我们给它乘上了一个衰减因子d用来降低总的投票数，我们取d为0.85。
5． （1-d） 这部分是一个概率上的数学戏法。它意味着如果一个网页没有链接指向它，那么它仍然会有一个很小的pagerank值0.15（也就是1-0.85）
那么Pagerank是如何被计算的呢？
这正是问题有趣的地方，每一个网页的PR（也就是PAGERANK值，以后我们统一用PR来表示）依赖于指向它的网页的PR。但是我们并不知道那些网页的PR直到我们知道指向他们的其他网页的PR值，这样我们就陷入了一个死循环当中，我们就无法进行PR的计算了。
但是实际上并不是那样的，通过简单的迭代算法我们能够计算出PR的值，并且符合web的规格化链接矩阵的主要特征向量。我们能够继续进行计算一个网页的PR在不知道其他网页的PR值的时候。看起来很奇怪，但是，我们每一次运行计算都会得到一个近似的估计值，我们需要记下每一次计算后的估计值，然后重复多次计算直到这个估计值不在变动为止，这样得到的最后结果就是我们要求的PR。
让我们做一个最简单的例子：两个网页，每个网页都有一个网页引用，并且每个网页都只有一个连接指向外部。因为只有一个连接指向外部，所以：C(A)=1 ,C(B)=1.
让我们来推测一下：
假设1：
我们并不知道这两个网页的PR，所以我们假设他们都为1.0，然后做一些计算。
d = 0.85
PR(A) = (1 – d) + d(PR(B)/1)
PR(B) = (1 – d) + d(PR(A)/1)
就等于了
PR(A) = 0.15 + 0.85 * 1
= 1
PR(B) = 0.15 + 0.85 * 1
= 1
我们发现PR(A),PR(B)经过计算并没有改变，它与我们的假设一致，我们看来非常幸运，一次就得到了稳定的结果，也就是我们要求的值。
假设2
问题看起来太简单了，也许我们出错了。好的，让我们开始重新假设他们的PR都为0,然后重新计算：
PR(A) = 0.15 + 0.85 * 0
= 0.15
PR(B) = 0.15 + 0.85 * 0.15
= 0.2775 注意我们在前面算出了一个更好PR(A)的近似值，所以我们在这里用到了它。
然后再进行计算：
PR(A) = 0.15 + 0.85 * 0.2775
= 0.385875
PR(B) = 0.15 + 0.85 * 0.385875
= 0.47799375
再次计算：
And again
PR(A) = 0.15 + 0.85 * 0.47799375
= 0.5562946875
PR(B) = 0.15 + 0.85 * 0.5562946875
= 0.622850484375
我们这样一直计算下去的话，那么他们的PR值就会不断的增加。但是他们的PR会不会增加到1后就停止呢？这两个网页的PR会不会超过1呢？
让我们来看看下一个假设
假设3
让我们重新假设这两个网页的PR值,我们假设他们都能于40。然后我们来做一些循环测试：
PR(A)=40
PR(B)=40
第一次计算：
PR(A) = 0.15 + 0.85 * 40
= 34.25
PR(B) = 0.15 + 0.85 * 0.385875
= 29.1775
第二次：
PR(A) = 0.15 + 0.85 * 29.1775
= 24.950875
PR(B) = 0.15 + 0.85 * 24.950875
= 21.35824375
我们发现，这些数字，也就是两个网页的PR近似值再直线下降。如果我们继续计算下去，我们会发现他们将到达1并且停止改变。
这里有一段代码用于计算这个例子中的假设2：请大家看一下代码：（代码1）
#!/usr/bin/perl
print "Content-Type: text/html\n\n
\n";Back");
$damp = 0.85;
$a = 0;
$b = 0;
$i = 40; # loop 10 times
# forward links
# a -> b - 1 outgoing link
# b -> a - 1 outgoing link
# i.e. "backward" links (what's pointing to me?)
# a <= b
# b <= a
print "I've rounded to 5 decimal places to make the output
easier to read\n\n";
while ($i--) {
printf("a: %.5f b: %.5f\n", $a, $b);
$a = (1 - $damp) + $damp * ($b);
$b = (1 - $damp) + $damp * ($a);
}
printf("Average pagerank = %.4f\n", ($a + $b) / 2);
print("
大家再看一下代码的运行结果。（结果1）
I've rounded to 5 decimal places to make the output easier to read
a: 0.00000 b: 0.00000
a: 0.15000 b: 0.27750
a: 0.38588 b: 0.47799
a: 0.55629 b: 0.62285
a: 0.67942 b: 0.72751
a: 0.76838 b: 0.80313
a: 0.83266 b: 0.85776
a: 0.87909 b: 0.89723
a: 0.91265 b: 0.92575
a: 0.93689 b: 0.94635
a: 0.95440 b: 0.96124
a: 0.96705 b: 0.97200
a: 0.97620 b: 0.97977
a: 0.98280 b: 0.98538
a: 0.98757 b: 0.98944
a: 0.99102 b: 0.99237
a: 0.99351 b: 0.99449
a: 0.99531 b: 0.99602
a: 0.99661 b: 0.99712
a: 0.99755 b: 0.99792
a: 0.99823 b: 0.99850
a: 0.99872 b: 0.99891
a: 0.99908 b: 0.99922
a: 0.99933 b: 0.99943
a: 0.99952 b: 0.99959
a: 0.99965 b: 0.99970
a: 0.99975 b: 0.99979
a: 0.99982 b: 0.99985
a: 0.99987 b: 0.99989
a: 0.99991 b: 0.99992
a: 0.99993 b: 0.99994
a: 0.99995 b: 0.99996
a: 0.99996 b: 0.99997
a: 0.99997 b: 0.99998
a: 0.99998 b: 0.99998
a: 0.99999 b: 0.99999
a: 0.99999 b: 0.99999
a: 0.99999 b: 0.99999
a: 0.99999 b: 1.00000
a: 1.00000 b: 1.00000
Average pagerank = 1.0000
注意：这里有一个原则，无论你如何开始你的假设，一旦这个pagerank计算公式被设定，那么所有网页的PAGERANK的平均值将是1.0。
我们可以不直到其他网页的PR而求得我们所需要的PR值。但是这样经过了很多次的循环迭代运算。如何才能快速的得到我们要求的PR值呢？
对于一个大型网络来说，我们要重复计算多少次才能得出pagerank的值呢？这是一个比较难的问题，象互联网这样大的网络来说它肯能需要几千万次的重复计算。其中，d的取值，也就是衰减因子需要非常的巧妙的。如果它太高的话可能需要几个世纪PR才能被确定下来，如果太低的话，你也将重复的过了头，无论d的取值是过高还是过低，那么，这些数字将象钟摆一样不断的晃动而永远不会停止下来。
选择计算的次序将对我们有所帮助，答案将总是会出现，无论你选择什么样的次序，但是一些次序将使你更快的得到我们想要的结果。在下面的例子中，为了清晰我们用了非常简单的代码，大约需要20到40次的重复计算就能得到结果。
例1：
在这里不做重复的计算了，大家可以看一下这个程序：（代码2）
#!/usr/bin/perl
print "Content-Type: text/html\n\n
\n";Back to example 1");
$damp = 0.85;
$a = 0;
$b = 0;
$c = 0;
$d = 0;
$i = 40; # loop 40 times
# forward links
# a -> b, c - 2 outgoing links
# b -> c - 1 outgoing link
# c -> a - 1 outgoing link
# d -> a - 1 outgoing link
# i.e. "backward" links (what's pointing to me?)
# a <= c
# b <= a
# c <= a, b, d
# d - nothing
while ($i--) {
printf(
"a: %.5f b: %.5f c: %.5f d: %.5f\n",$a, $b, $c, $d
);
$a = 1 - $damp + $damp * $c;
$b = 1 - $damp + $damp * ($a/2);
$c = 1 - $damp + $damp * ($a/2 + $b + $d);
$d = 1 - $damp;
}
printf("Average pagerank = %.4f\n", ($a + $b + $c + $d) / 4);
print("
再来看一下结果。（结果2）
a: 0.00000 b: 0.00000 c: 0.00000 d: 0.00000
a: 0.15000 b: 0.21375 c: 0.39544 d: 0.15000
a: 0.48612 b: 0.35660 c: 0.78721 d: 0.15000
a: 0.81913 b: 0.49813 c: 1.04904 d: 0.15000
a: 1.04169 b: 0.59272 c: 1.22403 d: 0.15000
a: 1.19042 b: 0.65593 c: 1.34097 d: 0.15000
a: 1.28982 b: 0.69818 c: 1.41912 d: 0.15000
a: 1.35626 b: 0.72641 c: 1.47136 d: 0.15000
a: 1.40065 b: 0.74528 c: 1.50626 d: 0.15000
a: 1.43032 b: 0.75789 c: 1.52959 d: 0.15000
a: 1.45015 b: 0.76632 c: 1.54518 d: 0.15000
a: 1.46341 b: 0.77195 c: 1.55560 d: 0.15000
a: 1.47226 b: 0.77571 c: 1.56257 d: 0.15000
a: 1.47818 b: 0.77823 c: 1.56722 d: 0.15000
a: 1.48214 b: 0.77991 c: 1.57033 d: 0.15000
a: 1.48478 b: 0.78103 c: 1.57241 d: 0.15000
a: 1.48655 b: 0.78178 c: 1.57380 d: 0.15000
a: 1.48773 b: 0.78228 c: 1.57473 d: 0.15000
a: 1.48852 b: 0.78262 c: 1.57535 d: 0.15000
a: 1.48904 b: 0.78284 c: 1.57576 d: 0.15000
a: 1.48940 b: 0.78299 c: 1.57604 d: 0.15000
a: 1.48963 b: 0.78309 c: 1.57622 d: 0.15000
a: 1.48979 b: 0.78316 c: 1.57635 d: 0.15000
a: 1.48990 b: 0.78321 c: 1.57643 d: 0.15000
a: 1.48997 b: 0.78324 c: 1.57649 d: 0.15000
a: 1.49001 b: 0.78326 c: 1.57652 d: 0.15000
a: 1.49004 b: 0.78327 c: 1.57655 d: 0.15000
a: 1.49007 b: 0.78328 c: 1.57656 d: 0.15000
a: 1.49008 b: 0.78328 c: 1.57657 d: 0.15000
a: 1.49009 b: 0.78329 c: 1.57658 d: 0.15000
a: 1.49009 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49010 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49010 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49010 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49010 b: 0.78329 c: 1.57659 d: 0.15000
a: 1.49011 b: 0.78329 c: 1.57660 d: 0.15000
a: 1.49011 b: 0.78330 c: 1.57660 d: 0.15000
a: 1.49011 b: 0.78330 c: 1.57660 d: 0.15000
a: 1.49011 b: 0.78330 c: 1.57660 d: 0.15000
a: 1.49011 b: 0.78330 c: 1.57660 d: 0.15000
Average pagerank = 1.0000
所以这个例子中正确的PR为：
大家通过程序的执行结果可以看出，大约经过了20次的重复后这些PR值被确定下来
大家看看上面这个图中的PageD，也就时网页D，即使没有任何一个网页有链接指向它，它仍然得到了0.15的PR，这个正确吗？
让我们来亲手算一下，对于PageD，没有链接指向它，那么根据公式它的PR应该为：
PR(D) = (1-d) + d * (0)
= 0.15
无论做多少次你都会得到这个结果。
说明：每一个网页的最小PR值将为0.15。但是这个可能仅仅是在理论上的。因为有人说GOOGLE会把那些没有链接指向的页面从索引中删除。也就是说如果你的网页没有链接指向，那么它就不会出现在GOOGLE的搜索引擎当中了。
例2：
一个简单的有等级的网络结构：
大家再看一下程序。（程序3）
#!/usr/bin/perl
print "Content-Type: text/html\n\n
\n";Back to example 2");
$damp = 0.85;
$a = $b = $c = $d = $e = $f = $g = $h = 0;
$i = 40; # loop 40 times
# forward links
# a -> b, c, d - 3 outgoing links - home
# b -> a - 1 outgoing link - about
# c -> a - 1 outgoing link - products
# d -> a, e, f, g, h - 5 outgoing links - links
# e,f,g,h - nothing - external sites
# i.e. "backward" links (what's pointing to me?)
# a <= b, c, d
# b,c,d <= a
# e,f,g,h <= d
while ($i--) {
printf(
"a: %.5f b: %.5f c: %.5f d: %.5f e: %.5f f: %.5f g: %.5f h: %.5f\n",
$a, $b, $c, $d, $e, $f, $g, $h
);
$a = 1 - $damp + $damp * ($b + $c + $d/5);
$b = 1 - $damp + $damp * ($a/3);
$c = 1 - $damp + $damp * ($a/3);
$d = 1 - $damp + $damp * ($a/3);
$e = $f = $g = $h = 1 - $damp + $damp * ($d/5);
}
printf("Average pagerank = %.4f\n",
($a + $b + $c + $d + $e + $f + $g + $h) / 8);
print("
这个是结果（结果3）
a: 0.00000 b: 0.00000 c: 0.00000 d: 0.00000 e: 0.00000 f: 0.00000 g: 0.00000 h: 0.00000
a: 0.15000 b: 0.19250 c: 0.19250 d: 0.19250 e: 0.18273 f: 0.18273 g: 0.18273 h: 0.18273
a: 0.50998 b: 0.29449 c: 0.29449 d: 0.29449 e: 0.20006 f: 0.20006 g: 0.20006 h: 0.20006
a: 0.70070 b: 0.34853 c: 0.34853 d: 0.34853 e: 0.20925 f: 0.20925 g: 0.20925 h: 0.20925
a: 0.80176 b: 0.37716 c: 0.37716 d: 0.37716 e: 0.21412 f: 0.21412 g: 0.21412 h: 0.21412
a: 0.85530 b: 0.39233 c: 0.39233 d: 0.39233 e: 0.21670 f: 0.21670 g: 0.21670 h: 0.21670
a: 0.88366 b: 0.40037 c: 0.40037 d: 0.40037 e: 0.21806 f: 0.21806 g: 0.21806 h: 0.21806
a: 0.89869 b: 0.40463 c: 0.40463 d: 0.40463 e: 0.21879 f: 0.21879 g: 0.21879 h: 0.21879
a: 0.90666 b: 0.40689 c: 0.40689 d: 0.40689 e: 0.21917 f: 0.21917 g: 0.21917 h: 0.21917
a: 0.91088 b: 0.40808 c: 0.40808 d: 0.40808 e: 0.21937 f: 0.21937 g: 0.21937 h: 0.21937
a: 0.91311 b: 0.40872 c: 0.40872 d: 0.40872 e: 0.21948 f: 0.21948 g: 0.21948 h: 0.21948
a: 0.91430 b: 0.40905 c: 0.40905 d: 0.40905 e: 0.21954 f: 0.21954 g: 0.21954 h: 0.21954
a: 0.91493 b: 0.40923 c: 0.40923 d: 0.40923 e: 0.21957 f: 0.21957 g: 0.21957 h: 0.21957
a: 0.91526 b: 0.40932 c: 0.40932 d: 0.40932 e: 0.21958 f: 0.21958 g: 0.21958 h: 0.21958
a: 0.91543 b: 0.40937 c: 0.40937 d: 0.40937 e: 0.21959 f: 0.21959 g: 0.21959 h: 0.21959
a: 0.91553 b: 0.40940 c: 0.40940 d: 0.40940 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91558 b: 0.40941 c: 0.40941 d: 0.40941 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91560 b: 0.40942 c: 0.40942 d: 0.40942 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91562 b: 0.40942 c: 0.40942 d: 0.40942 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91562 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
a: 0.91563 b: 0.40943 c: 0.40943 d: 0.40943 e: 0.21960 f: 0.21960 g: 0.21960 h: 0.21960
Average pagerank = 0.3778
象你所想象的那样，homepage页就是我们所说的主页有最高的PR，毕竟，它有最多的网页引用，有最多的链接指向它，但是怎么平均的PR变为了0.378了呢？这跟上面我们说所有网页的PR平均值等于1是不是有所冲突呢？是不是我们上面的结论是错误的呢？
当然不是。一切都是正确的，请大家看看这个External site 网页，他们的PR发生了什么呢？他们没有传递他们的PR，因为他们没有指向任何的网页，可以说他们浪费了他们的投票权，浪费了他们的PR。
注意这里的External Site不同于前面的pageD，前面的pageD是没有网页指向它，但是它有连接指向别的网页，所以它的PR值为最小值0.15，而这里的External Site页是没有指向别的页面的连接，但是却有别的页面指向它。
例3：让我们把那些外部网站指回到我们的首页中来，我们就可以看到平均值的变化：
大家看一下程序（程序4）
#!/usr/bin/perl
print "Content-Type: text/html\n\n
\n";Back to example 3");
$damp = 0.85;
$a = $b = $c = $d = $e = $f = $g = $h = 0;
$i = 40; # loop 40 times
# forward links
# a -> b,c,d - 3 outgoing links - home
# b -> a - 1 outgoing link - about
# c -> a - 1 outgoing link - products
# d -> a,e,f,g,h - 5 outgoing links - links
# e,f,g,h -> a - 1 outgoing link - regain the lost votes
# i.e. "backward" links (what's pointing to me?)
# a <= b, c, d
# b,c,d <= a
# e,f,g,h <= d
while ($i--) {
printf(
"a: %.5f b: %.5f c: %.5f d: %.5f e: %.5f f: %.5f g: %.5f h: %.5f\n",
$a, $b, $c, $d, $e, $f, $g, $h
);
$a = 1 - $damp + $damp * ($b + $c + $d/5 + $e + $f + $g + $h);
$b = 1 - $damp + $damp * ($a/3);
$c = 1 - $damp + $damp * ($a/3);
$d = 1 - $damp + $damp * ($a/3);
$e = $f = $g = $h = 1 - $damp + $damp * ($d/5);
}
printf("Average pagerank = %.4f\n",
($a + $b + $c + $d + $e + $f + $g + $h) / 8);
print("
结果（4）
a: 0.00000 b: 0.00000 c: 0.00000 d: 0.00000 e: 0.00000 f: 0.00000 g: 0.00000 h: 0.00000
a: 0.15000 b: 0.19250 c: 0.19250 d: 0.19250 e: 0.18273 f: 0.18273 g: 0.18273 h: 0.18273
a: 1.13124 b: 0.47052 c: 0.47052 d: 0.47052 e: 0.22999 f: 0.22999 g: 0.22999 h: 0.22999
a: 1.81183 b: 0.66335 c: 0.66335 d: 0.66335 e: 0.26277 f: 0.26277 g: 0.26277 h: 0.26277
a: 2.28388 b: 0.79710 c: 0.79710 d: 0.79710 e: 0.28551 f: 0.28551 g: 0.28551 h: 0.28551
a: 2.61130 b: 0.88987 c: 0.88987 d: 0.88987 e: 0.30128 f: 0.30128 g: 0.30128 h: 0.30128
a: 2.83840 b: 0.95421 c: 0.95421 d: 0.95421 e: 0.31222 f: 0.31222 g: 0.31222 h: 0.31222
a: 2.99591 b: 0.99884 c: 0.99884 d: 0.99884 e: 0.31980 f: 0.31980 g: 0.31980 h: 0.31980
a: 3.10517 b: 1.02980 c: 1.02980 d: 1.02980 e: 0.32507 f: 0.32507 g: 0.32507 h: 0.32507
a: 3.18094 b: 1.05127 c: 1.05127 d: 1.05127 e: 0.32872 f: 0.32872 g: 0.32872 h: 0.32872
a: 3.23350 b: 1.06616 c: 1.06616 d: 1.06616 e: 0.33125 f: 0.33125 g: 0.33125 h: 0.33125
a: 3.26996 b: 1.07649 c: 1.07649 d: 1.07649 e: 0.33300 f: 0.33300 g: 0.33300 h: 0.33300
a: 3.29524 b: 1.08365 c: 1.08365 d: 1.08365 e: 0.33422 f: 0.33422 g: 0.33422 h: 0.33422
a: 3.31278 b: 1.08862 c: 1.08862 d: 1.08862 e: 0.33507 f: 0.33507 g: 0.33507 h: 0.33507
a: 3.32494 b: 1.09207 c: 1.09207 d: 1.09207 e: 0.33565 f: 0.33565 g: 0.33565 h: 0.33565
a: 3.33338 b: 1.09446 c: 1.09446 d: 1.09446 e: 0.33606 f: 0.33606 g: 0.33606 h: 0.33606
a: 3.33923 b: 1.09612 c: 1.09612 d: 1.09612 e: 0.33634 f: 0.33634 g: 0.33634 h: 0.33634
a: 3.34329 b: 1.09727 c: 1.09727 d: 1.09727 e: 0.33654 f: 0.33654 g: 0.33654 h: 0.33654
a: 3.34611 b: 1.09806 c: 1.09806 d: 1.09806 e: 0.33667 f: 0.33667 g: 0.33667 h: 0.33667
a: 3.34806 b: 1.09862 c: 1.09862 d: 1.09862 e: 0.33676 f: 0.33676 g: 0.33676 h: 0.33676
a: 3.34941 b: 1.09900 c: 1.09900 d: 1.09900 e: 0.33683 f: 0.33683 g: 0.33683 h: 0.33683
a: 3.35035 b: 1.09927 c: 1.09927 d: 1.09927 e: 0.33688 f: 0.33688 g: 0.33688 h: 0.33688
a: 3.35101 b: 1.09945 c: 1.09945 d: 1.09945 e: 0.33691 f: 0.33691 g: 0.33691 h: 0.33691
a: 3.35146 b: 1.09958 c: 1.09958 d: 1.09958 e: 0.33693 f: 0.33693 g: 0.33693 h: 0.33693
a: 3.35177 b: 1.09967 c: 1.09967 d: 1.09967 e: 0.33694 f: 0.33694 g: 0.33694 h: 0.33694
a: 3.35199 b: 1.09973 c: 1.09973 d: 1.09973 e: 0.33695 f: 0.33695 g: 0.33695 h: 0.33695
a: 3.35214 b: 1.09977 c: 1.09977 d: 1.09977 e: 0.33696 f: 0.33696 g: 0.33696 h: 0.33696
a: 3.35224 b: 1.09980 c: 1.09980 d: 1.09980 e: 0.33697 f: 0.33697 g: 0.33697 h: 0.33697
a: 3.35232 b: 1.09982 c: 1.09982 d: 1.09982 e: 0.33697 f: 0.33697 g: 0.33697 h: 0.33697
a: 3.35237 b: 1.09984 c: 1.09984 d: 1.09984 e: 0.33697 f: 0.33697 g: 0.33697 h: 0.33697
a: 3.35240 b: 1.09985 c: 1.09985 d: 1.09985 e: 0.33697 f: 0.33697 g: 0.33697 h: 0.33697
a: 3.35243 b: 1.09985 c: 1.09985 d: 1.09985 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35244 b: 1.09986 c: 1.09986 d: 1.09986 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35245 b: 1.09986 c: 1.09986 d: 1.09986 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35246 b: 1.09986 c: 1.09986 d: 1.09986 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35247 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35247 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35247 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35248 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
a: 3.35248 b: 1.09987 c: 1.09987 d: 1.09987 e: 0.33698 f: 0.33698 g: 0.33698 h: 0.33698
Average pagerank = 1.0000
通过结果我们发现了现在整个网络的平均PR又回到了1.0
例4，5，6，7，8，9．10，11，12，13
以下还有几个例子，在这里由于时间关系就不给大家一一讲解了，感兴趣的话大家可以跟我探讨一下。
结束语：
最后我想补充说一下，其实pagerank算法并不难，除了它有一个看起来令人感到害怕的公式，但是我们上面讲解的都是小系统中的PAGERANK的计算，当这个算法被应用于整个互联网，并且进行几百亿次的计算才能得出结果的时候，那么就非常的复杂了。
总而言之，pagerank就是网页评估的重要的方式，要想你的网页得到很好的PR值，我们还是有必要进行PR算法的研究的。