pagerank算法讲解

PageRank算法介绍目录背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算背景介绍Web上超链接结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量。SergeyBrin(谢尔盖·布林)和LawrencePage(拉里·佩奇)在1998年提出了PageRank算法，同年J.Kleinberg（J·克莱因伯格）提出了HITS算法LawrencePage,SergeyBrin,RajeevMotwani,TerryWinograd,'ThePageRankCitationRanking:BringingOrdertotheWeb',1998,~backrub/pageranksub.ps为了更高效地计算PageRank,以下是改良以后的一篇论文。TaherH.Haveliwala,‘EfficientComputationofPageRank’,StanfordTechnicalReport,1999,(TM)是美国Google公司的登记注册商标。Google查询过程Google查询的全过程通常不超过半秒时间，但在这短短的时间内需要完成多个步骤，然后才能将搜索结果交付给搜索信息的用户。PageRank?Pagerank创始人：拉里佩奇(LarryPage)—Google创始人之一应用：是Google用来衡量一个网站的好坏的唯一标准。PageRank的提出Google的创始人之一LarryPage于1998年提出了PageRank，并应用在Google搜索引擎的检索结果排序上，该技术也是Google早期的核心技术之一LarryPage是Google的创始首席执行官，2001年4月转任现职产品总裁。他目前仍与EricSchmidt和SergeyBrin一起共同负责Google的日常运作。他在斯坦福大学攻读计算机科学博士学位期间，遇到了SergeyBrin，他们于1998年合伙创立Google。目录背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算Google的网页排序在Google中搜索“体育新闻”Google的网页排序在Google中搜索“体育新闻”搜索引擎工作的简要过程如下针对查询词“体育新闻”进行分词——》“体育”、“新闻”根据建立的倒排索引，将同时包含“体育”和“新闻”的文档返回，并根据相关性进行排序这里的相关性主要是基于内容的相关性但是会有一些垃圾网页，虽然也包含大量的查询词，但却并非满足用户需要的文档，如下图，一个网页中虽然出现了四次“体育新闻”但却不是用户所需要的因此，页面本身的重要性在网页排序中也起着很重要的作用查询词和文档的相关性Google的网页排序在Google中搜索“体育新闻”Google的网页排序如何度量网页本身的重要性呢？互联网上的每一篇html文档除了包含文本、图片、视频等信息外，还包含了大量的链接关系，利用这些链接关系，能够发现某些重要的网页直观地看，某网页A链向网页B，则可以认为网页A觉得网页B有链接价值，是比较重要的网页。某网页被指向的次数越多，则它的重要性越高；越是重要的网页，所链接的网页的重要性也越高。AB网页是节点，网页间的链接关系是边Google的网页排序如何度量网页本身的重要性呢？比如，新华网体育在其首页中对新浪体育做了链接，人民网体育同样在其首页中对新浪体育做了链接可见，新浪体育被链接的次数较多；同时，人民网体育和新华网体育也都是比较“重要”的网页，因此新浪体育也应该是比较“重要”的网页。新华网体育人民网体育Google的网页排序一个更加形象的图链向网页E的链接远远多于链向网页C的链接，但是网页C的重要性却大于网页E。这是因为因为网页C被网页B所链接，而网页B有很高的重要性。数量与质量Http网页链接示意图目录背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算什么是PageRankPageRank是一种在搜索引擎中根据网页之间相互的链接关系计算网页排名的技术。PageRank是Google用来标识网页的等级或重要性的一种方法。其级别从1到10级，PR值越高说明该网页越受欢迎（越重要）。PageRank近似于一个用户，是指在Internet上随机地单击链接将会到达特定网页的可能性。通常，能够从更多地方到达的网页更为重要，因此具有更高的PageRank。如果要查看此站点PageRank值，请安装GOOGLE工具条并启用PageRank特性，或者在firefox安装SearchStatus插件。Pagerank算法原理：PageRank的核心思想PageRank是基于「从许多优质的网页链接过来的网页，必定还是优质网页」的回归关系，来判定所有网页的重要性。•链入链接数(单纯的意义上的受欢迎度指标)•链入链接是否来自推荐度高的页面(有根据的受欢迎指标)•链入链接源页面的链接数(被选中的几率指标)因此，如果从类似于Yahoo!那样的PageRank非常高的站点被链接的话，仅此网页的PageRank也会一下子上升；相反地，无论有少链入链接数，如果全都是从那些没有多大意义的页面链接过来的话，PageRank也不会轻易上升。PageRank简单计算：假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面都链向A，那么A的PR（PageRank）值将是B，C及D的和。继续假设B也有链接到C，并且D也有链接到包括A的3个页面。一个页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。换句话说，根据链出总数平分一个页面的PR值。PageRank的简单计算过程PageRank的简化模型可以把互联网上的各网页之间的链接关系看成一个有向图。假设冲浪者浏览的下一个网页链接来自于当前网页。建立简化模型：对于任意网页Pi，它的PageRank值可表示为如下：其中Bi为所有链接到网页i的网页集合，Lj为网页j的对外链接数（出度）。iBjjjiLPRPR简化模型面临的缺陷实际的网络超链接环境没有这么理想化，PageRank会面临两个问题：•Rankleak•RanksinkRankLeakPR(A)PR(B)PR(C)PR(D)初始0.250.250.250.25一次迭代0.1250.1250.250.25二次迭代0.1250.1250.1250.25三次迭代0.1250.1250.1250.125……………n次迭代0000Rankleak：一个独立的网页如果没有外出的链接就产生等级泄漏解决办法：1.将无出度的节点递归地从图中去掉，待其他节点计算完毕后再加上2.对无出度的节点添加一条边，指向那些指向它的顶点RankSinkPR(A)PR(B)PR(C)PR(D)初始0.250.250.250.25一次迭代00.3750.250.375二次迭代00.3750.3750.25三次迭代00.250.3750.375四次迭代00.3750.250.375五次迭代0………Ranksink：整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生Ranksink目录背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算PageRank的随机浏览模型假定一个上网者从一个随机的网页开始浏览，上网者不断点击当前网页的链接开始下一次浏览。但是，上网者最终厌倦了，开始了一个随机的网页。随机上网者用以上方式访问一个新网页的概率就等于这个网页PageRank值。①这种随机模型更加接近于用户的浏览行为；②一定程度上解决了rankleak和ranksink的问题；③保证pagerank具有唯一值。随机浏览模型的图表示设定任意两个顶点之间都有直接通路，在每个顶点处以概率d按原来蓝色方向转移，以概率1-d按红色方向转移。随机浏览模型的邻接表表示由于网页数目巨大，网页之间的连接关系的邻接矩阵是一个很大的稀疏矩阵,采用邻接表来表示网页之间的连接关系.随机浏览模型的PageRank公式：N:网络中网页总数d:阻尼因子，通常设为0.85,d即按照超链接进行浏览的概率；1-d：随机跳转一个新网页的概率PR(pj):网页pj的PR值L(pj)：网页pj的链出网页数一个页面的PageRank是由其他页面的PageRank计算到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），由于等式PR=A*PR满足马尔可夫链的性质，如果马尔可夫链收敛，则PR存在唯一解.通过迭代计算得到所有节点的PageRank值。那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。马尔可夫链收敛定理改进LarryPage和SergeyBrin两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。由于互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。LarryPage和SergeyBrin两人利用稀疏矩阵计算的技巧，大大的简化了计算量。目录背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算PageRank的计算•互联网是一个有向图•每一个网页是图的一个顶点•网页间的每一个超链接是图的一个有向边•用邻接矩阵来表示图，即：定义邻接矩阵为G，若网页j到网页i有超链接，则；反之。•显然，如果网页有N个，则矩阵为N×N的0、1方阵。1ijg0ijg多个网页相互链接的图对应的邻接矩阵（这里将0,1值用二值图像显示，黑色代表0，白色代表1）PageRank的计算•定义邻接矩阵为G，若网页j到网页i有超链接，则；反之，。•记矩阵G的列和、行和分别是•它们分别给出了页面j的链出链接数目和链入链接数目iijjgcjijigr1ijg0ijgPageRank的计算•假设我们在上网的时侯浏览页面并选择下一个页面，这个过程与过去浏览过哪些页面无关，而仅依赖于当前所在的页面，那么这一选择过程可以认为是一个有限状态、离散时间的随机过程，其状态转移规律用Markov链描述。•定义转移概率矩阵)(ijaAjijijcganji...1,PageRank的计算•根据Markov链的基本性质，对于正则Markov链，存在平稳分布，满足•表示在极限状态（转移次数趋于无限）下各网页被访问的概率分布。•定义为网页的PageRank向量，表示第i个网页的PageRank值TNxxx),,(21Aiix1ix求矩阵A的特征值1对应的特征向量某7个网页之间的链接关系图网页链接图的邻接矩阵0110110101100010011001000100100101100001001000000G=PageRank的计算011/201/41/201/501/21/30001/5001/31/4001/50001/4001/5001/301/2100001/4001/5000000A=状态转移概率矩阵APageRank的计算0.6994565338373890.3828604185215180.3239588156720540.2429691117540400.4123112199462510.1030778049865630.1398913067674780.3035143769968050.1661341853035140.1405750798722040.1054313