PageRank算法介绍.

PageRank算法介绍背景介绍Google的创始人拉里·佩奇和谢尔盖·布林于1998年在斯坦福大学提出了PageRank算法该算法以拉里·佩奇（LarryPage）之姓来命名Google专有的算法，用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度PageRank让链接来“投票”，到一个页面的超链接相当于对该页投一票Google搜索核心算法网页级别（PageRank）按网页链接广泛程度判断网页重要性，是Google中表示网页重要性的综合性指标。页面分析（PageAnalysis）按页面标题是否出现关键词、网页内关键词出现的频率及关键词出现的位置确定哪些网页与正在执行的搜索密切相关。PageRank对搜索结果的影响结合了所有网页重要性和相关性指标，Google将最相关和最可靠的结果放在搜索结果的顶端。一般而言，PageRank对于排名的影响比页面分析还高。Google服务器Google工作电脑Google爬虫网页Google存储系统搜索引擎示意Google的网页排序在Google中搜索“体育新闻”Google的网页排序在Google中搜索“体育新闻”搜索引擎工作的简要过程如下针对查询词“体育新闻”进行分词——》“体育”、“新闻”根据建立的倒排索引，将同时包含“体育”和“新闻”的文档返回，并根据相关性进行排序这里的相关性主要是基于内容的相关性但是会有一些垃圾网页，虽然也包含大量的查询词，但却并非满足用户需要的文档，如下图，一个网页中虽然出现了四次“体育新闻”但却不是用户所需要的因此，页面本身的重要性在网页排序中也起着很重要的作用查询词和文档的相关性Google的网页排序在Google中搜索“体育新闻”Google的网页排序如何度量网页本身的重要性呢？互联网上的每一篇html文档除了包含文本、图片、视频等信息外，还包含了大量的链接关系，利用这些链接关系，能够发现某些重要的网页直观地看，某网页A链向网页B，则可以认为网页A觉得网页B有链接价值，是比较重要的网页。某网页被指向的次数越多，则它的重要性越高；越是重要的网页，所链接的网页的重要性也越高。AB网页是节点，网页间的链接关系是边Google的网页排序如何度量网页本身的重要性呢？比如，新华网体育在其首页中对新浪体育做了链接，人民网体育同样在其首页中对新浪体育做了链接可见，新浪体育被链接的次数较多；同时，人民网体育和新华网体育也都是比较“重要”的网页，因此新浪体育也应该是比较“重要”的网页。新华网体育人民网体育Google的网页排序一个更加形象的图链向网页E的链接远远多于链向网页C的链接，但是网页C的重要性却大于网页E。这是因为因为网页C被网页B所链接，而网页B有很高的重要性。什么是PageRankPageRank是一种在搜索引擎中根据网页之间相互的链接关系计算网页排名的技术。PageRank是Google用来标识网页的等级或重要性的一种方法。其级别从0到10级，PR值越高说明该网页越受欢迎（越重要）。PageRank近似于一个用户，是指在Internet上随机地单击链接将会到达特定网页的可能性。通常，能够从更多地方到达的网页更为重要，因此具有更高的PageRank。如果要查看此站点PageRank值，请安装Google工具条并启用PageRank特性，或者在firefox安装SearchStatus插件。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的对外链接数（出度）。简化模型面临的缺陷所有PageRank的计算是同时的。即在计算之前，类似上面的一个有向图已经确定了。然后所有网站的PageRank同时用上面这个公式计算。迭代过程如下：初始：所有网站的PageRank均等第一次迭代：每个网站得到了一个新的PageRank第二次迭代：用这组新的PageRank再按上述公式迭代形成另一组新的PageRankPageRank的计算互联网是一个有向图每一个网页是图的一个顶点网页间的每一个超链接是图的一个有向边用邻接矩阵来表示图，即：定义邻接矩阵为G，若网页j到网页i有超链接，则；反之。显然，如果网页有N个，则矩阵为N×N的0、1方阵。1ijg0ijgPageRank的计算定义邻接矩阵为G，若网页j到网页i有超链接，则；反之，。记矩阵G的列和、行和分别是它们分别给出了页面j的链出链接数目和链入链接数目1ijg0ijgiijjgcjijigrPageRank的计算假设我们在上网的时侯浏览页面并选择下一个页面，这个过程与过去浏览过哪些页面无关，而仅依赖于当前所在的页面，那么这一选择过程可以认为是一个有限状态、离散时间的随机过程，其状态转移规律用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.1054313099041530.1789137380191690.04472843450479230.0607028753993610求矩阵A特征值1对应的特征向量归一化7个网页的PageRank值PageRank结果的评价将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很高的ID=1的链接而使其有很大地影响。总之，即使有同样的链入链接的数目，链接源页面评价的高低也影响PageRank的高低。PageRank数值计算难点（一）计算机容量限制假设N是104的order。通常，数值计算程序内部行列和矢量是用双精度记录的，N次正方行列A的记忆领域为sizeof(double)*N*N=8*104*104＝800MB。N如果变成105或106的话，就变成80GB,8TB。这样的话不用说内存就连硬盘也已经很困难了。目前，Google处理着80亿以上的页面，很显然，已知的这种做法已经完全不适用了。PageRank数值计算难点（二）收敛问题特征向量的求解，就是求解方程，是N元一次方程组，一般地不能得到分析解，所以只能解其数值。然而，常用的迭代求解方法会导致收敛速度很慢。Aα=αPageRank算法的应用学术论文的重要性排序学术论文的作者的重要性排序某作者引用了其它作者的文献，则该作者认为其它作者是“重要”的。网络爬虫(WebCrawler)可以利用PR值，决定某个URL，所需要抓取的网页数量和深度重要性高的网页抓取的页面数量相对多一些，反之，则少一些关键词与句子的抽取（节点与边）Thankyou！