2009年5月5日星期二

PageRank Algorithm : 別說你懂PR演算法



在"Pagerank 演算法研究"曾經大致上說明了基本概念, 但是沒有提到一些實務的細節, 最近因為需要整理資料, 把國內外談到Pagerank 演算法的網頁都看了一下, 發現繁體內容少有對於PageRank正確的描述, 國外英文內容也幾乎一半以上都在胡扯, 也許你會說... 怎麼可能? 往下繼續看...看你是否真的懂PageRank?

先有幾個問題:

(1)如果有一個網頁A, 其PageRank等級為1, 具有100個對外連結, 當網頁B只有網頁A連入, 網頁A會如何貢獻PageRank給網頁B?
(2)如果有一個網頁A, 有1000個網頁連到網頁A, 這些連到網頁A的網頁, 每個都是PageRank等級1, 都具有100個對外連結, 請問網頁A的PageRank等級是多少?

如果你的答案是:

(1)PR(B)=(1-0.85)+0.85*(1/100)=0.15+0.0085=0.1585
(2)PR(A)=(1-0.85)+0.85*((1/100)*1000)=0.15+8.5=8.65

答案是這樣嗎? 如果你認為YES....那你還不太清楚PageRank演算法

從第一個答案還看不出怪異, 但從第二個答案, 應該就有人會覺得怪了....怪在哪裡?

具有1000個backlink, 且來源都是PageRank等級為1以上的網頁不稀奇, 怎麼可能就能把PR變成8???

如果今天如果有一個網頁A, 有10000個網頁連到網頁A, 這些連到網頁A的網頁, 每個都是PageRank等級1, 都具有100個對外連結, 請問網頁A的PageRank等級是多少?

結果變成 PR(A)=(1-0.85)+0.85*((1/100)*10000)=0.15+85=85.15

怎麼會是85?

你知不知道有多少網頁的外部連結可能到數十萬個, 如果這樣算的話,要到PR10太簡單了吧!(當然不會這樣)

也許有人會說, 那只是初始值, 還會經過迭代計算...然後收斂, 值會收斂下來

那麼我們來談談收斂, 什麼叫收斂? 就是經過多次計算後, 當數值呈現穩定不變, 就達收斂的狀態, 不管再經幾次迭代計算, 數值都不會再變

上面的式子根本就是固定值, 也就是不用迭代計算, 早就穩定不變

為什麼上面答案(1)(2)是錯誤的? 其中0.85目的何在? 為什麼會選擇0.85? 而不是0.8,也不是0.5?

許多SEO書籍對於這個問題大多避而不談, 因為實際上可能也不知道該怎麼談

問題出在哪裡呢? 我們後面再來解釋答案了!

相關訊息:
Pagerank 演算法研究
什麼是PageRank Hijack?
善用PageRank指標提升企業競爭力
Google Analytics & PageRank
SERP vs PageRank : PR值與搜尋排前的關係

標籤: ,

加入書籤 :

其他書籤 :

14 個意見:

2009年5月5日下午4:07 , Anonymous 匿名 提到...

有一個網站說

Q:PageRank的值是否會因為網頁外部連結而減少?
A:PageRank值漏的問題到目前還是有爭議的,有些專家相信PageRank值漏的事實,因為網頁會因連結而把PageRank轉移到另一網頁,因而造成網頁的PageRank輕微損失。就因為會有如此的結果,所以網頁要常增加新的連結,以維持現有PageRank值的水準。

而持另一種反向理論的專家相信,網頁如果沒有外部鏈結將損及網頁本身,他們相信Google會降低不連結網頁的PageRank值。同時他們也相信具有外部連結的網頁,終究會在大量連結的情況下,網頁的PageRank會得到應有的回饋。

這個說法正確嗎?

 
2009年5月5日下午5:05 , Anonymous 匿名 提到...

外部連結數目越多只是分散可以貢獻出去的pagerank
沒聽過"因為網頁會因連結而把PageRank轉移到另一網頁...因而造成網頁的PageRank輕微損失"
可能是措詞的問題吧

 
2009年5月5日下午8:22 , Anonymous tdchen 提到...

文章裡的1,2的答案應該對啊!
怎麼不對呢

 
2009年5月5日下午10:28 , Anonymous 匿名 提到...

問題就是=>太難了

 
2009年5月5日下午11:08 , Anonymous kimmy 提到...

pr在seo裡不是已經不太重要嗎?
所以不知道應該沒有關係吧!?
自我安慰中 :)

 
2009年5月6日上午7:14 , Anonymous 匿名 提到...

在這種 dangling link 的情況下,PageRank Vector R 求到最後會變成 0 向量,所以遇到這種情況的時候,就是先移除該 node, 才求所有 page 的 pagerank, 等到全部的 pagerank 有結果以後再把 node 加回去, 才不會造成太大的變化(e.g. 0)

 
2009年5月6日下午12:29 , Blogger admin 提到...

Google文件有說明
"Because dangling links do not affect the ranking of any other page directly, we simply remove them from the system until all the PageRanks are calculated. After all the PageRanks are calculated they can be added back in without affecting things significantly."

dangling links會先移除的原因是它"不會影響"其他page的迭代計算,先移除可以不需費時去算這些dangling link
整個都算完,dangling link才再加回來
跟zero vector好像沒關係

 
2009年5月6日下午5:21 , Anonymous 匿名 提到...

Section 2.7: dangling link 對 PR 計算會有很大的影響.

這個影響是可能會造成 PR 最後為 0.
而後的 model 加上一個 E(u) 只是為了讓 model 能夠不受這類的歧異影響.

只要要算的 PR 中含有 dangling node, 應該就是錯誤的結果.

在運算PR之前, 對每一個 dangling node, 就要先把連結到他的 link 拿掉. 直到算完才拿回來.

至於拿回來, 要以 0.15 算, 還是說要考慮其他 node 的影響. 或是乾脆等他不是 dangle 以後才算... 也許算是實作上的議題?

 
2009年5月6日下午5:23 , Anonymous 匿名 提到...

"只是為了讓 model 能夠不受這類的歧異影響."

表示數學式子能夠繼續運作...
不會因為 graph 裡有多個 components 而產生不一致的結果.

 
2009年5月6日下午10:52 , Anonymous 匿名 提到...

請參考
http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf

2.7 Dangling Links
One issue with this model is dangling links. Dangling links are simply links that point to any page
with no outgoing links. They a ect the model because it is not clear where their weight should
be distributed, and there are a large number of them. Often these dangling links are simply pages
that we have not downloaded yet, since it is hard to sample the entire web (in our 24 million pages
currently downloaded, we have 51 million URLs not downloaded yet, and hence dangling). Because
dangling links do not affect the ranking of any other page directly, we simply remove them from
the system until all the PageRanks are calculated. After all the PageRanks are calculated, they
can be added back in, without affecting things significantly. Notice the normalization of the other
links on the same page as a link which was removed will change slightly, but this should not have
a large effect.

"dangling link 對 PR 計算會有很大的影響.這個影響是可能會造成 PR 最後為 0"

這個來源是哪裡? 光看這段會斷章取義

"至於拿回來, 要以 0.15 算, 還是說要考慮其他 node 的影響..."

應不能以0.15計算

After the weights have converged, we add the dangling links back in and
recompute the rankings. Note after adding the dangling links back in, we need to iterate as many
times as was required to remove the dangling links. Otherwise, some of the dangling links will have
a zero weight. This whole process takes about five hours in the current implementation. With less
strict convergence criteria, and more optimization, the calculation could be much faster.

你的前後段來源在這裡...應該是會錯意吧
他是說如果沒有iterate夠的話, 會造成某些變零....也就是如果次數夠多,就沒有零的問題

 
2009年5月13日下午9:46 , Anonymous 匿名 提到...

我所謂 0 的意思是在於第一個算式,也就是最簡化(最根本,還沒有加上 E(u))的 pagerank。

在這個情況下碰到沒有 outgoing link 的 node 或者斷掉的 graph,整個 pagerank 向量最後會變成 0。造成數學上的歧異。

所以後來的式子才加上 E(u),也就是不要讓每一次的演算結果會是 0,這是一個數學上的妥協。就演算法原來的意思來看,只要出現 dangling 就會有錯誤。

所以如果以完整版的 pagerank (E(u)的),碰到 danling,不會出現 0,但卻會累積 pagerank。這是因為它的 E(u) 每次都貢獻 1 的權重。

把 dangling 拿掉,將它視為另外的部份去計算 PR,不管主圖迭代幾次,dangling的 PR都會一直是 PR = 0.15 * 1 + 0

 
2009年5月13日下午10:32 , Blogger admin 提到...

所以沒有rank sink問題的pagerank algorithm,也應該沒有dangling的問題

 
2009年5月14日上午12:34 , Anonymous wong 提到...

"最簡化的pagerank...造成數學上的歧異...." 這就是要修正演算法的目的啊!
把dangling拿掉後應該最後還要再拿回來,最後PR就不會是0.15

 
2009年6月23日上午12:25 , Anonymous KIKI流行著衣網 提到...

這個有點太困難了一些.................:(

 

張貼意見

<< 首頁