深圳SEO公司
欢迎您光临浏览!

搜索引擎分析谷歌的PR值(PageRank)

虽然谷歌已经停止对PR的更新,但深圳SEO认为有必要给大家讲讲谷歌PR;网页搜索的本质是网页信息的聚合,把本来很难聚合在一起的网页通过共同包含的关健词聚合起来。网页被聚合后就自然会产生排序问题。归纳起来就是既不能不排,也不能乱排,需要通过科学有效的方法将“好”的搜索结果按照“好”的程度依次排列。当然“好”是一个相当主观的且难以量化的概念,因此如何评价这个“好”成为搜索质量的关健。在搜索引擎的发展史中,Google发明的PageRank无疑是浓墨重彩的一笔。
PageRank的来由Google公司的两位创始人L.Page及S.Brin在1998年提出了PageRank的概念(Page.et al.1998)。在他们提出这个概念时,一方面,万维网的发展正处于信息大爆炸的时期。当时估计大约有l亿5千万网页,而且不到一年的时间网页的数目就会翻倍;另一方面,网页质量参差不齐。例如文献(Page.et al.1998]中提到的网页信息“从Joe在哪里吃午饭到信息检索的期刊”无所不包,可以说实际有意义的、有价位的,以及经常被用户检索的网页规模并没有想像中的那么大,一个基本的方法是通过为网页排名使得重要性高且有价值的网页能够被优先检索。PageRank(网页排名)就是在这样的应用背景下诞生的。
PageRank的基本想法
人们在万维网上冲浪的过程中,常常从一个起始网页开始(例如新闻门户网站),之后被那些带有链接文字(锚文本)所描述的网页吸引,从而点击并打开另一个网页。并依次往复,直到对冲浪感觉厌倦,而正是由于网页和网页通过链接关系构成的这个网络使得网上冲浪成为可能。然而直到Google提出了PageRank模型,这种网负间彼此链接关系的价值才被挖掘出来.这种挖掘过程也称为即“链接分析”(link analyze),简单地说.如果网页A链接到B,那么表示网页A的编写者(网页工程师或者其他网页创造者)对网页B的一种认可。或者说网页A为网页B投了一票,网页B的重要性被网页A认可。
直觉上说,如下3点可以认为是网页重要性的一种评价。
1.认可度越高的网页越重要,即反向链接〔backlink )越多的网页越重要。
2.反向链接的源网页质量越高,被这些高质量网页的链接指向的网页越重要。
3.链接数越少的网页越重要。    举个例子,假定在一次比赛中一个网球选手A被另一个网球选手B击败。定义一个A指向B的链接表示这种胜负关系。即A-B表示A输给B,成者说A认可了B的厉害。那么很显然对照上面得出下面结论。
1.如果B的反向链接越多,即认可B厉害的人越多,因此B的排名越高。
2.如果输给B的选手的排名越高,即认可B厉害的人也是厉害的人,那么B的排名越高。
3.如果B输给的选手越少,即B认可厉害的人越少,那么B的排名越高.综上所述,赢的次数多、赢得对手质量高且输的少的选手的排名高是很自然的,PageRank的算法的基本思想也来自于此。
在描述下载系统时曾提到过“随机冲浪”模型(Bernardo A.Huberman, et al.1998),它是PageRank的理论基础,该模型描述网民访问网页的如下行为。
1.用户随机选择一个网页作为上网的起始网页。
2.完这个网页后从该网页内所含的超链接随机选择一个页面继续浏览。
3.沿着超链接重复浏览,直到对某个主题感到厌倦而重
新随机选择另一个网页浏览。如此反复,直到结束。
PageRank的计算公式
图4-17为文献[Page, el al.1998]的原图。图中我们看到一个直观并简单的计算方法。以最左上角的网页为例,这个网页被3个箭头指向,假定共计得到了100分。然后通过两个链接(小横线表示网页内部的链接,方块表示一个网页)平均将这100分均分给了它所指向的两个网页。平均的意义在于假定用户是随机冲浪的,也就是点击第1个链接和第2个链接的可能性相等。这种由于指向关系而得到一定的分数。最后通过计算每个网页得到分数的多有评价网页重要性的方法,就是PageRank的基本设计想法,也称作链接关系分析(link analyze)。
PageRank的计算公式
如果分数被这样不断地传递下去,因为万维网彼此相连,这样的计算会没完没了吗?或者说PageRank的计算会收敛吗?
图4-18所示为对三个网页分别计算它们PageRank的一个迭代收敛的例子。
PageRank的迭代收敛例子
在图4-18中,无论怎样迭代的计算,不难发现。每个网页的得分都是固定不变的。网页A的分数平均分给了网页B和网页C,网页B又完全给了C,最后网页C把得到的分数又还给了网页A。可以看出这3个网页得到的分数之和总是1,而且无论如何循环计算,这种分数分布不再发生变化。这种特性在数学上称为“不变分布”,这也是PageRank计算收敛的且终奥秘。当然PageRank实际的计算公式考虑了各种因素,使得这种不变分布必然存在。这些数学上的原理,请读者参阅相关随机过程的书籍或论文予以透彻了解,下面深圳SEO将介绍PageRank的计算公式。
PageRank采用以下公式计算:[Sergey Brin 1998]
PageRank的计算公式
说明如下:
1.PRn(A):网页A的PageRank值。
2.PRn-1(Ti):网页Ti存在指向A的链接,并且网页Ti在上一次迭代时的PageRank值.
3.C( Ti):网页Ti的外链数量。
4.d:阻尼系数,O<d<1,阻尼系数表示在随机冲浪模型中网页Ti将自身d的份额的PageRank厦平均分给每个外链。由于网页Ti指向网页A,因此网页A获得来自网页Ti的C(Ti)分之一的PageRank值。
从整体上来看这个公式,一个网页A的PageRank值,由两方面得分决定,其比例分别为1-d和d。
一方面,任何网页都有可能跳转到网页A来(不通过链接方式)。假定全集为n个网页,那么其中任意一个网页就有n个可能的无条件跳转的去处。每种跳转的概率相等,均为1/n。因此网页A得到了每个网页的1/n的(1-d)的分数,每个网页的分数初始值都为1。每次分数不论如何流动,其总值都为n。因此,流动的分数值的分数被分配到了网页A上,PageRank中1-d的分数也可以理解为一个网页的基本分数,这是在整个计算中固定不变的常数。
另一方面,由于有些网页存在明确的指向网页A的链接因此d的分数的分数被分配给网页A。
因此对于公式:
pr值的计算方式
第1个部分可以认为是固有得分;第2个部分可以认为是因为被其它网页指向而得到其它网页的一部分得分。
在数学上可以证明,PageRank由两方面因素共同决定的计算方法可以避免Dangling page和Page sink的问题[Langville et al 2003]。
PageRank的计算涉及随机过程方面的数学原理,接下来通过一系列的例子来深入理解。假定存在如图4-19所示的简单的网页链接关系。
PageRank的计算随机过程方面的数学原理
下面由深圳SEO带大家来看看PageRank的计算方法得到下列方程组,假定d=0.5:
PR(A)=0.5+0.5 x PR(C)
PR(B)=0.5+0.5 x(PR(A)/2)
PR(C)=0.5+0.5x(PR(A)/2+PR(B))
解这个三元方程组,得到:
PR(A)=14/13二1.0769
PR(B)=10/13二0.76923
PR(C)=15/13二1.1538
从最后的PageRank值可以清楚地看出,在这3个网页中,网页C的重要性最高,它的得分1.1538分;其次是网页A;最后是网页B。这种通过链接关系的分析得到网页重要性是合理的,网页C在这个局部是更被“认可”的,它被网页A和网页B指向;网页A被更高级别的网页C“认可”,而网页B被网页A“认可”,这样网页A和网页B同样具有一个Backlink。由于网页C的级别大于网页A。因此最终网页A的重要性大于网页B。
此外,PageRank还可以通过迭代计算的方法得到,计算过程如图4-2所示。
这里初始向量为s:=(1  1  1)t,表示每个网页的初始PageRank值均为l。到这第7次迭代时,迭代结果和第6次迭代的结果基本相同,因此迭代停止。继续计算下去,PageRank值不再变化或有很小的变化,这种稳定的PageRank值被用于衡量网页的重要性。然而当网页数量很大,这种链接关系复杂时,采用这些方法是低效的.
PageRank的计算方法
在实践中.采用万法(Power method)来计算PageRank。
深圳SEO带来PageRank的这个经典公式:
PageRank经典公式
可以转化为求解  limax图   的值。其中矩阵为阻尼系数(A也被称为“Google matrix”)。d为阻尼系数,p为概率转移矩阵,eT为n维的全1行,m为全部网页个数(概率转移矩阵大小,x是各个网页的初始PageRank值,初始每个网页的PageRank值均为1。因此,eeT/m矩阵在每次迭
代时与全部网页的PageRank向量乘积总是保持一个n维的全1-d的向量(在下面的例子中会提到)。这可以理解为总能够从其他网页得到1-d的分数,幂法计算过程的伪码如下。

谷歌pr值详解
谷歌pr值详解
谷歌pr值详解

在最后两次的结果近似成相同的情况下迭代结束。这个结果和解方程、简单迭代的方法求出的结果是一致的。用幂法计算PageRank总是收敛的,即总会在有限的迭代计算轮次内结束。
参考文献(Langville et a1 2003) (Haveliwala et al 2003) (LarsElden 2003)可以进一步深入理解PageRank计林过程收敛的奥秘,以及参数d是如何影响收敛速度的基本原理。
在实际应用中,计算PageRank的过程要比想像的更为复杂。例如从提高收敛效率角度,加快计算速度;采用将Google matrix(PageRank这个概率转移矩阵学术上也称作Google matrix)分块
的思想执行并行计算减少磁盘I/O。从而发挥多CPU的作用,有兴趣的读者可以进一步探索。
自从PageRank的计算方法被公开后,各种为了提高排名而进行的作弊行为也随之而来。Google及其他采用类似技术的搜索引擎公司都面临着前所未有的压力,PageRank的科学性和可信度也受到了极大怀疑。但是科学家们采用了各种反作弊的技术手段,沉重打击了作弊者的不道德行为,维护了PageRank应有的价值。
至此,今天在深圳SEO发表这篇谷歌PageRank已经结束了分析系统的全部旅程。为了更好的从全局理解分析系统各个模块的工作关系,下一节中将和大家一起从宏观全局的视角重新回顾分析系统。
本文出自深圳SEO公司,未经允许不得转载:深圳SEO-微笑SEO服务公司 » 搜索引擎分析谷歌的PR值(PageRank)
分享到: 更多 (0)

评论 1

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    Con lo que va a deber andarse con mucho cuidado.

    cerrajeros 24 horas zaragoza9个月前 (02-13)回复