PageRank算法原理及过程

SEO 2020-02-04 20:57未知admin

1、 PageRank算法概述:

page rank,或PageRank,也称为PageRank、Google left rank或PageRank。

这是谷歌创始人拉里•佩奇(Larry·;page)和谢尔盖•布林(Sergey·;Brin)在1997年构建早期搜索系统原型时提出的链接分析算法。自从Google在商业领域取得空前成功以来,该算法也成为其他搜索引擎和学术界十分关注的计算模型。目前,许多重要的链路分析算法都是从PageRank算法中派生出来的。PageRank是Google用来识别网页级别/重要性的一种方法,也是Google用来衡量网站质量的唯一标准。在融合了标题和关键字等所有其他因素后,谷歌通过PageRank调整搜索结果,使那些“排名/重要性”较高的页面可以在其他搜索结果网站中排名更高,从而提高搜索结果的相关性和质量。它的级别是从0到10,10是满分。公关价值越高,页面就越受欢迎(也越重要)。例如:PR值为1的站点表示该站点不是很受欢迎,而PR值为7到10则表示该站点非常受欢迎(或非常重要)。一般的PR4,甚至是一个好的网站。谷歌把自己网站的公关价值定为10,这说明谷歌是一个非常受欢迎的网站,也可以说这个网站非常重要。
 

2、 从入站链接数到PageRank:

在PageRank被提出之前,一些研究者已经提出使用网页中的链接数来分析和计算链接。如果一个网页有更多的链接,那么这个网页就更重要。在早期,许多搜索引擎也采用了链接数作为链接分析方法,这对提高搜索引擎的效果也有着显著的作用。PageRank不仅考虑链接数量的影响,还涉及到网页的质量。这两种方法的结合,使网页的重要性得到了更好的评价标准。
 

对于Internet页面a,PageRank的计算基于以下两个基本条件:
 

(1)  Quantity if:在Web图模型中,如果一个页面节点从其他页面接收到更多的传入链接,那么这个页面就更重要。
 

(2)  质量如果:链接到页面a的质量不同,高质量的页面将通过链接向其他页面传递许多其他权重。所以高质量的页面指向a页越多,a页就越重要。

                                                

 

3、基本概念

 

(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值越高其排名越高。

 

 

4、算法原理
 

PageRank算法[^ref_3]总的来说就是预先给每个网页一个PR值(下面用PR值指代PageRank值),由于PR值物理意义上为一个网页被访问概率,所以一般是1N,其中N为网页总数。另外,一般情况下,所有网页的PR值的总和为1。如果不为1的话也不是不行,最后算出来的不同网页之间PR值的大小关系仍然是正确的,只是不能直接地反映概率了。

 

预先给定PR值后,通过下面的算法不断迭代,直至达到平稳分布为止。

 

互联网中的众多网页可以看作一个有向图。下图是一个简单的例子[^ref_4]:

 

sample1

 

这时A的PR值就可以表示为:

 

PR(A)=PR(B)+PR(C)

 

然而图中除了C之外,B和D都不止有一条出链,所以上面的计算式并不准确。想象一个用户现在在浏览B网页,那么下一步他打开A网页还是D网页在统计上应该是相同概率的。所以A的PR值应该表述为:

 

PR(A)=PR(B)2+PR(C)1

 

互联网中不乏一些没有出链的网页,如下图:

 

sample1

 

图中的C网页没有出链,对其他网页没有PR值的贡献,我们不喜欢这种自私的网页(其实是为了满足 Markov 链的收敛性),于是设定其对所有的网页(包括它自己)都有出链,则此图中A的PR值可表示为:

 

PR(A)=PR(B)2+PR(C)4

 

然而我们再考虑一种情况:互联网中一个网页只有对自己的出链,或者几个网页的出链形成一个循环圈。那么在不断地迭代过程中,这一个或几个网页的PR值将只增不减,显然不合理。如下图中的C网页就是刚刚说的只有对自己的出链的网页:

 

sample3

 

为了解决这个问题。我们想象一个随机浏览网页的人,当他到达C网页后,显然不会傻傻地一直被C网页的小把戏困住。我们假定他有一个确定的概率会输入网址直接跳转到一个随机的网页,并且跳转到每个网页的概率是一样的。于是则此图中A的PR值可表示为:

 

PR(A)=α(PR(B)2)+(1−α)4

 

在一般情况下,一个网页的PR值计算如下:

 

PR(pi)=α∑pj∈MpiPR(pj)L(pj)+(1−α)N

 

其中Mpi是所有对pi网页有出链的网页集合,L(pj)是网页pj的出链数目,N是网页总数,α一般取0.85。

根据上面的公式,我们可以计算每个网页的PR值,在不断迭代趋于平稳的时候,即为最终结果。