PageRank算法简析

摘要

伴随着互联网的发展,网络资源已经越来越复杂与繁琐,想在浩瀚的网页中找到用户所需要的信息也变得十分复杂。因此需要按某种规律对搜索出的信息进行自动排列，才能使用户更高效率地查找信息。搜索引擎技术为解决这一难题做出了突出贡献，搜索引擎提供的结果集中页面质量的好坏以及高质量的页面能否在结果集中有较好的排名，对搜索引擎用户来说具有重要意义，同时也是衡量搜索引擎技术优劣的关键指标，所以对页面进行重要性评估并按重要性排序是搜索引擎要解决的技术核心。

本文中所要探讨的Google搜索引擎最初是斯坦福大学的博士研究生Sergey Brin和Lawrence Page实现的一个原型系统，现在已经发展成为WWW上最好的搜索引擎之一。Google的体系结构类似于传统的搜索引擎，它与传统的搜索引擎最大的不同处在于对网页进行了基于权威值的排序处理，使最重要的网页出现在结果的最前面。Google通过PageRank元算法计算出网页的PageRank值，从而决定网页在结果集中的出现位置，PageRank值越高的网页，在结果中出现的位置越前。

Google的PageRank根据网站的外部链接和内部链接的数量和质量俩衡量网站的价值。PageRank背后的概念是，每个到页面的链接都是对该页面的一次投票，被链接的越多，就意味着被其他网站投票越多。这个就是所谓的“链接流行度”——衡量多少人愿意将他们的网站和你的网站挂钩。PageRank这个概念引自学术中一篇论文的被引述的频度——即被别人引述的次数越多，一般判断这篇论文的权威性就越高。PageRank是Google衡量网页重要性的工具，测量值范围为从1至10，分别表示某网页的重要性。在Google工具栏可以随时获得某网页的PageRank值。

在这里我们将透视PageRank的一些特殊之处，从而对其能够获得较为深入的了解，使广大用户能够更好的使用和了解Googel。

关键词：搜索引擎，google，PageRank算法

一、引言

万维网WWW（World Wide Web）是一个巨大的，分布全球的信息服务中心，正在以飞快的速度扩展。1998年WWW上拥有约3.5亿个文档，每天增加约1百万的文档，不到9个月的时间文档总数就会翻一番。WEB上的文档和传统的文档比较，有很多新的特点，它们是分布的，异构的，无结构或者半结构的，这就对传统信息检索技术提出了新的挑战。

  传统的WEB搜索引擎大多数是基于关键字匹配的，返回的结果是包含查询项的文档，也有基于目录分类的搜索引擎。这些搜索引擎的结果并不令人满意。有些站点有意提高关键字出现的频率来提高自身在搜索引擎中的重要性，破坏搜索引擎结果的客观性和准确性。另外，有些重要的网页并不包含查询项。搜索引擎的分类目录也不可能把所有的分类考虑全面，并且目录大多靠人工维护，主观性强，费用高，更新速度慢。

    Google的Page Rank排序算法在很大程度上解决了这一难题，关于Page Rank

算法的探讨，下面的章节会有详述。第二代搜索引擎规模是在互联网数据库极大

丰富的背景下产生的，也是在互联息过载和信息迷向的时期到来，搜索引擎

在一定程度上缓解了这些问题，但互联网数据依然在增加，信息过载的问题，时

刻对搜索引擎带来冲击。

二、算法概念 

PageRank[1]取自Google 的创始人Larry Page, 它是Google 排名运算法则(排名公式)的一部分，用来标识网页的等级和重要性。

传统情报检索理论中确定学术文献权威性的重要方法之一就是引文分析方法，它根据引文的数量来确定文献的权威性。PageRank算法的发明者，Page对互联网络超链接拓扑结构和文献引文分析机制的相似性进行了研究，把引文分析思想借鉴到互联网络网页重要性的计算中来，利用互联网络自身的超链接拓扑结构给所有的网页确定一个重要性的等级数。

当从网页A链接到网页B时，就认为“网页A投了网页B一票"，增加了网页B的重要性。最后根据网页的得票数评定其重要性，以此来帮助实现排序算法的优化，而这个重要性的量化指标就是Page Rank值。

但是互联网络上的网页和学术论文的差别很大。首先学术论文的出版发表是非常严格的，而网页的发布非常自由、成本很低并缺乏控制，用一个简单的程序就可以产生大量的网页和超链接。

另外，学术论文的引文一般和该文的领域有关系，而网页的超链接范围却可以很广。可见简单的超链接数量计算并不能客观真实地反映互联网络中网页的重要性，所以PageRank算法除了考虑网页得票数(即超链接)的纯数量之外，还要分析为其投票的网页的重要性，因为网页的重要性决定着同时也依赖于其他网页的重要性，重要的网页所投的票有助于增强其他网页的“重要性，f261。简单地说Page-Rank算法就是要从互联网络的超链接结构中计算出网页的重要性。

三、pagerank原理

PR级别从1 到10 级，PR 值越高说明该网页越受欢迎( 越重要) 。一般搜索引擎将PageRank 值与网页搜索结果相似度共同作为搜索结果的排序依据。PageRank 算法的具体思路是，将某个页面的PageRank 除以存在于这个页面的正向链接,由此得到的值分别和正向链接指向的页面的PageRank 相加, 即得到了被链接的页面的PageRank。算法基于“从许多优质的网页链接过来的网页, 必定还是优质网页”的回归关系, 来判定所有网页的重要性。一个网页的得票越多, 则认为它的重要性也就越高。进一步说, 投票网页的重要性也决定着票本身的重要程度。PageRank 的算法如下:

PR(A)=(1- d)+d(PR(T1)/C(T1)+L+PR(Tn)/C(Tn)) ( 1)

公式中的PR 代表页面的PageRank 数值,T1～Tn 代表有链接指向页面A 的网页, C 是网页出链接的数量, d[2]是阻尼系数(常数, Google通常取值0. 85)。由( 1) 式可知, 计算某个页面的PageRank 值实际上是一个迭代的过程, 计算结果的精确程度依赖于初值的选取和迭代的次数。对于初值一般取1, 而为了保证实际应用中这个结果总是收敛的, 则加入了阻尼系数d。另外需要说明的是, 在IE 上安装了Google 工具栏的用户也许看到工具栏上的PageRank 显示条, 这个工具可以即时地反映出IE 当前访问的网页在Google 中的PageRank 值, 该值在0 至10 的范围内变化。这个值并非该页面的真实PR 值, 而是真实PR 值的一个对数指标, 对数基应该是5- 6 范围内的某个数值。

四、PageRank及其相关算法比较

PageRank                                                     基本思想：如果网页T存在一个指向网页A的连接，则表明T的所有者认为A比较重要，从而把T的一部分重要性得分赋予A。这个重要性得分值为：PR（T）/C(T) 。其中PR（T）为T的PageRank值，C(T)为T的出链数，则A的PageRank值为一系列类似于T的页面重要性得分值的累加。 

优点：是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。 

不足：人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低；另外，PageRank有很严重的对新网页的歧视。

Topic-Sensitive PageRank（主题敏感的PageRank）

基本思想：针对PageRank对主题的忽略而提出。

核心思想：通过离线计算出一个PageRank向量集合，该集合中的每一个向量与某一主题相关，即计算某个页面关于不同主题的得分。主要分为两个阶段：主题相关的PageRank向量集合的计算和在线查询时主题的确定。 

优点：根据用户的查询请求和相关上下文判断用户查询相关的主题（用户的兴趣）返回查询结果准确性高。 

不足：没有利用主题的相关性来提高链接得分的准确性。 

Hilltop

基本思想：与PageRank的不同之处：仅考虑专家页面的链接。主要包括两个步骤：专家页面搜索和目标页面排序。 

优点：相关性强，结果准确。 

不足：专家页面的搜索和确定对算法起关键作用，专家页面的质量决定了算法的准确性，而专家页面的质量和公平性难以保证；忽略了大量非专家页面的影响，不能反应整个Internet的；当没有足够的专家页面存在时，返回空，所以Hilltop适合对于查询排序进行求精。

Google对PageRank的解释 

在Google网站上有一个专门的域名介绍PageRank（http://www.Google.com/technology/） 

　　PageRank完全依靠的是网络的民主特性，利用大量的链接结构表明某个单独页面的价值。本质上来说，Google把链接转换为一次投票，当从网页A链接到网页B时，Google就认为“网页A投了网页B一票”。 Google也不是纯粹考虑投票的数量，还对投票的网页进行分析。本身很重要的网页的投票有助于增强其他对方网页的重要度。 

　　重要的是，Google会记录每次的搜索行为，高质量的网站能够获得较高的PageRank分值。当然，重要的网页如果不能匹配你的查询就没有任何价值。所以，Google把PageRank技术及文本匹配技术进行结合从而搜索出既重要又相关的的结果。Google的匹配技术不是只考虑词条在网页上的出现次数，而是检查网页内容（及链接网页的内容）的所有方面，从而决定该网页是否匹配你的查询。 

更多信息访问Google PageRank介绍： 

搜索引擎排名与PageRank的关系 

　　虽然每个搜索引擎都严格保密各自的明确的搜索算法，但是搜索引擎分析人士相信搜索引擎结果（排名列表）是“Page Relevance”与“PageRank”因素综合承继的结果。 

    Ranking = (Page Relevance) x (PageRank)  

PageRank逻辑算法无疑是具有重大意义的，而且这种算法不能够被网管人员轻易操纵。Google的搜索结果能够显示出如此高的相关性无疑也是它能够获得彻底成功的重要原因之一。大多数其他搜索引擎已经完全采用同类模式作为自己的搜索算法，而有的搜索引擎将这种算法在决定结果排名中的重要程度进行定义后应用与自己的搜索结果中。 

Google 工具栏 

　　Google工具栏供人免费下载安装，除了某些有用的功能外，比较显著的一个特点就是它可以告诉用户目前正在访问的每个网页的PageRank值。 

　　下载后的Google工具栏位于浏览器窗口下部，可随时随地进行网上搜索。工具栏显示出每个页面从1－10不等的PageRank分值。对于Google未索引的网页，工具栏不会显示出该页的PageRank分值。需要提醒的是，该分值是针对网页而言，而非网站。 

注：PR值越高，说明营销人员要针对相应的搜索词条获得较高的排名位置就有更多的竞争。所以，我们建议根据关键词优化网页的PR值。 

影响google PageRank的因素

　　1 与pr高的网站做链接: 

　　2 内容质量高的网站链接 

　　3 加入搜索引擎分类目录 

　　4 加入免费开源目录 

　　5 你的链接出现在流量大、知名度高、频繁更新的重要网站上 

　　6 google对PDF格式的文件比较看重。 

　　7 安装Google工具条 

　　8 域名和tilte标题出现关键词与meta标签等 

　　9 反向连接数量和反向连接的等级 

　　10 Google抓取您网站的页面数量 

11 导出链接数量

链接流行度 

　　“链接流行度”系统是基于网页获得的链接的数量及质量而定的。也就是说，指向你的网页的链接数量越多，你的网页将被搜索引擎认为越重要。数量并不是决定网站重要度的唯一因素，重要度还取决于其他因素，包括被链接到本站点的站点的质量、他们的内容的质量及与本站点的行业相关性等。 

　　链接到本站点的网页会把PageRank的部分分值分配到本站点。所以链接页面的PageRank分值越高，分配给本站点的分值也就越高。 

　　PageRank也会被链接页面商店所有导出链接所瓜分。譬如，同样PR为5的链接网页，导出链接只有15个的网页会比导出链接为100个的网页分配给你更多的分值。 所以重要的是要从PR值较高并且总体导出链接数量较少网页才能获得安全链接。 

　　最简单的检测网站流行度的方法就是利用Google搜索，方法如下： link:www.yoursite.com ，其它主要搜索引擎在搜索你的链接流行度时都有不同的规则。 

建立链接流行度提高PageRank 

　　建立链接流行度是搜索引擎营销的一个重要方面。尽管认为的提高PageRank不是意见容易的事，但是你通过改善链接流行度就可以不难做到。通过长期不懈的关注建立链接的工作，你就会提高站点的PageRank，大大改善自己的站点排名。就在不久前，Google及其他搜索引擎配制了某些类似与PageRank的算法成分（如TSPR”Topic Sensitive PageRank”Hilltop“Links from expert documents”），进一步将决定排名的比重放置在页面以外因素上。 

随着页面以外因素在网站排名中受到重视，所以提高加强这些因素的重视就变得越来越重要。当越来越多的网管意识到PageRank及链接流行度的重要性时，就不难在同行业中与其他站点进行链接交换了。

参考文献：

厦门大学系统与控制研究中心 张光年、李茂青《基于PageRank 算法的一种搜索引擎优化方法及实现》

西北大学 县小平《搜索引擎PageRank算法研究》

北京交通大学 韩洪光《搜索引擎分析——基于Page Rank算法的研究与改进》

河海大学 陈洁惠《搜索引擎排序算法的研究》

www.baidu.com