51阅读吧 - 为您打造专业优质的文章分享平台!
您的当前位置: 51阅读吧 >

pagerank算法公式|pagerank算法讲解

NO.1 pagerank算法讲解

PageRank算法介绍
程 苹 cp2phi@gmail.com

目录
背景介绍 ? Google的网页排序 ? PageRank简化模型 ? PageRank随机浏览模型 ? PageRank的计算
?

背景介绍
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/~backrub/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?

Pagerank
创始人:拉里佩奇(Larry Page )
—Google创始人之一

应 用:是Google用来衡量一个网站 的好坏的唯一标准。

?PageRank的提出
?Google的创始人之一Larry Page于1998年提出了 PageRank,并应用在Google搜索引擎的检索结果排序 上,该技术也是Google早期的核心技术之一 ?Larry Page是Google的创始首席执行官,2001年4月转 任现职产品总裁。他目前仍与Eric Schmidt和Sergey Brin一起共同负责 Google的日常运作。他在斯坦福大 学攻读计算机科学博士学位期间,遇到了Sergey Brin, 他们于1998年合伙创立Google。

目录
?背景介绍 ?Google的网页排序 ?PageRank简化模型 ?PageRank随机浏览模型 ?PageRank的计算

Google的网页排序
? 在Google中搜索“体育新闻”

Google的网页排序
?在Google中搜索“体育新闻”
?搜索引擎工作的简要过程如下

查询词和文档的相关性

?针对查询词“体育新闻”进行分词——》“体育”、“新 闻” ?根据建立的倒排索引,将同时包含“体育”和“新闻”的文 档返回,并根据相关性进行排序
?这里的相关性主要是基于内容的相关性 ?但是会有一些垃圾网页,虽然也包含大量的查询词,但却 并非满足用户需要的文档,如下图,一个网页中虽然出现 了四次“体育新闻”但却不是用户所需要的 ?因此,页面本身的重要性在网页排序中也起着很重要的作 用

Google的网页排序
?在Google中搜索“体育新闻”

Google的网页排序
? 如何度量网页本身的重要性呢? 互联网上的每一篇html文档除了包含文本、图片、视频等 信息外,还包含了大量的链接关系,利用这些链接关系, 能够发现某些重要

的网页
网页是节点,网页 间的链接关系是边
A B

? 直观地看,某网页A链向网页B,则可以认为网页A觉得网 页B有链接价值,是比较重要的网页。 某网页被指向的次数越多,则它的重要性越高;越是重要 的网页,所链接的网页的重要性也越高。

Google的网页排序
? 如何度量网页本身的重要性呢?

?比如,新华网体育在其首页中对新浪体育做了链接, 人民网体育同样在其首页中对新浪体育做了链接
新华网体育
人民网体育

?可见,新浪体育被链接的次数较多;同时,人民网体 育和新华网体育也都是比较“重要”的网页,因此新 浪体育也应该是比较“重要”的网页。

Google的网页排序
?一个更加形象的图
链向网页E的链接远 远多于链向网页C的 链接,但是网页C的 重要性却大于网页E。 这是因为因为网页C 被网页B所链接,而 网页B有很高的重要 性。

Http网页链接示意图

目录
?背景介绍 ?Google的网页排序 ?PageRank简化模型 ?PageRank随机浏览模型 ?PageRank的计算

什么是PageRank
PageRank是一种在搜索引擎中根据网页之间相互的链 接关系计算网页排名的技术。 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的简单计算过程

PRi ?

?
j?Bi

PRj Lj

PageRank的简化模型
可以把互联网上的各网页之间的链接关系看成一个有向 图。假设冲浪者浏览的下一个网页链接来自于当前网页。 建立简化模型:对于任意网页Pi,它的PageRank值可表 示为如下:其中Bi为所有链接到网页i的网页集合,Lj为 网页j的对外链接数(出度)。

简化模型面临的缺陷
实际的网络超链接环境没有这么理想 化,PageRank会面临两个问题:
? Rank leak ? Rank sink

Rank Leak
PR(A) 初始 一次迭代 二次迭代 三次迭代 0.25 0.125 0.125 0.125 PR(B) 0.25 0.125 0.125 0.125 PR(C) 0.25 0.25 0.125 0.125 PR(D) 0.25 0.25 0.25 0.125


n次迭代


0


0


0


0

Rank leak:一个独立的网页如果没有外出的链接就产生等级泄漏 解决办法: 1.将无出度的节点递归地从图中去掉,待其他节点计算完毕后再加上 2.对无出度的节点添加一条边,指向那些指向它的顶点

Rank Sink
PR(A) 初始 一次迭代 三次迭代 四次迭代 五次迭代 0.25 0 0 0 0 PR(B) 0.25 0.375 PR(C) 0.25 0.25 PR(D) 0.25 0.375

二次迭代 0

0.375
0.25 0.375 …

0.375
0.375 0.25 …

0.25
0.375 0.375 …

Rank sink:整个网页图中的一组紧密链接成环的网页如果没有外 出的链接就产生Rank sink

目录
?背景介绍 ?Google的网页排序 ?PageRank简化模型 ?PageRank随机浏览模型 ?PageRank的计算

PageRank的随机浏览模型
假定一个上网者从一个随机的网页开始浏览,上网 者不断点击当前网页的链接开始下一次浏览。但是,上 网者最终厌倦了,开始了一个随机的网页。随机上网者 用以上方式访问一个新网页的概率就等于这个网页 PageRank值。 ① 这种随机模型更加接近于用户的浏览行为; ② 一定程度上解决了rank leak和rank sink的问题; ③ 保证pagerank具有唯一值。

随机浏览模型的图表示

设定任意两个顶点之间都有直接通路, 在每个顶点处以概率d按原来蓝色方向转移,以概率1d按红色方向转移。

随机浏览模型的邻接表表示
由于网页数目巨大,网页之间的连接关系的邻接矩阵是一个很 大的稀疏矩阵,采用邻接表来表示网页之间的连接关系.随机浏览模 型的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值会趋向于正常和稳定。

马尔可

夫链收敛定理

改进
Larry Page和Sergey Brin 两人从理论上证明了 不论初始值如何选取,这种算法都保证了网页排名的 估计值能收敛到他们的真实值。 由于互联网上网页的数量是巨大的,上面提到的 二维矩阵从理论上讲有网页数目平方之多个元素。如 果我们假定有十亿个网页,那么这个矩阵 就有一百 亿亿个元素。这样大的矩阵相乘,计算量是非常大的 。Larry Page和Sergey Brin两人利用稀疏矩阵计算 的技巧,大大的简化了计算量。

目录
?背景介绍 ?Google的网页排序 ?PageRank简化模型 ?PageRank随机浏览模型 ?PageRank的计算

PageRank的计算
? ? ? ? 互联网是一个有向图 每一个网页是图的一个顶点 网页间的每一个超链接是图的一个有向边 用邻接矩阵来表示图,即:定义邻接矩阵为G,若 网页j到网页i有超链接,则 gij ? 1 ;反之 gij ? 0 。 ? 显然,如果网页有N 个,则矩阵为N×N 的0、1方 阵。

多个网页相 互链接的图 对应的邻接 矩阵(这里 将0,1值用 二值图像显 示,黑色代 表0,白色 代表1)

PageRank的计算
? 定义邻接矩阵为G,若网页j到网页i有超链接, 则 gij ? 1 ;反之, gij ? 0 。 ? 记矩阵G的列和、行和分别是
c j ? ? gij

ri ? ? gij
j

i

? 它们分别给出了页面j的链出链接数目和链入链 接数目

PageRank的计算
? 假设我们在上网的时侯浏览页面并选择下一 个页面,这个过程与过去浏览过哪些页面无 关,而仅依赖于当前所在的页面,那么这一 选择过程可以认为是一个有限状态、离散时 间的随机过程,其状态转移规律用Markov链 描述。 ? 定义转移概率矩阵 A ? (aij )

aij ?

gij cj

i, j ? 1...n

PageRank的计算
? 根据Markov链的基本性质,对于正则Markov链, 存在平稳分布 , ? ? ( x1, x2 ,?xN )T 满足 求矩阵A的特 征值1对应的 A? ? ? ? xi ? 1 特征向量 ? i ? ? 表示在极限状态(转移次数趋于无限)下各 网页被访问的概率分布。 ? ? 定义为网页的PageRank向量,xi 表示第i个网 页的PageRank值

某7个网页之间的链接关系图

网页链接图的邻接矩阵
0 1 1 G = 1 1 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0

PageRank的计算
状态转移概率矩阵A
0 1 1/2 0 1/4 1/2 0 1/5 0 1/2 1/3 0 0 0 1/5 0 0 1/3 1/4 0 0 1/5 0 0 0 1/4 0 0 1/5 0 0 1/3 0 1/2 1 0 0 0 0 1/4 0 0 1/5 0 0 0 0 0 0

A =

?

PageRank的计算
求矩阵A特征 0.699456533837389 值1对应的特 0.382860418521518 征向量 ?
0.323958815672054 0.242969111754040 ?? 0.412311219946251 0.103077804986563 0.139891306767478
归一化

0.303514376996805 0.166134185303514 0.140575079872204 0.105431309904153 0.178913738019169 0.0447284345047923 0.0607028753993610

7个网页的PageRank值

Page

Rank结果的评价
将 PageRank 的评价按顺序排列(PageRank 小数点3位四舍五入):

页面之间相互关系及状态转移图

PageRank结果的评价

让我们详细地看一下。ID=1 的页面的PageRank 是 0.304,占据全体的三分之一,成为了第1位。 特别需要说明的是,起到相当大效果的是从排在第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数值计算难点(一)
? 计算机容量限制 ? 假设 N 是 104 的 order。通常,数值计算 程序内部行列和矢量是用双精度记录的,N 次正方行列 A 的记忆领域为 sizeof(double)* N * N =8 *104 * 104= 800MB。N 如果变成 105 或106 的话,就变成 80GB, 8TB。这样的话不用说内存就连硬盘也 已经很困难了。目前,Google处理着80亿以 上的页面,很显然,已知的这种做法已经完 全不适用了。

PageRank数值计算难点(二)
? 收敛问题 ? 特征向量的求解,就是求解方程 Aα= α , 是 N 元一次方程组,一般地不能得到分析解, 所以只能解其数值。 ? 然而,常用的迭代求解方法会导致收敛速度很慢。

PageRank算法的应用
? 学术论文的重要性排序 ? 学术论文的作者的重要性排序
?某作者引用了其它作者的文献,则该作者认为其它作 者是“重要”的。

? 网络爬虫(Web Crawler)
?可以利用PR值,决定某个URL,所需要抓取的网页数量 和深度 ?重要性高的网页抓取的页面数量相对多一些,反之, 则少一些

? 关键词与句子的抽取(节点与边)

pagerank小结
? 优点: 是一个与查询无关的静态算法,所有网页的PageRank值通过离线计算获 得;有效减少在线查询时的计算量,极大降低了查询响应时间。 ? PageRank的缺点 ? 过分相信链接关系 ? 一些权威网页往往是相互不链接的,比如新浪、搜狐、网易以及腾讯 这些大的门户之间,基本是不相互链接的,学术领域也是这样。 ? 1)人们的查询具有主题特征,PageRank忽略了主题相关性,导致结 果的相关性和主题性降低 ? 2)旧的页面等级会比新页面高。因为即使是非常好的新页面也不会 有很多上游链接,除非它是某个站点的子站点。 ? 排序技术是搜索引擎的绝密 ? Google目前所使用的排序技术,已经不再是简单的PageRank

再见~(≧▽≦)

/~ 啦啦啦

谢谢大家!


NO.2 SEO Google算法解析系列之主题敏感的PageRank算法

  为了提高查询结果的主题相关性,2002年斯坦福大学的Taher Haveliwala提出了主题敏感的Pagerank算法TSPR,现在是Google排名的核心算法之一。

  无论Pagerank、HITs甚至HillTop算 法都存在“主题漂移"问题,特别对于疯狂而又随意交互外链的站点,导致搜索引擎返回主题无关结果,搜索引擎用户体验很差。而TSPR借鉴了早期开发目录 (ODP,如Yahoo,Dmoz等)的思想并结合PageRank算法:针对一个查询来确定一个URL对该查询的主题敏感性得分,作为排名的一个重要依 据,大大提高了返回结果的主题相关性。

  TSPR算法主要分为两个过程:

  第一过程针对URL离线生成Rank向量,这个过程是基于开放目录的,以Dmoz为例,“中国汽车消费网”的首页 URL在"Open Directory - World: Chinese Simplified: 休闲: 汽车"这个主题(这里假设为Cj)里,假设该页面上的非隶属URL数为L个,那么"中国汽车消费网"的URL对主题Cj的得分(Ranki)为1/L,由于“中国汽车消费网”的URL可能出现在多个主题目录中(对于主题目录页面中没有该URL,自然得分就为0),那么选取TOP N个主题得分,组成这个URL的Rank向量。

  第二个过程就是在线生成针对查询关键词的URL的主题敏感性得分,(1).首先计算一个查询是某一主题的可能性与敏感性得分,和HillTop算法一样, 将一个查询分为k个术语(term),根据朴素贝叶斯分类器(机器学习与数据挖掘常用的一种数学方法,这里不详述),计算该查询是某一主题的概率,以“汽 车消费”为例,分为"汽车"和"消费"两个术语属于Cj主题的概率为0.8和0.1,那么该查询为Cj主题的可能性为P(Cj)*0.08 (其中P(Cj)也是一个概率,也可以作为个性化参数,如表示用户对主题Cj的偏好程度);(2).然后计算针对该查询和主题Cj时"中国汽车消费网"的URL的敏感性得分,该得分为TSPRj=Ranki*P(Cj)*0.08,那么的针对“汽车消费”这个查询,315che的URL针对“汽车消费”这个查询的敏感性得分等于上述所有主题中TOP N个TSPRj得分之和(其实也就是第一个过程Rank向量与该查询属于TOP N个Cj概率向量的点积)。

  TSPR算法的总体过程如上,简单的说,对于一个查询,计算一个URL对该查询的主题敏感性得分是依赖于开放目录的。足见Google对开放目录的重视。

  总结:1.一个网站的被开放目录收录是极其重要的,是其在一些主题性关键词查询获得较好Google排名的保证,而这类关键词一般都是热门关键词,是网站 的立身 之本。2.从第一个过程可以看出,一个主题的网站越多,每个网站的敏感性得分就会越小,从第二个过程可以看出一个网站被越多的主题收录,敏感性的就越高, 显然被越多的开放目录收录,主题敏感性就越高。所以选择合适主题,让尽量多的开放目录收录可以提高重要页面的主题敏感性得分。

  本文由http://www.315che.com/站长供稿!

NO.3 小彭:简单的PageRank算法理解

  PageRank算法诞生于1998年的斯坦福大学,Google的创始人拉里·佩奇和谢尔盖·布林发明了这项技术。

  PageRank算法简单来说就是通过网页间相互的链接关系以确定网页的重要性及等级。网页A链向网页B则为网页A对网页B的投票,google根据投票网页和被投票网页(即网页A和网页B)的等级来决定新的等级,一个网页的PageRank值由所有链接它的网页的重要性经过递归计算得出。

  简单的PageRank算法理解:

  假设有4个页面:A,B, C 和 D。如果所有页面都链向A,那么A的PR值将是B,C 及 D的和。

  A = B + C + D

  继续假设:B链接到A的同时链接到C,并且D链接到A的同时链接到A,B,C的3个页面。因为B页面的PR值是恒定的,所以B向A和C这两个页面传递的PR值相同,由两个页面均分。同样的,D页面的PR值只有三分之一算到了A的 PageRank 上。

  A = B/2 + C/1 + D/3

  可以这样理解,每个网页传递的PR值由导出的链接均分。假设页面的导出链接数为L,那么A页面的接收的PR值为:

  A = B / L(B) + C / L(C) + D / L(D)

  最后:上述这些被换算成百分比再乘上一个系数q,则得出该页面的PR值,但是按照此算法,没有页面的PR的将会是0,所以Google通过数学系统给了每个页面一个最小值1 - q。

  A = {B / L(B) + C / L(C) + D / L(D)+...} q + 1 - q

  每一个页面的PR值均是由其他页面的传递而计算得到,经过不断的计算PR值就会逐渐趋于平稳。

  简单的PageRank算法说明到这里,有兴趣的可以查找更多的搜索引擎算法研究资料。

  2005年Google推出nofollow属性,此属性可以使Google认为该链接不对目标网页进行投票,保证爬虫的正确识别和防止大量spam的产生。但据点石互动2009年6月4日消息《Google调整nofollow属性效果》称该属性效果已经降低。

  PageRank算法最直观的体现显示在Google工具条上的(0-10)的绿色指标(PR值)上。PR值从低到高0-10标示网页的等级,当显示为0或10时可以忽略(0有可能为全站的网站上线而PR值尚未更新、10则表示该网站已经相当权威)。

  小彭在《在百度优化中,高质量的外链项目属于重中之重》一文中提到:“高pr不一定代表高质量,可低的pr一般来说站点的质量都不怎么样”,此文说明在针对百度的网站优化过程中,PageRank算法体现出的PR值在SEO工作中仅能做为SEO工作者的一个判别指标,切不可盲目迷信PR值。

  原文:小彭@长沙SEO http://www.pyy1990.cn/ 转载请保留

上一篇:支行副行长竞聘演讲稿|银行副行长竞聘演讲 上一篇:二十四式太极拳教学视频|陈式太极拳教学视频
与该文相关的文章

温馨提示:如果您对51阅读吧有任何建议,请通过网站联系邮箱向我们反馈,感谢各位的建议与支持!