2008年8月25日星期一

Pagerank 演算法研究

Larry Page在1996年間發明了Pagerank的演算法, 爾後又與Sergey Brin在Stanford發表了"The Anatomy of a Large-Scale Hypertextual Web Search Engine", 這個Web Search Engine就是現在使用的Google, Pagerank詳內容到1998年才發表, 並且直到2001年才取得專利

Page Rank公式如下



(以上公式圖形由http://www.sitmo.com/latex/產生)

以上d指damping factor, 其值在0~1, 一般設為0.85
PR(Vi)為Vi這個頁面的PR值
In(Vi)為連進Vi這個頁面的link數目
Out(Vj)為Vj這個頁面連出去的link數目

也就是說如果有3個頁面A,B,C

A如果連到B,C
B如果連到C

如果A的PR=4
則PR(B)=(1-0.85) + 0.85 * 4/2 = 1.85

而PR(C)=(1-0.85) + 0.85 * (4/2 + 1.85) = 3.4225

B,C會平均繼承A的PR值, 但C會單獨繼承B的PR值

Pagerank是一種link-analysis algorithm, 是根據citation analysis而來, 原本使用在學術期刊論文被引用次數的技術

在Pagerank之後, 1999年Kleinberg發表了HITS algorithm(Hyperlink-Induced Topic Search), HITS決定兩個值: authority value & hub value, 並且是在query time計算, 而不是像Pagerank是在indexing time計算, Teoma是使用HITS (目前被Ask.com收購)

相對於link-analysis algorithm的content-analysis algorithm, 於另外文章再討論

不管是Pagerank或是HITS, 都是iterative ranking algorithm, 非常耗費演算時間及資源, 因此許多研究者提出了不同的方式來加速計算時間:

1999年 Efficient Computation of PageRank(Haveliwala and et al.)

2002年 Pagerank Computation and the Structure of the Web:Experiments and Algorithms(Arasu and et al.)

2002年 I/O Efficient Techniques for Computing PageRank(Chen and et al.)

2003年 Scaling Personalized Web Search(Jeh and et al.)

2003年 Exploiting the Block Structure of the Web for Computing PageRank (Kamvar and et al.)

2003年 Extrapolation Methods for Accelerating PageRank Computations (Kamvar and et al.)

2004年 Parallel PageRank computation on a gigabit PC cluster (Manaskasemsak and et al.)

2006年 Parallel adaptive technique for computing PageRank (Rungsawang and et al.)

2007年 Improvement of Pagerank for Focused Crawler (Yuan and et al.)

但是不管怎麼加速演算法, 其iterative ranking algorithm的特性不會改變, 但可能會加入content-analysis algorithm的一些特性來走向semantic web

而Pagerank公式內的Out(Vj), 使得一些做SEO的人注意到HTML中的nofollow特性, 來進行一些link quality的改善

深入探討:
PageRank Algorithm : 別說你懂PR演算法

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

標籤: , , , , ,

加入書籤 :

其他書籤 :

5 個意見:

2008年8月25日下午11:11 , Anonymous 匿名 提到...

在上面例子 如果c又link回到a
那pr(a)是否又要重算 導致pr(b) pr(c)都要重新算
那這樣會不會算得無法停止?

 
2008年8月26日上午9:07 , Anonymous admin 提到...

不會無法停止,當計算到收斂就可以停止
許多加速pr計算的修正版,都是提出可以快速收斂的演算法

關於Google自己談到這個收斂的特性
可以參考:

http://answers.google.com/answers/threadview/id/379557.html

 
2008年8月26日下午11:54 , Anonymous 匿名 提到...

thanks!!

 
2008年11月8日下午2:58 , Anonymous 匿名 提到...

非常好的參考資料
值得鼓勵

 
2009年6月2日上午1:16 , Anonymous 匿名 提到...

這些參考資料真省了我好多多的時間
謝謝了呀!

 

張貼意見

<< 首頁