pagerank--网页排序的里程碑式算法

《pagerank--网页排序的里程碑式算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Pagerank--网页排序的里程碑式算法随着网络管制的逐渐严格，似乎网络环境越来越纯净而且安全了，而越来越多的域外内容也被干干净净的屏蔽，搜索引擎中充斥着根据相关法律法规和政策，部分搜索结果未予显示，和上百条重复累赘照抄照搬的链接。现在似乎只知百度不知google，当年的那个彻底改观了整个互联网的生态的公司，也许很快就彻底消失在下一代的眼中了。2011年9月27日google推出了newdoodle庆祝自己的13岁生日。2014年11月写此文纪念国内严格的网络管制“获得成功”。提到google就不的不提到它的搜索引擎，一个推动整个互联网向前跨越一个年代的产品，那么一个由网页排名

2、和搜索算法构成的搜索引擎，其核心功能是什么呢？自然是网页搜索，。而搜索出的链接是该散乱放置随机分配位置还是按照某些顺序决定其“重要程度”而进行排序放置呢？答案显而易见是后者。可是如何对网页排序才是最好的方式，一直是各个搜索引擎最最头疼的事情。搜索的最好方式就是有一个明确的排序，字典中按字母顺序排列，图书馆按照书的类别分类，商店的商品按种类分配，而且他们有很多共通特点;1.数量有限2.类别明显3.重复度很低4.及时性不强（不需要很快的速度更新）而互联网信息很任性的没有满足以上的任何一条，而在google推出Pagerank算法之前，主流的网页算法排序都基本差不多，就是对PageVi

3、ew（基本可以理解为访问量、点击量、链接量直接的意思）进行统计，统计所有包含词条的链接，然后进行数理统计。那么问题来了：统计工作哪家强？统计速度哪加快？其实读到这里大家已经可以看出这个方法的逻辑问题了：首先、必须对所有的每一种每一个相关词条进行数量统计，而且是抽样统计，还要建立在如此大的网络波动性的基础上。《蜗居》想必大家都看过，宋思明说:但凡能用钱解决的问题就不是大问题！只要拥有庞大的储存空间和一个具有强大的云计算能力的算法似乎这个问题就可以用资金搞定，但是我们需要想一想每毫秒都会产生成百万上千万的信息词条，那么我们需要多庞大的储存空间和计算能力的算法能持续解决这个问题呢。第二

4、这个方法可以让无孔不入的网络广告商们可以睡觉睡到自然醒，数钱数到手抽筋，他们只要把自己代理的广告植入一些公共引用类链接就可以收钱了，因为网民会帮他把访问量刷上去，都不用他自己动手，一段时间后，各大词条的置顶链接一定是他们的广告，不用多花一分钱的版费，最搞笑的是，在google之前的网络四大巨头的搜索引擎中搜索他们自己公司的名字，只有一个能出现在前十里，其他的都被我们强大的广告商们牢牢地占据了领先位置不可撼动。那这么说来似乎我们进入了一个死循环，这个问题难道就没有办法解决了？不，任何的事情都有解决办法，其实这个问题并没有想象的那么恐怖。1999年LarryPage和SergeyBr

5、in发表了一篇论文，文中介绍了一种叫做“Pagerank”的算法，介绍了一个新的概念，什么是：“网页的重要程度”。利用了一个网页即一个sub-system其链接被其他“重要”网页所链接的次数来计算的算法。这一思想来源于学术界评判学术论文重要性的通用方法，就是看这篇论文被引用的次数和引用者地位，一篇论文被诺贝尔奖获得者引用和被小学生引用肯定不一样。而按照上文的思路和定义决定一个网页（设为Ri）的排序时决定他地位因素有两点1.多少网页链接了Ri2.链接他的网页（Rx）的排序那么问题又来了，我们进入了一个“先有鸡还是先有蛋”的循环。其实这个问题并不难解决，Page和Brin又引进了一个

6、第四维度的变量，即分析一个虚拟用户在互联网上的漫游过程。他们假定：虚拟用户一旦访问了一个网页后，下一步将有相同的几率访问被该网页所链接的任何一个其它网页。换句话说，如果网页Ri有Ni个对外链接，则虚拟用户在访问了Ri之后，下一步点击那些链接当中的任何一个的几率均为1/Ni。初看起来，这一假设并不合理，因为任何用户都有偏好，怎么可能以相同的几率访问一个网页的所有链接呢？但如果我们考虑到佩奇和布林的虚拟用户实际上是对互联网上全体用户的一种平均意义上的代表，这条假设就不象初看起来那么不合理了。那么网页的排序由什么来决定呢？是由该用户在漫游了很长时间——理论上为无穷长时间——后访问各网页

7、的几率分布来决定，访问几率越大的网页排序就越靠前。、为了将这一分析数学化，我们用pi(n)表示虚拟用户在进行第n次浏览时访问网页Ri的几率。接下来我们把这个问题化简然后一步一步由简变繁，先建立一个最小的模型，一个拥有XYZ三个单元的模型，最开始给定XYZ三个变量均等的Pagerank值m，然后按照箭头的方向将自身的值均分然后按照箭头方向进行数值交换，最后数值会稳定在某个数上。例如：设m=1第一次交换时X’=X/3+Y/2Y’=X/3+Y/2+Z/2Z’=X/3+Z/2利用平稳马尔