收藏本站 收藏本站
积木网首页 - 软件测试 - 常用手册 - 站长工具 - 技术社区
积木学院 > 搜索引擎 > 资源分享 > 正文

Google 的秘密- PageRank 彻底解说 中文版

来源:互联摘选 日期:2007-11-30 21:32

1.前言

最近,搜索引擎 Google (http://www.google.com/)非常引人注目。Google 是基于现担任 CEO 的 Larry Page 和担任总经理的 Sergey Brin (2001年2月)在就读于美斯坦福大学研究生院时所开发的搜索引擎的一种检索服务。Google 从1998年9月开始服务,但Netscape CommunicationsGoogle 的测试阶段就开始与其合作,美国 Yahoo! 公司也从2000年6月起将默认搜索引擎(美国 Yahoo! 不能检索时作为增补的搜索引擎)由原先合作的 Inktomi 转换为了 Google。日语版 Google 在2000年9月正式登场,现已被 BIGLOBE(NEC)所采用。 (注:2001年4月 Yahoo! JAPAN@NIFTY,7月索尼,2002年1月 Excite 也相继与 Google 建立了协作关系)。

Google 被评价的优点不仅仅在于去除无用的(广告)标语构成单一页面的功能、独自的 Cache 系统、动态制成摘要信息、为实现高速检索而设置的分散系统(数千台规模的Linux群集器)等,而其中最大的优点正是它检索结果的正确性。一种能够自动判断网页重要性的技术「PageRank是(网页等级)」就是为此而设计的一种技术。 本文的目的就是以尽可能浅显易懂的语言来说明 PageRank 系统的概要和原理。

以下是 PageRank 的一篇基础文章。

Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998,
http://www-db.stanford.edu/~backrub/pageranksub.ps

为了更高效地计算 PageRank,以下是改良以后的一篇论文。

Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999,
http://dbpubs.stanford.edu:8090/pub/1999-31

另外,以下是 PageRank 的演示用资料(PowerPoint)。

Larry Page, 'PageRank: Bringing Order to the Web',
http://hci.stanford.edu/~page/papers/pagerank/ (已失效)

接下来就对这两篇文章(另加一篇资料)进行基本说明。 首先,用简单的例子来解说 PageRank 的概念,再归结到使用超链接关系的排序系统来解决大规模疏松疏矩阵的特性值的问题。然后我们会接触一些在现实世界中应用基本模型时出现的问题和对应方法。接下来,为了探讨是否能够作为「个人化 PageRank」使用,进行对免费全文检索系统 Namazu 的安装实验并对其结果进行阐述。最后发表我对 PageRank 的个人见解。

另外,为了能够理解以下的说明内容,需要大学基础课程程度的数学知识(尤其是线形代数)。然而为使文科生也能够顺利读下去,尽可能地不用算式来说明问题,同时,为了加入笔者个人的见解,没有加入像原文那么多的算法和数字,也存在许多不够严密和欠正确的地方,事先在次声明。具体内容请参照原文。

PageRank(TM) 是美国 Google 公司的登记注册商标。

2. PageRank 的基本概念

PageRank 是基于「从许多优质的网页链接过来的网页,必定还是优质网页」的回归关系,来判定所有网页的重要性。

在以下冗长的说明中,许多部分大量地使用了专业用语,会造成理解上的困难。这一章虽然准备集中于定性而简单的解说,但是,即使如此也会有怎么也不明白的时候,此时只要能够理解「从许多优质的网页链接过来的网页,必定还是优质网页」这一思考方法也就非常得可贵了。因为在所有几个要点中,这个是最重要的思考方法。

来自于 Google 自己的介绍「Google的受欢迎的秘密(http://www.google.co.jp/intl/ja/why_use.html)」 是象以下一样解说的。

关于PageRank
    PageRank,有效地利用了 Web 所拥有的庞大链接构造的特性。 从网页A导向网页B的链接被看作是对页面A对页面B的支持投票,Google根据这个投票数来判断页面的重要性。可是 Google 不单单只看投票数(即链接数),对投票的页面也进行分析。「重要性」高的页面所投的票的评价会更高,因为接受这个投票页面会被理解为「重要的物品」。
    根据这样的分析,得到了高评价的重要页面会被给予较高的 Page Rank(网页等级),在检索结果内的名次也会提高。PageRank 是 Google 中表示网页重要性的综合性指标,而且不会受到各种检索(引擎)的影响。倒不如说,PageRank 就是基于对"使用复杂的算法而得到的链接构造"的分析,从而得出的各网页本身的特性。
    当然,重要性高的页面如果和检索词句没有关联同样也没有任何意义。为此 Google 使用了精练后的文本匹配技术,使得能够检索出重要而且正确的页面。

通过下面的图我们来具体地看一下刚才所阐述的算法。具体的算法是,将某个页面的 PageRank 除以存在于这个页面的正向链接,由此得到的值分别和正向链接所指向的页面的 PageRank 相加,即得到了被链接的页面的 PageRank。

PageRank 概念图。(引自 Page et al.(1998) Figure 2 'Simplified Page Calculation')

让我们详细地看一下。提高 PageRank 的要点,大致有3个。

  • 反向链接数 (单纯的意义上的受欢迎度指标)
  • 反向链接是否来自推荐度高的页面 (有根据的受欢迎指标)
  • 反向链接源页面的链接数 (被选中的几率指标)

首先最基本的是,被许多页面链接会使得推荐度提高。也就是说「(被许多页面链接的)受欢迎的页面,必定是优质的页面」。所以以反向链接数作为受欢迎度的一个指标是很自然的想法。这是因为,“链接”是一种被看作「可以看看这个页面/这个页会有用」的推荐行为。但是,值得骄傲的是 PageRank 的思考方法并没有停留在这个地方。

也就是说,不仅仅是通过反向链接数的多少,还给推荐度较高页面的反向链接以较高的评价。同时,对来自总链接数少页面的链接给予较高的评价,而来自总链接数多的页面的链接给予较低的评价。 换句话说「(汇集着许多推荐的)好的页面所推荐的页面,必定也是同样好的页面」和「与感觉在被胡乱链接的链接相比,被少数挑选出的链接肯定是优质的链接」这两种判断同时进行着。一方面,来自他人高水平网页的正规链接将会被明确重视,另一方面,来自张贴有完全没有关联性的类似于书签的网页的链接会作为「几乎没有什么价值(虽然比起不被链接来说好一些)」而被轻视。

因此,如果从类似于 Yahoo! 那样的 PageRank 非常高的站点被链接的话,仅此网页的 PageRank 也会一下子上升;相反地,无论有多少反向链接数,如果全都是从那些没有多大意义的页面链接过来的话,PageRank 也不会轻易上升。不仅是 Yahoo!, 在某个领域中可以被称为是有权威的(或者说固定的)页面来的反向链接是非常有益的。但是,只是一个劲地在自己一些同伴之间制作的链接,比如像「单纯的内部照顾」这样的做法很难看出有什么价值。也就是说,从注目于全世界所有网页的视点来判断(你的网页)是否真正具有价值。

综合性地分析这些指标,最终形成了将评价较高的页面显示在检索结果的相对靠前处的搜索结构。

以往的做法只是单纯地使用反向链接数来评价页面的重要性,但 PageRank 所采用方式的优点是能够不受机械生成的链接的影响。 也就是说,为了提高 PageRank 需要有优质页面的反向链接。 譬如如果委托 Yahoo! 登陆自己的网站,就会使得 PageRank 骤然上升。但是为此必须致力于制作(网页的)充实的内容。这样一来,就使得基本上没有提高 PageRank 的近路(或后门)。不只限于PageRank (Clever 和 HITS 等也同样),在利用链接构造的排序系统中,以前单纯的 SPAM 手法将不再通用。这是最大的一个优点,也是 Google 方便于使用的最大理由。(虽然是最大的理由,但并不是唯一的理由。)

在这里请注意,PageRank 自身是由 Google 定量,而与用户检索内容的表达式完全无关。就像后边即将阐述的一样,检索语句不会呈现在 PageRank 自己的计算式上。不管得到多少的检索语句,PageRank 也是一定的、文件固有的评分量。

PageRank 的定性说明大致就是这样一些。但是,为了实际计算排列次序、比较等级,需要更定量性的讨论。以下一章将做详细的说明。

3.怎样求得 PageRank

我们感兴趣的是,在有像超级链接构造那样的互相参照关系的时候,定量地知道哪一个页面是最「重要」的。换句话大胆地说,这个也就是严密计算「应该从哪一页开始读取」这个指标的过程。就算从谁都不看的小页面开始读取也没有办法。

那么,一般地说为了使得像 Web 那样的超级链接构造能够反映在在排列次序上,需要在计算机上建立超级链接构造的数字模型。 怎么模型化需要取决于安装者的方针所以一概而论,但是如果应用图表理论来观察超级链接构造的话,最终常常回到线形代数考虑方法上去。这对于 PageRank 也是一样的。

计算方法的原理

作为最基本的考虑方法,就是用行列阵的形式来表达链接关系。从页面 i 链接到另一张页面 j 的时,将其成分定义为1,反之则定义为 0 。即,行列阵 A 的成分 aij 可以用,

  aij=1 if  (从页面 i 向页面 j 「 有 」 链接的情况) 

      0 if  (从页面 i 向页面 j 「没有」链接的情况) 

来表示。文件数用 N 来表示的话,这个行列阵就成为 N×N 的方阵。这个相当于在图表理论中的「邻接行列」。也就是说,Web 的链接关系可以看做是采用了邻接关系有向图表 S。总而言之,只要建立了链接,就应该有邻接关系。

(*注)由点和点连接的线构成的图形被称为「图表(graph)」。这些点被称为「顶点(vertex)」或者「节点(node)」;这些线被称为「边(edge)」或者「弧(arc)」。图表分为两类,“边”没有方向的图表被称为「无向图表(undirected graph)」,“边”带有方向的图表被称为「有向图表(directed graph)」。把有向图表想像成单向通行的道路就可以了。 图表能用各种的方法来表示,但一般用在数据结构上的是「邻接行列(adjacency matrix)」和「邻接列表(adjacency list)」。需要注意的是,如果是无向图表,邻接行列 A 就成为了对称行列,而如果是有向图表,A 就会成为不对称行列。

以下是用位图表示的 Apache 的在线手册(共128页)的邻接行列。当黑点呈横向排列时,表示这个页面有很多正向链接(即向外导出的链接);反之,当黑店呈纵向排列时,表示这个页面有很多反向链接

邻接行列的例子(采用了Apache 的在线手册)

PageRank 的行列阵是把这个邻接行列倒置后(行和列互换),为了将各列(column)矢量的总和变成 1 (全概率), 把各个列矢量除以各自的链接数(非零要素数)。这样作成的行列被称为「推移概率行列」,含有 N 个概率变量,各个行矢量表示状态之间的推移概率。倒置的理由是,PageRank 并非重视「链接到多少地方」而是重视「被多少地方链接」。

PageRank 的计算,就是求属于这个推移概率行列最大特性值的固有矢量(优固有矢量)。

这是因为,当线性变换系 t→∞ 渐近时,我们能够根据变换行列的"绝对价值最大的特性值"和"属于它的固有矢量"将其从根本上记述下来。换句话说,用推移概率行列表示的概率过程,是反复对这个行列进行乘法运算的一个过程,并且能够计算出前方状态的概率。

再者,虽然听起来很难,但是求特性值和固有矢量的值是能够严密分析的一种基础的数学手段。我们能够自由地给矢量的初始值赋值,但是因为不断地将行列相乘,得到的矢量却会集中在一些特定数值的组合中。我们把那些稳定的数值的组合称为固有矢量,把固有矢量中特征性的标量(scalar)称为特性值,把这样的计算方法总称为分解特性值,把解特性值的问题称为特性值问题

(*注) 对 N 次的正方行列 A 把满足 Ax =λx 的数 λ 称为 A 的特性值,称 x 为属于 λ 的固有矢量。如果你怎么也不能适应行列的概念的话,你也可以考虑 N×N 的二元排列就可以了。同时,也可以把矢量考虑成为长度为 N 的普通的(一元)排列就可以了。

简单的例子

让我们用简单的例子来试着逐次计算 PageRank 。首先考虑一下有像下图表示那样的链接关系的7个HTML文件。并且,这些HTML文件间的链接关系只是闭合于这1-7的文件中。也就是说,除了这些文档以外没有其他任何链接的出入。另外请注意,所有的页面都有正向和反向链接(即没有终点),这也是后面将提出的一个重要假定,在此暂且不深入探讨。

表示页面间互相链接关系的推移图

首先,把这张推移图图表构造的邻接列表表示为排列式,就有以下式子。即,根据各个链接源ID列举链接目标的ID。

链接源I D 	链接目标 ID

1		2,3 ,4,5, 7

2		1

3		1,2 

4		2,3,5

5 		1,3,4,6 

6		1,5

7		5

以这个邻接列表中所表示的链接关系的邻接行列 A 是以下这样的 7×7 的正方行列。一个仅有要素 0 和 1 位图行列(bitmap matrix)。横向查看第 i 行表示从文件 i 正向链接的文件ID。

A = [

	 0, 1, 1, 1, 1, 0, 1; 

	 1, 0, 0, 0, 0, 0, 0;

	 1, 1, 0, 0, 0, 0, 0; 

	 0, 1, 1, 0, 1, 0, 0;

	 1, 0, 1, 1, 0, 1, 0;

	 1, 0, 0, 0, 1, 0, 0; 

	 0, 0, 0, 0, 1, 0, 0; 

 ]

PageRank 式的推移概率行列 M ,是将 A 倒置后将各个数值除以各自的非零要素后得到的。即以下这个 7×7 的正方行列。横向查看第 i 行非零要素表示有指向文件 i 链接的文件ID(文件 i 的反向链接源)。请注意,各纵列的值相加的和为 1(全概率)。

M = [ 

	0, 	1,	1/2,	0,	1/4,	1/2,	0; 

	1/5,	0,	1/2,	1/3,	0,	0,	0; 

	1/5,	0,	0,	1/3,	1/4,	0,	0; 

	1/5,	0,	0,	0,	1/4,	0,	0; 

	1/5,	0,	0,	1/3,	0,	1/2,	1; 

	0,	0,	0,	0,	1/4,	0,	0;

	1/5,	0,	0,	0,	0,	0,	0;

]

表示 PageRank 的矢量 R (各个的页面的等级数的队列),存在着 R = cMR 的关系(c 为定量)。在这种情况下,R 相当于线形代数中的固有矢量,c 相当于对应特性值的倒数。为了求得 R ,只要对这个正方行列 M 作特性值分解就可以了。

在分解特性值时有相应的各种各样的数值分析法,但是本文将不在这里对各种方法详细说明,请读者自己去阅读一本恰当的教科书(在你的暑假里一定有这么一本被埋没的教科书)。在此,我们就暂且使用决 GNU Octave 这个计算程序实际计算一下特性值和固有矢量。

(*注) GNU Octave ,是支持数值计算,类似于描述性出色的 MATLAB 的编程语言。扩展后的处理语言更适合于行列演算,但基本上和C语言的语风相像,因此可读性很高。详细请参照 http://www.octave.org/。 当然,除了Octave以外 MATLABScilab 也是非常不错的语言,但是根据 GPL, Octave 是最容易得到的。

实际举例

下面我们举一个实际例子。如果不太明白以下例子在做什么的话,只要认为我们能够使用 Octave 这个程序来解特性值问题即可。

首先,使用恰当的编辑器制作以下 Octave 脚本。(在行尾加上分号就能消去多余的结果输出,不过,此次为了说明特意去掉了。)

% cat pagerank.m 

#!/usr/bin/octave 

## pagerank.m - 计算 PageRank(TM) 用的简单的 GNU Octave 脚本



##设置计时器。 

tic(); 



## 根据PageRank 的定义,将从文件 i 链接到文件 j 的链接状态的推移概率行列定义为 M(i,j)



M = [

	0,	1,	1/2,	0,	1/4,	1/2 ,	0;

	1/5,	0,	1/2,	1/3,	0,	0,	0;

	1/5,	0,	0,	1/3,	1/4,	0,	0;

	1/5,	0,	0,	0,	1/4,	0,	0;

	1/5,	0,	0,	1/3,	0,	1/2,	1;

	0,	0,	0,	0,	1/4,	0,	0;

	1/5,	0,	0,	0,	0,	0,	0; 

] 

##计算 全部 M 的特性值和固有矢量列的组合。



[V,D]= eig(M)



## 保存与绝对价值最大的特性值对应的固有矢量到EigenVector。

    

 EigenVector = V(:, find(abs(diag(D))==max(abs(diag(D))))) 



## PageRank 是将 EigenVector 在概率矢量上标准化后得到的值。

 PageRank = EigenVector./ norm(EigenVector,1) 

 

## 输出计算时间。 

elapsed_time = toc()

(2003/7/23: 修正上述脚本的错误。)

误: EigenVector = V(:, find(max(abs(diag(D))))  )

正: EigenVector = V(:, find(abs(diag(D))== max(abs(diag(D))))) 

用 Octave 运行这个 pagerank.m 脚本后在标准输出中得到以下结果。

% octave pagerank.m 

GNU Octave, version 2.0.16 (i586-redhat-linux-gnu). 

Copyright (C) 1996, 1997, 1998, 1999, 2000 John W. Eaton. 

This is free software with ABSOLUTELY NO WARRANTY. 

For details, type `warranty'. 





M =

 

0.00000 1.00000 0.50000 0.00000 0.25000 0.50000 0.00000 

0.20000 0.00000 0.50000 0.33333 0.00000 0.00000 0.00000

0.20000 0.00000 0.00000 0.33333 0.25000 0.00000 0.00000 

0.20000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000 

0.20000 0.00000 0.00000 0.33333 0.00000 0.50000 1.00000 

0.00000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000 

0.20000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 



V =

 

Columns 1 through 3: 



0.69946 + 0.00000i 0.63140 + 0.00000i 0.63140 + 0.00000i 

0.38286 + 0.00000i -0.28715 + 0.15402i -0.28715 - 0.15402i 

0.32396 + 0.00000i -0.07422 - 0.10512i -0.07422 + 0.10512i

0.24297 + 0.00000i 0.00707 - 0.24933i 0.00707 + 0.24933i 

0.41231 + 0.00000i -0.28417 + 0.44976i -0.28417 - 0.44976i 

0.10308 + 0.00000i 0.22951 - 0.13211i 0.22951+ 0.13211i 

0.13989 + 0.00000i -0.22243 - 0.11722i -0.22243 + 0.11722i 



Columns 4 through 6: 



0.56600 + 0.00000i 0.56600 + 0.00000i -0.32958 + 0.00000i 

0.26420 - 0.05040i 0.26420 + 0.05040i 0.14584 + 0.00000i 

-0.10267 + 0.14787i -0.10267- 0.14787i 0.24608 + 0.00000i 

-0.11643 + 0.02319i -0.11643 - 0.02319i -0.24398+ 0.00000i 

-0.49468 - 0.14385i -0.49468 + 0.14385i 0.42562 + 0.00000i 

-0.14749+ 0.38066i -0.14749 - 0.38066i -0.64118 + 0.00000i 

0.03106 - 0.35747i 0.03106+ 0.35747i 0.39720 + 0.00000i 



Column 7: 



0.00000 + 0.00000i 

-0.40825 + 0.00000i 

-0.00000 + 0.00000i 

0.00000 + 0.00000i 

-0.00000 + 0.00000i 

0.81650 + 0.00000i

-0.40825 + 0.00000i 



D = 



Columns 1 through 3: 



1.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

0.00000 + 0.00000i -0.44433 + 0.23415i 0.00000 + 0.00000i

0.00000 + 0.00000i 0.00000 + 0.00000i -0.44433 - 0.23415i 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 



Columns 4 through 6: 



0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 

0.02731 + 0.31430i 0.00000 + 0.00000i 0.00000 + 0.00000i 

0.00000 + 0.00000i 0.02731 - 0.31430i 0.00000 + 0.00000i 

0.00000 + 0.00000i 0.00000 + 0.00000i -0.16595 + 0.00000i 

0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 



Column 7: 



0.00000 + 0.00000i 

0.00000 + 0.00000i 

0.00000 + 0.00000i 

0.00000 + 0.00000i 

0.00000 + 0.00000i 

0.00000 + 0.00000i 

-0.00000 + 0.00000i 



EigenVector = 

0.69946 

0.38286

0.32396 

0.24297 

0.41231 

0.10308 

0.13989 



PageRank =

0.303514 

0.166134 

0.140575

0.105431 

0.178914 

0.044728 

0.060703 



elapsed_time = 0.063995

Octave 的输出中,特性值被表示为对角行列 D 的对角成分,各个特性值相对应的固有矢量被表示为行列 V 对应列的列矢量。也就是说 M * V = D * M 成立。 如果包含复数特性值的话这里的特性值有7个,其中绝对价值最大的特性值 λ 是λ=1。与之相对应的固有矢量为实矢量:

EigenVector = 

	0.69946 

	0.38286 

	0.32396 

	0.24297 

	0.41231 

	0.10308 

	0.13989

即行列 V 的第1列。请注意,这个求得的固有矢量中概率矢量(要素的和等于1的 N 次元非负矢量)没有被标准化,只是矢量的「大小」等于 1。 用算式来表达就是,Σpi ≠1 ,Σ(pi)2=1。 在这里,对概率矢量进行标准化

PageRank =

	0.303514 

	0.166134 

	0.140575 

	0.105431 

	0.178914 

	0.044728 

	0.060703

PageRank 就是排位了。 注意,全部相加的和为 1。 计算只用了0.064秒。

求得的 PageRank 的评价

将 PageRank 的评价按顺序排列 (PageRank 小数点3位四舍五入)。

名次 PageRank   文件ID    发出链接ID  被链接ID

  1     0.304     1       2,3,4,5,7   2,3,5,6

  2     0.179     5       1,3,4,6     1,4,6,7

  3     0.166     2       1           1,3,4

  4     0.141     3       1,2         1,4,5

  5     0.105     4       2,3,5       1,5

  6     0.061     7       5           1

  7     0.045     6       1,5         5

首先应该关注的是,PageRank 的名次和反向链接的数目是基本一致的。无论链接多少正向链接都几乎不会影响 PageRank,相反地有多少反向链接却是从根本上决定 PageRank 的大小。但是,仅仅这些并不能说明第1位和第2位之间的显著差别(同样地、第3位和第4位,第6位和第7位之间的差别)。总之,绝妙之处在于 PageRank 并不只是通过反向链接数来决定的。

让我们详细地看一下。ID=1 的文件的 PageRank 是0.304,占据全体的三分之一,成为了第1位。特别需要说明的是,起到相当大效果的是从排在第3位的 ID=2 页面中得到了所有的 PageRank(0.166)数。ID=2页面有从3个地方过来的反向链接,而只有面向 ID=1页面的一个链接,因此(面向ID=1页面的)链接就得到了所有的 PageRank 数。不过,就因为 ID=1页面是正向链接反向链接最多的页面,也可以理解它是最受欢迎的页面吧。

反过来,最后一名的 ID=6 页面只有 ID=1 的15%的微弱评价,这可以理解为是因为没有来自 PageRank 很高的 ID=1 的链接而使其有很大地影响。 总之,即使有同样的反向链接的数目,链接源页面评价的高低也影响 PageRank 的高低。

表示页面互相的链接关系的推移图(加入了PageRank)

实际地试着计算一下PageRank的收支。因为λ=1所以计算很简单,只要将自各页的流入量单纯相加即可。譬如 ID=1 的流入量为,

流入量=(ID=2发出的Rank)+(ID=3发出的Rank)+(ID=5发出的Rank)+(ID=6发出的Rank)

    = 0.166+0.141/2+0.179/4+0.045/2

    = 0.30375

在误差范围内PageRank的收支相符合。其他页面ID的情况也一样。以上的 PageRank 推移图正表示了这个收支。沿着各自的链接发出的PageRank等于此页面原有的PageRank除以发出链接数的值,而且和各自的页面的PageRank收支相平衡。

不过,这样绝妙均衡的本身,对理解线形代数的人来说当然不会是让人惊讶的事情。因为这正是「特性值和固有矢量的性质」,总之这样被选的数值的组就是固有矢量。但即使是这样,实际试着确认一下的话,已经能够很好地使用PageRank的方法来考虑了。

以上就是 PageRank 的基本原理。 Google 做的就是大规模地处理这样的非常特性值问题。

(出处:www.Gimoo.net)

推荐阅读

 

热点信息

 
强悍的草根IT技术社区,这里应该有您想要的! 友情链接:b2b电子商务
Copyright © 2010 Gimoo.Net. All Rights Rreserved  京ICP备05050695号