Google 的秘密- PageRank 彻底解说

作者:佚名       来源于:中国营销策划网

(*注) GNU Octave ,是支持数值计算,类似于描述性出色的 MATLAB 的编程语言。扩展后的处理语言更适合于行列演算,但基本上和C语言的语风相像,因此可读性很高。详细请参照 http://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
|<< << < 1 2 3 4 5 6 7 8 9 10 > >> >>|


 5/12   首页 上一页 3 4 5 6 7 8 下一页 尾页

上一篇登录搜索引擎的准备工作

下一篇搜索引擎垃圾

 【相关文章




版权声明:文章观点仅代表作者观点,作为参考,不代表本站观点。部分文章来源于网络,如果网站中图片和文字侵犯了您的版权,请联系我们及时删除处理!转载本站内容,请注明转载网址、作者和出处,避免无谓的侵权纠纷。