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值與搜尋排前的關係

1個留言

於 Pagerank 演算法研究.

敬請留言

你的回應對我們是很重要的. 你的電子郵件將不會被公開.

請等待 ...
*
Loading Facebook Comments ...