当前位置：首页>网站专题>网络营销
怎样求得 PageRank(3)
时间：2007年01月05日 内容来源： 互诺科技 浏览量：0

实际举例
下面我们举一个实际例子。如果不太明白以下例子在做什么的话，只要认为我们能够使用 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)

实际地试着计算一下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 做的就是大规模地处理这样的非常特性值问题。

返回列表