實(shí)際舉例
下面我們舉一個(gè)實(shí)際例子。如果不太明白以下例子在做什么的話，只要認(rèn)為我們能夠使用 Octave 這個(gè)程序來(lái)解特性值問(wèn)題即可。
首先，使用恰當(dāng)?shù)木庉嬈髦谱饕韵?Octave 腳本。(在行尾加上分號(hào)就能消去多余的結(jié)果輸出，不過(guò)，此次為了說(shuō)明特意去掉了。)
% cat pagerank.m
#!/usr/bin/octave
## pagerank.m - 計(jì)算 PageRank(TM) 用的簡(jiǎn)單的 GNU Octave 腳本
##設(shè)置計(jì)時(shí)器。
tic();
## 根據(jù)PageRank 的定義，將從文件 i 鏈接到文件 j 的鏈接狀態(tài)的推移概率行列定義為 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;
]
##計(jì)算 全部 M 的特性值和固有矢量列的組合。
[V，D]= eig(M)
## 保存與絕對(duì)價(jià)值最大的特性值對(duì)應(yīng)的固有矢量到EigenVector。
EigenVector = V(:, find(abs(diag(D))==max(abs(diag(D)))))
## PageRank 是將 EigenVector 在概率矢量上標(biāo)準(zhǔn)化后得到的值。
PageRank = EigenVector．/ norm(EigenVector,1)
## 輸出計(jì)算時(shí)間。
elapsed_time = toc()
(2003/7/23: 修正上述腳本的錯(cuò)誤。)
誤: EigenVector = V(:, find(max(abs(diag(D)))) )
正: EigenVector = V(:, find(abs(diag(D))== max(abs(diag(D)))))
用 Octave 運(yùn)行這個(gè) pagerank.m 腳本后在標(biāo)準(zhǔn)輸出中得到以下結(jié)果。
% 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 的輸出中，特性值被表示為對(duì)角行列 D 的對(duì)角成分，各個(gè)特性值相對(duì)應(yīng)的固有矢量被表示為行列 V 對(duì)應(yīng)列的列矢量。也就是說(shuō) M * V = D * M 成立。 如果包含復(fù)數(shù)特性值的話這里的特性值有7個(gè),其中絕對(duì)價(jià)值最大的特性值 λ 是λ=1。與之相對(duì)應(yīng)的固有矢量為實(shí)矢量：
EigenVector =
0.69946
0.38286
0.32396
0.24297
0.41231
0.10308
0.13989
即行列 V 的第1列。請(qǐng)注意，這個(gè)求得的固有矢量中概率矢量(要素的和等于1的 N 次元非負(fù)矢量)沒(méi)有被標(biāo)準(zhǔn)化，只是矢量的「大小」等于 1。 用算式來(lái)表達(dá)就是，Σpi ≠1 ，Σ(pi)2＝1。 在這里，對(duì)概率矢量進(jìn)行標(biāo)準(zhǔn)化
PageRank =
0.303514
0.166134
0.140575
0.105431
0.178914
0.044728
0.060703
PageRank 就是排位了。 注意，全部相加的和為 1。 計(jì)算只用了0.064秒。
求得的 PageRank 的評(píng)價(jià)
將 PageRank 的評(píng)價(jià)按順序排列 (PageRank 小數(shù)點(diǎn)3位四舍五入)。
名次 PageRank 文件ID 發(fā)出鏈接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
首先應(yīng)該關(guān)注的是，PageRank 的名次和反向鏈接的數(shù)目是基本一致的。無(wú)論鏈接多少正向鏈接都幾乎不會(huì)影響 PageRank，相反地有多少反向鏈接卻是從根本上決定 PageRank 的大小。但是，僅僅這些并不能說(shuō)明第1位和第2位之間的顯著差別(同樣地、第3位和第4位，第6位和第7位之間的差別)�？傊�，絕妙之處在于 PageRank 并不只是通過(guò)反向鏈接數(shù)來(lái)決定的。
讓我們?cè)敿?xì)地看一下。ID=1 的文件的 PageRank 是0.304，占據(jù)全體的三分之一，成為了第1位。特別需要說(shuō)明的是，起到相當(dāng)大效果的是從排在第3位的 ID=2 頁(yè)面中得到了所有的 PageRank(0.166)數(shù)。ID=2頁(yè)面有從3個(gè)地方過(guò)來(lái)的反向鏈接，而只有面向 ID=1頁(yè)面的一個(gè)鏈接，因此(面向ID=1頁(yè)面的)鏈接就得到了所有的 PageRank 數(shù)。不過(guò)，就因?yàn)?ID=1頁(yè)面是正向鏈接和反向鏈接最多的頁(yè)面，也可以理解它是最受歡迎的頁(yè)面吧。
反過(guò)來(lái)，最后一名的 ID=6 頁(yè)面只有 ID=1 的15％的微弱評(píng)價(jià),這可以理解為是因?yàn)闆](méi)有來(lái)自 PageRank 很高的 ID=1 的鏈接而使其有很大地影響。 總之，即使有同樣的反向鏈接的數(shù)目，鏈接源頁(yè)面評(píng)價(jià)的高低也影響 PageRank 的高低。
 |
| 表示頁(yè)面互相的鏈接關(guān)系的推移圖(加入了PageRank) |
實(shí)際地試著計(jì)算一下PageRank的收支。因?yàn)棣?1所以計(jì)算很簡(jiǎn)單，只要將自各頁(yè)的流入量單純相加即可。譬如 ID=1 的流入量為，
流入量＝(ID=2發(fā)出的Rank)+(ID=3發(fā)出的Rank)+(ID=5發(fā)出的Rank)+(ID=6發(fā)出的Rank)
= 0.166+0.141/2+0.179/4+0.045/2
= 0.30375
在誤差范圍內(nèi)PageRank的收支相符合。其他頁(yè)面ID的情況也一樣。以上的 PageRank 推移圖正表示了這個(gè)收支。沿著各自的鏈接發(fā)出的PageRank等于此頁(yè)面原有的PageRank除以發(fā)出鏈接數(shù)的值，而且和各自的頁(yè)面的PageRank收支相平衡。
不過(guò)，這樣絕妙均衡的本身，對(duì)理解線形代數(shù)的人來(lái)說(shuō)當(dāng)然不會(huì)是讓人驚訝的事情。因?yàn)檫@正是「特性值和固有矢量的性質(zhì)」，總之這樣被選的數(shù)值的組就是固有矢量。但即使是這樣，實(shí)際試著確認(rèn)一下的話，已經(jīng)能夠很好地使用PageRank的方法來(lái)考慮了。
以上就是 PageRank 的基本原理。 Google 做的就是大規(guī)模地處理這樣的非常特性值問(wèn)題。
粵公網(wǎng)安備 44010402000282號(hào)