PageRank算法介绍李鹏飞 2013.4.28Google服务器Google工作电脑Google爬虫网页Google存储系统搜索引擎示意目录nGoogle的网页排序nPageRank算法求解nPageRank算法的应用n小结Google的网页排序n在Google中搜索“体育新闻”Google的网页排序n在Google中搜索“体育新闻”搜索引擎工作的简要过程如下n针对查询词“体育新闻”进行分词“体育”、“新 闻”n根据建立的倒排索引，将同时包含“体育”和“新闻”的 文档返回，并根据相关性进行排序这里的相关性主要是基于内容的相关性但是会有一些垃圾网页，虽然也包含大量的查询词，但却 并非满足用户需要的文档，如下图，一个网页中虽然出现 了四次“体育新闻”但却不是用户所需要的因此，页面本身的重要性在网页排序中也起着很重要的作 用查询词和文档的相关性Google的网页排序n在Google中搜索“体育新闻”Google的网页排序n如何度量网页本身的重要性呢？互联网上的每一篇html文档除了包含文本、图 片、视频等信息外，还包含了大量的链接关系 ，利用这些链接关系，能够发现某些重要的网 页n直观地看，某网页A链向网页B，则可以认为网页A 觉得网页B有链接价值，是比较重要的网页。n某网页被指向的次数越多，则它的重要性越高；越 是重要的网页，所链接的网页的重要性也越高。AB网页是节点，网页 间的链接关系是边Google的网页排序n如何度量网页本身的重要性呢？比如，新华网体育在其首页中对新浪体育做了 链接，人民网体育同样在其首页中对新浪体育 做了链接可见，新浪体育被链接的次数较多；同时，人 民网体育和新华网体育也都是比较“重要”的网 页，因此新浪体育也应该是比较“重要”的网页 。新华网体育人民网体育Google的网页排序n一个更加形象的图链向网页E的链接远远大 于链向网页C的链接，但 是网页C的重要性却大于 网页E。这是因为因为网 页C被网页B所链接，而 网页B有很高的重要性。Pagerank算法简介创始人：拉里佩奇(Larry Page )Google创始人之一 应用： 是Google用来衡量一个网站的好坏的唯一标准。 Google的网页排序nPageRank的提出Google的创始人之一Larry Page于1998年提出 了PageRank，并应用在Google搜索引擎的检 索结果排序上，该技术也是Google早期的核心 技术之一Larry Page是Google的创始首席执行官，2001 年4月转任现职产品总裁。他目前仍与Eric Schmidt和Sergey Brin一起共同负责 Google的 日常运作。他在斯坦福大学攻读计算机科学博 士学位期间，遇到了Sergey Brin，他们于1998 年合伙创立Google。Pagerank算法原理：Google的网页排序n网页的PageRank值PR值：取值0-10 Google工具栏 9 8 nhttp:/toolbar.google.comPagerank算法相关概念PR值：用来评价网页的重要性，PR值越大越重要，其级别从0到10级。 一般PR值达到4，就算是一个不错的网站了。Google把自己的网站 的PR值定到10，这说明Google这个网站是非常受欢迎的，也可以说 这个网站非常重要。 阻尼因数：(damping factor)其值为0.85n 阻尼系数d定义为用户不断随机点击链接的概率，所以，它取决于 点击的次数，被设定为0-1之间。d的值越高，继续点击链接的概率就 越大。因此，用户停止点击并随机冲浪至另一页面的概率在式子中用 常数(1-d)表示。无论入站链接如何，随机冲浪至一个页面的概率总是 (1-d)。(1-d)本身也就是页面本身所具有的PageRank值。Pagerank核心思想PageRank通过网络浩瀚的超链接关系来确定一个页面的 等级。Google把从A页面到B页面的链接解释为A页面给 B页面投票，Google根据投票来源（甚至来源的来源，即 链接到A页面的页面）和投票目标的等级来决定新的等级 。这样，PageRank会根据网页B所收到的投票数量来评 估该网页的重要性。此外，PageRank还会评估每个投票 网页的重要性，因为某些重要网页的投票被认为具有较高 的价值，这样，它所链接的网页就能获得较高的价值。这 就是PageRank的核心思想，当然PageRank算法的实际 实现上要复杂很多。PageRank简单计算： n假设一个由只有4个页面组成的集合：A，B，C和D。如果所有页面 都链向A，那么A的PR（PageRank）值将是B，C及D的和。n继续假设B也有链接到C，并且D也有链接到包括A的3个页面。一个 页面不能投票2次。所以B给每个页面半票。以同样的逻辑，D投出的 票只有三分之一算到了A的PageRank上。n换句话说，根据链出总数平分一个页面的PR值。如图1 所示的例子来说明PageRank 的具体计算过程。 PR值计算公式：PR(A)=(1-d)/N+d(PR(t1)/C(t1)+.+PR(tn)/C(tn)N: 网络中网页总数 d: 阻尼因数 PR(x):网页x的PR值 C(tn)：网页tn的链出网页数一个页面的PageRank是由其他页面的PageRank计算得到。Google 不断的重复计算每个页面的PageRank。如果给每个页面一个随机 PageRank值（非0），那么经过不断的重复计算，这些页面的PR值 会趋向于正常和稳定。这就是搜索引擎使用它的原因。PR值的取决因素：n链入网页数n链入网页的质量n链入网页的链出网页数nPageRank值是一个特殊矩阵中的特征向量 。这个特征向量为：PR值的计算（1）PR(A)=(1-d)/n+d(PR(t1)/C(t1)+.+PR(tn)/C(tn)PR值的计算（2）(1- d)/n+d(PR(t1)/C(t1)+.+PR(tn)/C(tn)2.2 使用幂法求PageRank 幂法计算过程如下： X 设任意一个初始向量, 即设置初始每个网页的 PageRank值均。一般为1. R = AX; while (1 )( if ( l X - R I e ) /如果最后两次的结果近似或者相同，返回R return R; else X =R; R = AX; n一、 P概率转移矩阵的计算过程:n先建立一个网页间的链接关系的模型,即我们需要合适的数据结构表示页面间 的连接关系。n1) 首先我们使用图的形式来表述网页之间关系：n现在假设只有四张网页集合：A、B、C，其抽象结构如下图1：2.3 求解步骤： n2）我们用矩阵表示连通图：n用邻接矩阵 P表示这个图中顶点关系 ，如果顶（页面）i向顶点（页面）j有链接情况 ，则pij = 1 ，否则pij = 0 。如图2所示。如果网页文件总数为N ， 那么这个网页链接 矩阵就是一个N x N 的矩 阵 。 n3）网页链接概率矩阵n然后将每一行除以该行非零数字之和，即（每行非0数之和就是链接网个数）则得到新 矩阵P，如图3所示。 这个矩阵记录了 每个网页跳转到其他网页的概率，即其中i行j列 的值表示用户从页面i 转到页面j的概率。图1 中A页面链向B、C，所以一个用户从A跳 转到B、C的概率各为1/2。n4）概率转移矩阵Pn采用P 的转置矩 阵进行计算， 也就是上面提到的概率转移矩阵P 。 如图4所示：2.3 求解步骤： 2.4 A矩阵计算过程。 2.5 循环迭代计算PageRank的过程 2.6 改 进 Larry Page和Sergey Brin 两人从理论上证明了不论初始值如何选取，这种算法都保 证了网页排名的估计值能收敛到他们的真实值。 由于互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方 之多个元素。如果我们假定有十亿个网页，那么这个矩阵 就有一百亿亿个元素。这样 大的矩阵相乘，计算量是非常大的。Larry Page和Sergey Brin两人利用稀疏矩阵计 算的技巧，大大的简化了计算量。PageRank的计算举例链接源I D 链接目标 ID 1 2,3 ,4,5, 7 2 1 3 1,2 4 2,3,5 5 1,3,4,6 6 1,5 7 53 PageRank算法的应用n学术论文的重要性排序n学术论文的作者的重要性排序某作者引用了其它作者的文献，则该作者认为其它作 者是“重要”的。n网络爬虫(Web Crawler)可以利用PR值，决定某个URL，所需要抓取的网页数 量和深度重要性高的网页抓取的页面数量相对多一些，反之， 则少一些n关键词与句子的抽取（节点与边）小结n优点： 是一个与查询无关的静态算法，所有网页的PageRank值通过离线 计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间 。nPageRank的缺点过分相信链接关系n一些权威网页往往是相互不链接的，比如新浪、搜狐、网易以及腾讯这些大 的门户之间，基本是不相互链接的，学术领域也是这样。n1）人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相 关性和主题性降低 n 2）旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上 游链接，除非它是某个站点的子站点。n排序技术是搜索引擎的绝密 Google目前所使用的排序技术，已经不再是简单的PageRank谢谢大家!