Google 的秘密- PageRank

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语言的语风相像，因此可读性很高。详细请参照 www.octave.org/。 当然，除了Octave以外 MATLAB 和 Scilab 也是非常不错的语言，但是根据 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




文章整理：西部数码--专业提供域名注册、虚拟主机服务

http://www.west263.com

以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!