pagerank算法讲解.ppt

目录
背景介绍
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, /~backrub/
为了更高效地计算 PageRank,以下是改良以后的一篇论文。Taher H. Haveliwala, ‘putation of PageRank’, Stanford Technical Report, 1999, :8090/pub/1999-31
PageRank(TM) 是美注册商标。
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的网页排序
在Google中搜索“体育新闻”
Google的网页排序
在Google中搜索“体育新闻”
搜索引擎工作的简要过程如下
针对查询词“体育新闻”进行分词——》“体育”、“新闻”
根据建立的倒排索引,将同时包含“体育”和“新闻”的文档返回,并根据相关性进行排序
这里的相关性主要是基于内容的相关性
但是会有一些垃圾网页,虽然也包含大量的查询词,但却并非满足用户需要的文档,如下图,一个网页中虽然出现了四次“体育新闻”但却不是用户所需要的
因此,页面本身的重要性在网页排序中也起着很重要的作用
查询词和文档的相关性
Google的网页排序
如何度量网页本身的重要性呢?
互联网上的每一篇html文档除了包含文本、图片、视频等信息外,还包含了大量的链接关系,利用这些链接关系,能够发现某些重要的网页
直观地看,某网页A链向网页B,则可以认为网页A觉得网页B有链接价值,是比较重要的网页。
某网页被指向的次数越多,则它的重要性越高;越是重要的网页,所链接的网页的重要性也越高。
A
B
网页是节点,网页
间的链接关系是边