PageRank 算法

一、PageRank介绍

PageRank，网页排名，又称为网页级别，Google左侧排名货佩奇排名，是一种由搜索引擎根据网页之间相互的超链接计算的技术，而作为网页排名的要素之一，以Goole公司创办人Larry Page之姓来命名。



PageRank算法，对每个目标网页进行附上权值，权值大的就靠前显示，权值小的就靠后显示。PageRank算法就是给每个网页附加权值的。PageRank算法借鉴学术界论文重要性的评估方法：谁被引用的次数多，谁就越重要。



二、算法的核心思想

1. 如果一个网页被很多其他网页链接到的话,说明这个网页比较重要，也就是PageRank值会相对较高

2. 如果一个PageRank值很高的网页链接到一个其他的网页，那么被链接到的网页的PageRank值会相应地因此而提高



三、基本概念

1. 出链：如果在网页A中附加了网页B的超链接B-Link，用户浏览网页A时可以点击B-Link然后进入网页B。上面这种A附有B-Link这种情况表示A出链B。可知，网页A也可以出链C，如果A中也附件了网页C的超链接C-Link；

2. 链接：上面通过点击网页A中B-Link进入B，表示由A入链B。如果用户自己在浏览器输入栏输入网页B的URL，然后进入B，表示用户通过输入URL入链B；

3. 无出链：如果网页A中没有附加其他网页的超链接，则表示A无出链；

4. 只对自己出链：如果网页A中没有附件其他网页的超链接，而只有他自己的超链接A-Link，则表示A只对自己出链；

5. PR值：一个网页的PR值，概率上理解就是此网页被访问的概率，PR值越高其排名越高。



四、算法

1. 假设一个由4个页面组成的小团体：A，B，C，和 D，如果所有页面都链接向A，那么A的PR值就是BCD的Pagerank的总和。

1. 假设B也有链接到C，并且D也有链接到包括A的3个页面。一个页面不能投票2次，所以，B给每个页面半票。以同样的逻辑，D投出的票只有三分之一算到了A的PageRank上。

换句话说，根据链出总数平分一个页面的PR值。

1. 互联网中一个网页只有对自己的出链，或者几个网页的出链形成一个循环网。那么在不断迭代过程中，这一个或几个网页的PR值将只增不减，显然不合理。如下图C网页就是刚刚说的只有对自己的出链的网页：

为了解决这个问题，我们想象一个隋杰浏览网页的人，假定他有一个确定的概率会输入网址直接跳转到一个随机的网页，并且跳转到每个网页的概率是一样的。于是此图中A的PR值可表示为：

PageRank的计算公式：