`

【转】Google Page Rank 算法(转载) - 北溟居 - CSDN博客

阅读更多

先保存一下,待有时间好好研究

1.Google PageRank 算法

1.1PageRank(网页级别)的概念
互联网发展早期的搜索引擎,对web页面的排序,是根据搜索的词组(短语)在页面中的出现次数(occurence ),并用页面长度和html标签的重要性提示等进行权重修订。链接名气(link popularity)技术通过其它文档链接到当前页面(inbound links)的链接数量来决定当前页的重要性,这样可以有效地抵制被人为加工的页面欺骗搜索引擎的手法。

PageRank计算页面的重要性,对每个链入(inbound)赋以不同的权值,链接提供页面的越重要则此链接入越高。当前页的重要性,是由其它页面的重要性决定的。

1.2PageRank算法1

PR(A) = (1-d) + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中:PR(A):页面A的网页级别,
PR(Ti):页面Ti的网页级别,页面Ti链向页面A,
C(Ti):页面Ti链出的链接数量,
d:阻尼系数,取值在0-1之间.

由此可见,1)这个算法不以站点排序,页面网页级别由一个个独立的页面决定;2)页面的网页级别由链向它的页面的网页级别决定,但每个链入页面的贡献的值是不同的。如果Ti页面中链出越多,它对当前页面A的贡献就越小。A的链入页面越多,其网页级别也越高;3)阻尼系数的使用,减少了其它页面对当前页面A的排序贡献。

由此可见,1)这个算法不以站点排序,页面网页级别由一个个独立的页面决定;2)页面的网页级别由链向它的页面的网页级别决定,但每个链入页面的贡献的值是不同的。如果Ti页面中链出越多,它对当前页面A的贡献就越小。A的链入页面越多,其网页级别也越高;3)阻尼系数的使用,减少了其它页面对当前页面A的排序贡献。

1.3、随机冲浪模型
Lawrence Page 和 Sergey Brin 提出了用户行为的随机冲浪模型,来解释上述算法。他们把用户点击链接的行为,视为一种不关心内容的随机行为。而用户点击页面内的链接的概率,完全由页面上链接数量的多少决定的,这也是上面PR(Ti)/C(Ti)的原因。一个页面通过随机冲浪到达的概率就是链入它的别的页面上的链接的被点击概率的和。阻尼系数d的引入,是因为用户不可能无限的点击链接,常常因劳累而随机跳入另一个页面。d可以视为用户无限点击下去的概率,(1-d)则就是页面本身所具有的网页级别。

1.4PageRank算法2(对算法1的修订)

PR(A) = (1-d) / N + d (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))
其中N是互联网上所有网页的数量

由此,所有页面的网页级别形成的一个概率分布,所有页面的网页级别之和是1。在算法1中,随机冲浪访问某个页面的概率由互联网的总页数决定,在算法2中,网页级别是一个页面被随机访问的期望值。
以下讲解,皆基于算法1,主要是计算简单,因为不用考虑N的值。

由此,所有页面的网页级别形成的一个概率分布,所有页面的网页级别之和是1。在算法1中,随机冲浪访问某个页面的概率由互联网的总页数决定,在算法2中,网页级别是一个页面被随机访问的期望值。
以下讲解,皆基于算法1,主要是计算简单,因为不用考虑N的值。

1.5PageRank的特性
所有页面的网页级别之和等于互联网的总页数。在网页数比较少的情况下,网页级别方程可以解出,而面对互联网上成亿的网页,再解方程是不可能的。
此处设阻尼系数为0.5,虽然Lawrence Page 和 Sergey Brin在实际将其设为 0.85.

PR(A) = 0.5 + 0.5 PR(C)
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))
解得:
PR(A) = 14/13 = 1.07692308
PR(B) = 10/13 = 0.76923077
PR(C) = 15/13 = 1.15384615
有:
PR(A)+PR(B)+PR(C)=3

1.6、迭代计算pagerank
Google采用一种近似的迭代的方法计算网页的网页级别的,也就是先给每个网页一个初始值,然后利用上面的公式,循环进行有限次运算得到近似的网页级别。根据Lawrence Page 和 Sergey Brin公开发表的文章,他们实际需要进行100次迭代才能得到整个互联网的满意的网页级别值,这儿的例子只用了10多次就可以了。在迭代的过程中,每个网页的网页级别的和是收敛于整个网络的页面数的。所以,每个页面的平均网页级别是1,实际上的值在(1-d)和(dN+(1-d))之间。

迭代次数

PR(A)

PR(B)

PR(C)

0

1

1

1

1

1

0.75

1.125

2

1.0625

0.765625

1.1484375

3

1.07421875

0.76855469

1.15283203

4

1.07641602

0.76910400

1.15365601

5

1.07682800

0.76920700

1.15381050

6

1.07690525

0.76922631

1.15383947

7

1.07691973

0.76922993

1.15384490

8

1.07692245

0.76923061

1.15384592

9

1.07692296

0.76923074

1.15384611

10

1.07692305

0.76923076

1.15384615

11

1.07692307

0.76923077

1.15384615

12

1.07692308

0.76923077

1.15384615

1.7Google搜索引擎的网页级别的实现
有三个因素决定的网页的等级:网页特定性因素、入链锚的文本、网页级别。
网页特定性因素包括网页的内容、标题及URL等。
为提供检索结果,Google根据网页特定性因素和入链锚的文本计算出网页的IR值,这个值被检索项在页面中的位置和重要性加权,以决定网页和检索请求相关性。IR值和网页级别联合标志网页的基本重要程度,这两个值的联合方式有多种,但明显的是不能相加的。
由于网页级别只对非特定的单个词的检索请求影响比较明显,对于由多个检索词构成的检索请求,内容相关性的分级标准的影响更大。

1.8、用Google工具条显示当前页面的网页级别
Google工具条是Google公司开发的IE插件,需要从Google下载并安装。注意,显示网页级别的功能是其高级功能,这时会自动收集用户的信息,并会自动升级工具条。
这个工具条显示的网页级别分为0-10共11级,如果根据理论用(Nd+(1-d))测算,假定d=0.85,则推测实际网级别的对数即为显示的级别,且对数的基数在6-7之间。

Google的目录服务可以显示网站的级别
此处级别分为7级。有人对两种级别进行了比较。


1.9、入链对计算页面级别的影响
入链总是能增加当前页面的级别,尤其当前页与其下级页面构成回路时,这种贡献更大。如右图例,设ABCD各 页初始级别为1,阻尼系数为0.5,PR(X)/C(X)=10。则易算出

PR(A) = 19/3 = 6.33
PR(B) = 11/3 = 3.67
PR(C) = 7/3 = 2.33
PR(D) = 5/3 = 1.67

如果A不在回路上,则只能得0.5*10=5的收益。
阻尼系数越大,页面级别的收益越大,且整个回路上都能收到更大的收益(即入链收益更能平均地分布到各个回路页面上。针对上例,将阻尼系数改为0.75,则有

PR(A) = 419/35 = 11.97
PR(B) = 323/35 = 9.23
PR(C) = 251/35 = 7.17
PR(D) = 197/35 = 5.63

除回路上各个页面的级别值明显增大外,PR(A)/PR(D)的值敢明显减少了。
入链对整个回路上所有页面的级别值的增加之和,可以由下面这个公式得出.

(d / (1-d)) × (PR(X) / C(X))

这个公式,可以由 简单推导出。
1.10、出链对计算页面级别的影响
增加出链不会影响整个web的总级别,但一个站点失去的级别值等于链到的站点的增加值之和。对于两个封闭的站点,从一个站点链上另一个站点时,增加的和减少的都是(d(/(1-d) × (PR(X) / C(X)).如果这两个站点互相链接,则此值减少。用随机冲浪模型可以解释这种现象,就是出链的增加,减少了用户访问站内页面的概率。举例如图,设阻尼系数 为0.75,则

PR(A) = 0.25 + 0.75 PR(B)
PR(B) = 0.25 + 0.375 PR(A)
PR(C) = 0.25 + 0.75 PR(D) + 0.375 PR(A)
PR(D) = 0.25 + 0.75 PR(C)
得:
PR(A) = 14/23
PR(B) = 11/23
PR(C) = 35/23
PR(D) = 32/23
PR(A)+PR(B)=25/23
PR(C)+PR(D)=67/23
PR(A)+PR(B)+PR(C)+PR(D)=92/23=4

Page和Brin将这样的链接称为悬摆链,它链到页面没有出链。悬摆链对页 面的级别计算产生负面影响。如例,阻尼系数为0.75.

PR(A) = 0.25 + 0.75 PR(B)
PR(B) = 0.25 + 0.375 PR(A)
PR(C) = 0.25 + 0.375 PR(A)
得:
PR(A) = 14/23
PR(B) = 11/23
PR(C) = 11/23
PR(A)+PR(B)+PR(C)=36/23

据Page和Brin,Google在索引页面时,悬摆链的量很大,
主要是由于限制robot.txt的限制及索引了一些没有链出的文件类
型如PDF等。为消除这种负面影响,google在计算级别时,将此
类链接从数据库里去掉,在计算完毕后,再单独计算悬摆链所链
到页面。由此可见,PDF类的文件还是可以放心地在网上发布的。

1.11、页面数量的影响
先看例子。阻尼系数为0.75,PR(X)/C(X)=10,则

PR(A) = 0.25 + 0.75 (10 + PR(B) + PR(C))
PR(B) = PR(C) = 0.25 + 0.75 (PR(A) / 2)
得:

PR(A) = 260/14
PR(B) = 101/14
PR(C) = 101/14
PR(A)+PR(B)+PR(C)=33;
增加页面D;
PR(A) = 0.25 + 0.75 (10 + PR(B) + PR(C) + PR(D))
PR(B) = PR(C) = PR(D) = 0.25 + 0.75 (PR(A) / 3)

PR(A) = 266/14
PR(B) = 70/14
PR(C) = 70/14
PR(D) = 70/14
PR(A)+PR(B)+PR(C)+PR(D)=34

增加页面后,所有页面的级别值之和增加了1,A页略有增加,而B、C则用大幅下降。
再看右边的例子,假定同上。

PR(A) = 0.25 + 0.75 (10 + PR(C))
PR(B) = 0.25 + 0.75 × PR(A)
PR(C) = 0.25 + 0.75 × PR(B)
得:
PR(A) = 517/37 = 13.97
PR(B) = 397/37 = 10.73
PR(C) = 307/37 = 8.30

增加页面D:
PR(A) = 0.25 + 0.75 (10 + PR(D))
PR(B) = 0.25 + 0.75 × PR(A)
PR(C) = 0.25 + 0.75 × PR(B)
PR(D) = 0.25 + 0.75 × PR(C)
得:
PR(A) = 419/35 = 11.97
PR(B) = 323/35 = 9.23
PR(C) = 251/35 = 7.17
PR(D) = 197/35 = 5.63

增加页面后,所有页面级别增加了1,但每个页面的级别值减少了,这是由于新加页面分享了入链代来的值。从这个结果看,增加页面减少了已有页面的级别值,露了google算法青睐小站点的特点。当然,大站点也会因内容丰富而吸引其它 站点的出链而得以级别值增加。
1.12、针对搜索引擎优化的级别分布
先看两个列子,阻尼系数为0.5,PR(X)/C(X)=10;

BC之间无链接时:

PR(A) = 0.5 + 0.5 (10 + PR(B) + PR (C))
PR(B) = 0.5 + 0.5 (PR(A) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2)

PR(A) = 8
PR(B) = 2.5
PR(C) = 2.5
BC之间互相链接时:
PR(A) = 0.5 + 0.5 (10 + PR(B) / 2 + PR(C) / 2)
PR(B) = 0.5 + 0.5 (PR(A) / 2 + PR(C) / 2)
PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B) / 2)
得:
PR(A) = 7
PR(B) = 3
PR(C) = 3

当BC 间互链时,虽然减少了A的级别,但BC都增加了。这符合优化站点所有页面而非只主页的优化思路,因为只有每个页面的级别都提高了,当有检索词命中这些页面时,它们才能排在前面。这种优化的方法也很明显了,就是尽可能地在所有页面间平均分布入链的贡献,各低级页面要增加互链。

只要不影响易用性,尽可能地将所有出链集中在一个或几个低级页面中,可以有效地降低出链对页面级别计算的负面影响。看列子:阻尼系数为0.5, PR(X)/C(X)=10;

BCD都有出链时:

PR(A) = 0.5 + 0.5 (PR(B) / 2 + PR(C) / 2 + PR(D) / 2)
PR(B) = PR(C) = PR(D) = 0.5 + 0.5 (PR(A) / 3)
得:
PR(A) = 1
PR(B) = 2/3
PR(C) = 2/3
PR(D) = 2/3
出链集中于D时:
PR(A) = 0.5 + 0.5 (PR(B) + PR(C) + PR(D) / 4)
PR(B) = PR(C) = PR(D) = 0.5 + 0.5 (PR(A) / 3)
得:
PR(A) = 17/13
PR(B) = 28/39
PR(C) = 28/39
PR(D) = 28/39

从结果看,出链集中后,ABCD各页面的级别都上升了。
1.13、影响页面级别的其它因素
在Lawrence Page和Sergey Brin关于PageRank的论文发表以后,除了web的链接结构以外,还有没有别的因素被加到PageRank的算法当中曾经有过广泛地讨论。 Lawrence Page本人在PageRank的专利说明中曾指出以下潜在的影响因素:链接的能见度,链接在文档中的位置,web页面间的距离,出链页面的重要性,页面的不过时。这此因素的增加,可以更好用随机冲浪模型模拟人类利用web的行为。
不管上述附加因素有没有在实际计算PageRank时使用,如何实现这些附加因素仍要讨论。
首先算法公式需要改进.

PR(A) = (1-d) + d (PR(T1)×L(T1,A) + ... + PR(Tn)×L(Tn,A))

此处,L(T1,A)是入链的评价值,由几个因素构成,只需要在迭代前计算一次,减少了对数据库的查询次数,虽然每次迭代的查询结果会有不同。
Lawrence Page在PageRank的专利说明中指出链接评价的两个因素是链接的可见性和在文档中的位置。链接评价取代了PR(A)/C(A),指出了对一特定的页面的链接,每个链接被点击的概率是不同的。
此处,每一链接有两个属性值,X表示可见度,如果没有被重点强调(如粗体、斜体等) 为1否则为2,Y表链接在文档中的位置,如果在文档下半部为1否则为3。则有

X(A,B) × Y(A,B) = 1 × 3 = 3
X(A,C) × Y(A,C) = 1 × 1 = 1
X(B,A) × Y(B,A) = 2 × 3 = 6
X(B,C) × Y(B,C) = 2 × 1 = 2
X(C,A) × Y(C,A) = 2 × 3 = 6
X(C,B) × Y(C,B) = 2 × 1 = 2
易得:
Z(A) = X(A,B) × Y(A,B) + X(A,C) × Y(A,C) = 4
Z(B) = X(B,A) × Y(B,A) + X(B,C) × Y(B,C) = 8
Z(C) = X(C,A) × Y(C,A) + X(C,B) × Y(C,B) = 8
链接评价公式为:(页面T1指向T2)
L(T1,T2) = X(T1,T2) × Y(T1,T2) / Z(T1)
有:
L(A,B) = 0.75
L(A,C) = 0.25
L(B,A) = 0.75
L(B,C) = 0.25
L(C,A) = 0.75
L(C,B) = 0.25
最后利用改进的公式计算页面级别:
PR(A) = 0.5 + 0.5 (0.75 PR(B) + 0.75 PR(C))
PR(B) = 0.5 + 0.5 (0.75 PR(A) + 0.25 PR(C))
PR(C) = 0.5 + 0.5 (0.25 PR(A) + 0.25 PR(B))
得:
PR(A) = 819/693
PR(B) = 721/693
PR(C) = 539/693

为了防止人为的级别优化,页面的距离被用来影响链接的评价。站内链接的权重小于站间链接的权重。页面的距离可能由页面是否在一个站内、一个服务器及物理距离等决定。
另一个影响页面重要性的能参数,是页面的不过时性(up-to-dateness),意指有越多的新建的页面指向某一个页面,则这个页面内容过时的可能性越小。
为增加这些因素的影响,要对公式进行修订如下:

L(Ti,A) = K(Ti,A) × K1(Ti) × ... × Km(Ti)

其中,K(Ti,A)表示链接可见度及位置的权重,Kn(Ti)是第n个因素对页面Ti的影响。看列子:此处,从C引出的链接的重要性是其它 的4倍。

K(A) = 0.5
K(B) = 0.5
K(C) = 2
计算级别值:
PR(A) = 0.5 + 0.5 × 2 PR(C)
PR(B) = 0.5 + 0.5 × 0.5 × 0.5 PR(A)
PR(C) = 0.5 + 0.5 (0.5 PR(B) + 0.5 × 0.5 PR(A))
得:
PR(A) = 4/3
PR(B) = 2/3
PR(C) = 5/6

此时,所有页面的级别之和不等于页面数量。
1.14 PageRank 算法的改进

1. 主题敏感的PageRankTopic-Sedsitive PageRank
在这个算法中,我们需要预先计算离线时页面的重要性的分数;然后,我们为每一个页面计算多种重要性分数,即关于不同的主题来计算这个页面的重要性分数。在查询的时候,把这些重要性分数与根据被查询的主题的重要性分数综合在一起,就形成一个复合的PageRank分数。采用这种方法能形成更加精确的排序值,而不是原始普通的排序值。

2. 二次方程推断法(Quadratic Extra polation
这是一个可以加快PageRank的运算速度的方法。它能通过周期性的削减当前的矩阵乘幂迭代的非主要特征向量的方法,大大加快其收敛速度。使用这种方法计算PageRank值时,当计算一个包含8000万个节点的网络图时,与采用原来的PageRank方法相比,计算速度可以提高20%-300%。

3. 分块矩阵排序算法(BlockRank Algo rithm

该算法是PageRank算法的另一个加速算法,它首先把网络根据领域划分成不同的区域(块),为每个区域计算它们的局部PageRank值;估计它们的相对的重要性(每个区域的BlockRank值);用这个区域的Block-Rank.值来给每个区域的Block-Rank赋予一定的权重。然后再把这些加权的局部

的PageRank值近似地看作全局的PageRank向量,把这个向量作为标准的PageRank算法的开始向量。这种方法可以减少计算的迭代次数,可以把更多的时间用于收敛速度慢的区域的计算,提高了局部PageRank计算的有效性。BlockRank算法可以采取并行或分布的形式来进行计算,节约运算的时间。此外,局部的PageRank计算结果在以后的计算中可以被再利用。

Google Page Rank 算法(转载) - 北溟居 - CSDN博客

分享到:
评论

相关推荐

    谷歌pagerank算法

    谷歌 pagerank 算法是互联网历史上具有里程碑意义的算法之一,由谷歌创始人拉里·佩奇和谢尔盖·布林共同设计。它的核心思想来源于论文引用关系的研究,认为一篇论文的重要性可以通过引用它的其他论文数量来衡量。在...

    Page Rank

    Page Rank是Google搜索引擎算法的核心组成部分,它通过评估网页之间的链接关系来确定网页的重要性。这个概念由Google的创始人拉里·佩奇(Larry Page)和谢尔盖·布林(Sergey Brin)在1996年提出,是他们早期搜索...

    Rank-Rnet.rar_Page Rank_driverh92_page_重要性排序

    Page Rank是Google创始人Larry Page提出的一种网页排名算法,它通过计算网页之间的链接关系来评估网页的重要性,成为搜索引擎优化(SEO)领域的一个核心概念。在这个名为"Rank-Rnet.rar"的压缩包文件中,我们看到一...

    根据《集体智慧编程》实现的一个小型的搜索引擎,包括page rank算法和BF 神经网络算法的实现.zip

    Page Rank是Google的创始人拉里·佩奇和谢尔盖·布林提出的著名算法,用于评估网页在互联网上的重要性。其基本思想是:一个被许多高质量网页链接的页面,其Page Rank值通常较高。Page Rank的计算过程涉及以下几个...

    人工智能-项目实践-搜索引擎-基于page rank的个人搜索引擎项目

    Page Rank是由Google创始人拉里·佩奇和谢尔盖·布林提出的算法,用于评估网页的重要性。该算法的基本思想是,一个网页的Page Rank值不仅取决于其本身的质量,还与链接到它的其他网页的Page Rank有关。高Page Rank的...

    Vue2.x和Vue3.x面试常问知识点-面试题-JackieDYH - CSDN博客.pdf

    1. **SPA(Single Page Application)理解**: - SPA是指在页面首次加载后,通过JavaScript动态更新DOM来改变页面内容,而不是重新加载整个页面。这提供了更好的用户体验,减少了页面跳转时间。 - 优点包括更好的...

    结合听歌排行爬虫开发的微信小程序song-rank-wxapp-master.zip

    在本项目"song-rank-wxapp-master.zip"中,我们关注的是一个基于微信小程序的音乐排行榜应用的开发。微信小程序是一种轻量级的应用形态,它无需下载安装即可使用,为用户提供了便捷的在线体验。这个项目的重点在于...

    大数据十大经典算法PageRank-讲解课件.ppt

    PageRank算法是Google搜索引擎的核心算法之一,由Larry Page和Sergey Brin提出,用于评估网页的重要性。下面是对PageRank算法的详细解释。 一、PageRank的定义 PageRank是一个函数,对Web中的每个网页赋予一个实数...

    google搜索算法重要核心

    标题中的“google搜索算法重要核心”指的主要是Google在搜索引擎技术方面所采用的关键算法,这些算法使得Google能够高效、准确地处理海量数据,为用户提供快速且相关的搜索结果。描述中提到的“并行计算”,是Google...

    [搜索链接]Page Rank查询_pagerank.zip

    Page Rank是Google创始人Larry Page提出的一种网页排名算法,它在搜索引擎优化(SEO)领域具有重要地位。这个压缩包文件“Page Rank查询_pagerank.zip”很可能包含关于Page Rank算法的详细资料,帮助我们理解其原理...

    详解页式管理置换算法FIFO-LRU-OPT.docx

    在虚拟内存管理中,页式管理是一种常用的技术,它通过将程序地址空间分割成固定大小的页(page),与物理内存中的相应大小块(frame)进行交互。这种管理方式要求操作系统必须处理好页面置换问题,即在内存不足的...

    页面置换算法模拟-OPT、FIFO及LRU算法.docx

    在操作系统中,页面置换算法是解决虚拟内存管理中页故障问题的关键技术,它涉及到如何选择在物理内存中被替换出去的页面。本实验报告主要介绍了三种常见的页面置换算法:先进先出(FIFO)、近来最久未使用(LRU)...

    Google-Chrome-Google-Page-Rank:获取 Google 页面排名并将其显示在地址栏中的 Chrome 扩展程序

    "Google-Chrome-Google-Page-Rank" 指的是一款针对 Google Chrome 浏览器的扩展程序,它的主要功能是获取网页的 Google Page Rank(谷歌页面排名),并将其结果显示在浏览器的地址栏中。Google Page Rank 是 Google ...

    在 Matlab 中实现Page Rank 算法.rar

    1.版本:matlab2014/2019a/2021a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程...

    大数据十大经典算法PageRank 讲解PPT.ppt

    PageRank 算法是一种评估网页重要性的算法,由 Google 公司创始人 Larry Page 和 Sergey Brin 于 1998 年提出。该算法的主要思想是:被越多优质的网页所指的网页,它是优质的概率就越大。 PageRank 算法的定义 ----...

    Google的PageRank算法学习

    PageRank是Google搜索引擎的核心算法之一,由Google的创始人Larry Page和Sergey Brin在斯坦福大学研究期间提出。该算法的主要目的是通过对网页之间的链接关系进行分析,为每一个网页赋予一个数值权重,即“网页级别...

    页面调度算法模拟

    本实验具体目标为模拟实现一种页面调度算法——最优调度算法(Optimal Page Replacement Algorithm, OPT)。这是一种理想的调度算法,其基本思想是在所有未被替换的页面中选择未来最长时间内不会被访问的页面作为...

    国外PR批量查询工具

    PaRaMeter stands for "Page Rank Meter" - a free Google PageRank checking and monitoring tool. PageRank is one of the methods Google uses to determine how relevant and important a page is. PageRank is ...

Global site tag (gtag.js) - Google Analytics