pagerank算法讲解.ppt

《pagerank算法讲解.ppt》由会员分享，可在线阅读，更多相关《pagerank算法讲解.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、背景介绍背景介绍Web上超链接结构是个非常丰富和重要的资源，如果能够充分利用的话，可以极大的提高检索结果的质量。Sergey Brin(谢尔盖布林 )和Lawrence Page(拉里佩奇)在1998年提出了PageRank算法，同年J. Kleinberg（J克莱因伯格）提出了HITS算法Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, The PageRank Citation Ranking: Bringing Order to the Web, 1998, http:/www-db.stanford.edu/back

2、rub/pageranksub.ps 为了更高效地计算 PageRank,以下是改良以后的一篇论文。Taher H. Haveliwala, Efficient Computation of PageRank, Stanford Technical Report, 1999, http:/dbpubs.stanford.edu:8090/pub/1999-31 PageRank(TM) 是美国 Google 公司的登记注册商标。Google查询过程Google 查询的全过程通常不超过半秒时间，但在这短短的时间内需要完成多个步骤，然后才能将搜索结果交付给搜索信息的用户。 PageRank?Pag

3、erank创始人：拉里佩奇(Larry Page(Larry Page ) ) GoogleGoogle创始人之一创始人之一应 用：是Google用来衡量一个网站 的好坏的唯一标准。 PageRank的提出Google的创始人之一Larry Page于1998年提出了PageRank，并应用在Google搜索引擎的检索结果排序上，该技术也是Google早期的核心技术之一Larry Page是Google的创始首席执行官，2001年4月转任现职产品总裁。他目前仍与Eric Schmidt和Sergey Brin一起共同负责 Google的日常运作。他在斯坦福大学攻读计算机科学博士学位期间，遇到了

4、Sergey Brin，他们于1998年合伙创立Google。目录 背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算Google的网页排序在Google中搜索“体育新闻”Google的网页排序在Google中搜索“体育新闻”搜索引擎工作的简要过程如下针对查询词“体育新闻”进行分词“体育”、“新闻”根据建立的倒排索引，将同时包含“体育”和“新闻”的文档返回，并根据相关性进行排序这里的相关性主要是基于内容的相关性但是会有一些垃圾网页，虽然也包含大量的查询词，但却并非满足用户需要的文档，如下图，一个网页中虽然出现了四次“体育新闻”但却不是用户所

5、需要的因此，页面本身的重要性在网页排序中也起着很重要的作用查询词和文档的相关性Google的网页排序在Google中搜索“体育新闻”Google的网页排序如何度量网页本身的重要性呢？ 互联网上的每一篇html文档除了包含文本、图片、视频等信息外，还包含了大量的链接关系，利用这些链接关系，能够发现某些重要的网页直观地看，某网页A链向网页B，则可以认为网页A觉得网页B有链接价值，是比较重要的网页。 某网页被指向的次数越多，则它的重要性越高；越是重要的网页，所链接的网页的重要性也越高。AB网页是节点，网页间的链接关系是边Google的网页排序如何度量网页本身的重要性呢？比如，新华网体育在其首页中对新

6、浪体育做了链接，人民网体育同样在其首页中对新浪体育做了链接可见，新浪体育被链接的次数较多；同时，人民网体育和新华网体育也都是比较“重要”的网页，因此新浪体育也应该是比较“重要”的网页。新华网体育人民网体育Google的网页排序一个更加形象的图链向网页E的链接远远多于链向网页C的链接，但是网页C的重要性却大于网页E。这是因为因为网页C被网页B所链接，而网页B有很高的重要性。Http网页链接示意图目录 背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算什么是PageRank PageRank是一种在搜索引擎中根据网页之间相互的链接关系计算网页排

7、名的技术。 PageRank是Google用来标识网页的等级或重要性的一种方法。其级别从1到10级，PR值越高说明该网页越受欢迎（越重要）。 PageRank近似于一个用户，是指在Internet上随机地单击链接将会到达特定网页的可能性。通常，能够从更多地方到达的网页更为重要，因此具有更高的PageRank。 如果要查看此站点PageRank值，请安装GOOGLE工具条并启用PageRank特性，或者在firefox安装SearchStatus插件。Pagerank算法原理：PageRank 的核心思想 PageRank 是基于从许多优质的网页链接过来的网页，必定还是优质网页从许多优质的网页链

8、接过来的网页，必定还是优质网页的回归关系，来判定所有网页的重要性。链入链接数链入链接数 (单纯的意义上的受欢迎度指标) 链入链接链入链接是否来自推荐度高的页面 (有根据的受欢迎指标) 链入链接源链入链接源页面的链接数 (被选中的几率指标) 因此，如果从类似于 Yahoo! 那样的 PageRank 非常高的站点被链接的话，仅此网页的 PageRank 也会一下子上升；相反地，无论有少链入链接链入链接数，如果全都是从那些没有多大意义的页面链接过来的话，PageRank 也不会轻易上升。PageRank简单计算： 假设一个由只有假设一个由只有4个页面组成的集合：个页面组成的集合：A，B，C和和D。

9、如果所有页面。如果所有页面都链向都链向A，那么，那么A的的PR（PageRank）值将是）值将是B，C及及D的和。的和。 继续假设继续假设B也有链接到也有链接到C，并且，并且D也有链接到包括也有链接到包括A的的3个页面。一个个页面。一个页面不能投票页面不能投票2次。所以次。所以B给给每个页面每个页面半票。半票。以同样的逻辑，以同样的逻辑，D投出的投出的票只有票只有三分之一三分之一算到了算到了A的的PageRank上。上。 换句话说，换句话说，根据链出总数平分一个页面的根据链出总数平分一个页面的PR值值。 PageRank的简单计算过程 PageRank的简化模型可以把互联网上的各网页之间的链接

10、关系看成一个有向图。假设冲浪者浏览的下一个网页链接来自于当前网页。建立简化模型：对于任意网页Pi，它的PageRank值可表示为如下：其中Bi为所有链接到网页i的网页集合，Lj为网页j的对外链接数（出度）。 iBjjjiLPRPR 简化模型面临的缺陷 实际的网络超链接环境没有这么理想化，PageRank会面临两个问题： Rank leak Rank sinkRank LeakPR(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.125n次迭代

11、0000Rank leakRank leak：一个独立的网页如果没有外出的链接就产生等级泄漏：一个独立的网页如果没有外出的链接就产生等级泄漏解决办法：解决办法：1.1.将无出度的节点递归地从图中去掉，待其他节点计算完毕后再加上将无出度的节点递归地从图中去掉，待其他节点计算完毕后再加上2.2.对无出度的节点添加一条边，指向那些指向它的顶点对无出度的节点添加一条边，指向那些指向它的顶点Rank SinkPR(A)PR(B)PR(C)PR(D)初始0.250.250.250.25一次迭代00.3750.250.375二次迭代00.3750.3750.25三次迭代00.250.3750.375四次迭代

12、00.3750.250.375五次迭代0Rank sinkRank sink：整个网页图中的一组紧密链接成环的网页如果没有外：整个网页图中的一组紧密链接成环的网页如果没有外出的链接就产生出的链接就产生Rank sinkRank sink目录 背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算PageRank的随机浏览模型 假定一个上网者从一个随机的网页开始浏览，上网者不断点击当前网页的链接开始下一次浏览。但是，上网者最终厌倦了，开始了一个随机的网页。随机上网者用以上方式访问一个新网页的概率就等于这个网页PageRank值。 这种随机模型更加

13、接近于用户的浏览行为； 一定程度上解决了rank leak和rank sink的问题； 保证pagerank具有唯一值。随机浏览模型的图表示随机浏览模型的图表示设定任意两个顶点之间都有直接通路，在每个顶点处以概率d按原来蓝色方向转移，以概率1-d按红色方向转移。随机浏览模型的邻接表表示随机浏览模型的邻接表表示 由于网页数目巨大，网页之间的连接关系的邻接矩阵是一个很大的稀疏矩阵,采用邻接表来表示网页之间的连接关系.随机浏览模型的PageRank公式： N: 网络中网页总数 d: 阻尼因子，通常设为0.85,d即按照超链接进行浏览的概率； 1-d：随机跳转一个新网页的概率 PR(pj):网页pj的

14、PR值 L(pj)：网页pj的链出网页数 一个页面的PageRank是由其他页面的PageRank计算到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），由于等式PR=A*PR满足马尔可夫链的性质，如果马尔可夫链收敛，则PR存在唯一解.通过迭代计算得到所有节点的PageRank值。那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。马尔可夫链收敛定理改进 Larry Page和Sergey Brin 两人从理论上证明了不论初始值如何选取，这种算法都保证了网页排名的估计值能收敛到他们的真实值。 由于互联网上网页的数量是巨大的，上面提

15、到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页，那么这个矩阵 就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。Larry Page和Sergey Brin两人利用稀疏矩阵计算的技巧，大大的简化了计算量。目录 背景介绍Google的网页排序PageRank简化模型PageRank随机浏览模型PageRank的计算PageRank的计算互联网是一个有向图每一个网页是图的一个顶点网页间的每一个超链接是图的一个有向边用邻接矩阵来表示图，即：定义邻接矩阵为G，若网页j到网页i有超链接，则 ；反之 。显然，如果网页有N 个，则矩阵为NN 的0、1方阵。1ijg0ijg多个

16、网页相多个网页相互链接的图互链接的图对应的邻接对应的邻接矩阵（这里矩阵（这里将将0,10,1值用值用二值图像显二值图像显示，黑色代示，黑色代表表0 0，白色，白色代表代表1 1）PageRank的计算定义邻接矩阵为G，若网页j到网页i有超链接，则 ；反之， 。记矩阵G的列和、行和分别是它们分别给出了页面j的链出链接数目和链入链接数目iijjgcjijigr1ijg0ijgPageRank的计算假设我们在上网的时侯浏览页面并选择下一个页面，这个过程与过去浏览过哪些页面无关，而仅依赖于当前所在的页面，那么这一选择过程可以认为是一个有限状态、离散时间的随机过程，其状态转移规律用Markov链描述。定

17、义转移概率矩阵)(ijaA jijijcga nji.1,PageRank的计算根据Markov链的基本性质，对于正则Markov链，存在平稳分布 ，满足 表示在极限状态（转移次数趋于无限）下各网页被访问的概率分布。 定义为网页的PageRank向量， 表示第i个网页的PageRank值TNxxx),(21Aiix1ix求矩阵求矩阵A A的特的特征值征值1 1对应的对应的特征向量特征向量某7个网页之间的链接关系图 网页链接图的邻接矩阵 0 1 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1

18、0 0 1 0 0 0 0 0 0G = PageRank的计算 0 11/20 1/4 1/2 01/50 1/2 1/3 0 0 01/50 0 1/3 1/4 0 01/50 0 0 1/4 0 01/50 0 1/3 01/21 0 0 0 0 1/4 0 01/50 0 0 0 0 0A =状态转移概率矩阵APageRank的计算0.6994565338373890.3828604185215180.3239588156720540.2429691117540400.4123112199462510.1030778049865630.1398913067674780.30351437

19、69968050.1661341853035140.1405750798722040.1054313099041530.1789137380191690.04472843450479230.0607028753993610求矩阵求矩阵A A特征特征值值1 1对应的特对应的特征向量征向量归一化归一化 7个网页的PageRank值PageRank结果的评价 将 PageRank 的评价按顺序排列(PageRank小数点3位四舍五入):页面之间相互关系及状态转移图PageRank结果的评价 让我们详细地看一下。ID=1 的页面的PageRank 是0.304，占据全体的三分之一，成为了第1位。 特别

20、需要说明的是，起到相当大效果的是从排在第3位的 ID=2 页面中得到了所有的PageRank (0.166) 数。ID=2页面有从3个地方过来的链入链接链入链接，而只有面向 ID=1页面的一个链接，因此(面向ID=1页面的)链接就得到ID=2的所有的PageRank数。 不过，就因为ID=1页面是链出链接链出链接和链入链接链入链接最多的页面，也可以理解它是最受欢迎的页面。PageRank结果的评价 反过来，最后一名的 ID=6 页面只有 ID=1 的15的微弱评价。 总之，即使有同样的链入链接链入链接的数目，链接源页面评价的高低也影响 PageRank 的高低。PageRank数值计算难点（一

21、） 计算机容量限制 假设 N 是 104 的 order。通常，数值计算程序内部行列和矢量是用双精度记录的，N 次正方行列 A 的记忆领域为 sizeof(double)* N * N =8 *104 * 104800MB。N 如果变成 105 或106 的话，就变成80GB, 8TB。这样的话不用说内存就连硬盘也已经很困难了。目前，Google处理着80亿以上的页面，很显然，已知的这种做法已经完全不适用了。PageRank数值计算难点（二） 收敛问题 特征向量的求解，就是求解方程 ，是 N 元一次方程组，一般地不能得到分析解，所以只能解其数值。 然而，常用的迭代求解方法会导致收敛速度很慢。A=