首先申明，本博文自原創(chuàng)，部分?jǐn)?shù)據(jù)來源于網(wǎng)絡(luò)。
在google的
搜索結(jié)果中，PR值越
高的網(wǎng)頁排在越前面。
網(wǎng)頁權(quán)重的算法有很多種，為何我唯獨(dú)選擇了page rank來討論，不僅因?yàn)樗?font face="Times New Roman">Google搜索引擎采用的搜索結(jié)果排名算法之核心，且它把整
個互聯(lián)網(wǎng)當(dāng)做一個整體來對待且最終依靠經(jīng)典的數(shù)學(xué)模型精準(zhǔn)地得到web上
網(wǎng)頁的權(quán)重。
雖然今天的搜索引擎的排名系統(tǒng)遠(yuǎn)遠(yuǎn)要比這個算法復(fù)雜。域名數(shù)據(jù)，內(nèi)容質(zhì)量，用戶數(shù)據(jù)，建站時間等都可能被考慮進(jìn)去，但是page rank算法仍然是核心的技術(shù)之一，使得Google名聲大噪。關(guān)于page rank的介紹性文章，在Google黑板報里的” 談 Page Rank – Google 的民主表決式網(wǎng)頁排名技術(shù)”。關(guān)于其更詳細(xì)的論述，可以參照Google 的兩個創(chuàng)始人拉里•佩奇 （Larry Page ）和謝爾蓋•布林 (Sergey Brin)的論文 ” The PageRank Citation Ranking: Bringing Order
to the Web ”。
首先，page rank基
于以下的假設(shè)：”一個
網(wǎng)頁被引用 (即反向
鏈接)的次數(shù)越多，則
說明越重要; 一個網(wǎng)
頁雖然沒有被多次引用，但是被重要的網(wǎng)頁引用，則它也可能是很重要的；一個網(wǎng)頁的重要性被平均的傳遞到它所引用的網(wǎng)頁。”所以，為了說明問題的方便，就引出了下面這個簡化了的Page Rank算法。簡化版一：R(u) = cR(1)/N(1) + ……+cR(v)/N(v)。(v∈Bu)。
其中R(v)是網(wǎng)頁v的PR值，N(v)是
網(wǎng)頁v的正向鏈接數(shù)，B(u)是頁面u的反向鏈接的集合。c是
阻尼系數(shù)(Damping Factor)，它的值在0到1之間。因
此，阻尼系數(shù)的使用，減少了其它頁面對當(dāng)前頁面A的排序貢獻(xiàn)。那么這個式子如何用數(shù)學(xué)的方法解答呢？首先可以認(rèn)為整個互聯(lián)網(wǎng)是
一個大的有向圖G=(V,E)。V是所有頁面的集合，E是有向邊的集
合，(i,j)表示頁i有指向頁j的超鏈接。由于有向圖和矩陣在本質(zhì)上
是可以互相轉(zhuǎn)換的，下面舉例是如何互轉(zhuǎn)的：
此有向連通圖模擬網(wǎng)頁間的超鏈接
鏈接源I D 鏈接目標(biāo) ID
1
2,3 ,4,5, 7
2
1
3
1,2
4
2,3,5
5 1,3,4,6
6
1,5
7
5
如果我們假設(shè)Aij＝1 ,if (從頁面
i 向頁面 j 「有 」 鏈接的情況) ；Aij＝0,
if (從頁面 i 向頁面 j 「沒有」鏈接的情況) 。
則根據(jù)以上我們可以構(gòu)造如下矩陣
A = [
0, 1, 1, 1, 1, 0, 1;
1, 0, 0, 0, 0, 0, 0;
1, 1, 0, 0, 0, 0, 0;
0, 1, 1, 0, 1, 0, 0;
1, 0, 1, 1, 0, 1, 0;
1, 0, 0, 0, 1, 0, 0;
0, 0, 0, 0, 1, 0, 0;
]
接下來再來看看公式一中的PR值求法，即
PR(1) = c[1*PR(2) + (1/2)*PR(3) + (1/4)*PR(5) +(1/2)*PR(6)];
PR(2) = c[(1/5)*PR(1) + (1/2)*PR(3) + 0.25*PR(5) + 0.5*PR(5)];
............
PR(7) = c[(1/5)*PR(1) + 0+ 0......];
則，可以得出PT = cMPT，其中M的方陣如下，
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;
]
所以，PT為M的特征根為c的
特征向量。只需求出最大特征根的特征向量，就是網(wǎng)頁集對應(yīng)的最終PageRank值，這可以用迭代方法計算。如何迭代呢？如果
我們給定初始向量PT1’做第一次迭代，就相當(dāng)于用初始向量乘以上面的矩陣。第二次迭代就相當(dāng)于用第一
迭代的結(jié)果再乘以上面的矩陣……實(shí)際上，在隨機(jī)過程的理論中，上述矩陣被稱為“轉(zhuǎn)移概率矩陣”。這種離散狀態(tài)按照離散時間的隨機(jī)轉(zhuǎn)移過程稱為馬爾可夫鏈(Markov
chain)。設(shè)轉(zhuǎn)移概率矩陣為P，若存在正整數(shù)N，使得PN>0(每
一個元素大于0)，這種鏈被稱作正則鏈，它存在唯一的極限狀態(tài)概率，并且與初始狀態(tài)無關(guān)。這篇”Google搜索與Inter網(wǎng)中的數(shù)學(xué)”文章
里，描述了馬氏鏈與page rank的關(guān)系。
最后可以看到，從最開始的矩陣A到矩陣M可以
很容易轉(zhuǎn)化得到(將A倒置后將各個數(shù)值除以各自的非零要素)。
現(xiàn)在考慮有一個頁面（比如是頁面7），它不含有任何的超鏈接，即它的前向
鏈接或者說出度為0，很顯然，方陣M的最后一行為全零，這樣，特征向量PT也
為全零。我們也可以從圖論的角度來闡述這個問題。我們可以這樣定義一個有向圖：圖G的頂點(diǎn)集合為V={V1,V2,…,Vn}，
邊的集合為E={Eij}。我們把有向圖G的每個頂點(diǎn)都給定一個權(quán)值P(Vi)，
即為它的PR值。有向邊AB的權(quán)值定義為A為B貢
獻(xiàn)的PageRank，也即網(wǎng)站A鏈接到網(wǎng)站B的概率。這樣，對于一個
頂點(diǎn)，若它的出度大于0，則從它出去的權(quán)值和為1（這一點(diǎn)可以從上述的方陣M中
的列可以看出，滿足了全概率）。顯然，如果圖中有一個頂點(diǎn)X的出度是0，那么經(jīng)過有限次迭代后所有
頂點(diǎn)的PR值都將變?yōu)?。這是因?yàn)橛捎赬不對外貢獻(xiàn)任何PR，
所以整體的PR總和在不斷減少，最終減為0。這個被拉里•佩奇和謝爾蓋
•布林稱為rank sink。
為了克服這個問題，就有了下面這個公式：Rank算
法簡化版二：R(u)
= （1-c）+
cR(1)/N(1) + ……+cR(v)/N(v)。(v∈Bu)。 ……公式二
(1-c)實(shí)際上為了服從概率分布。這樣可以推導(dǎo)出P = (1-c)e +
cMP，即
P = [(1-c)eeT/n + cM]P (eTP=n)。關(guān)于用矩陣方法來推導(dǎo)的更詳細(xì)的文章，可以參考這篇 "The
$25,000,000,000 Eigenvector: The Linear Algebra Behind Google" .
現(xiàn)在可以想象一下整個web中
有250億不止的網(wǎng)頁，收斂速度是至關(guān)重要的。所以為什么作者拉里•佩奇 （Larry Page ）和謝爾蓋•布林 (Sergey Brin)要取c為0.85,在這篇文章 ”How Google Finds Your
Needle in the Web's Haystack ”的最后部分討論到。
Pagerank算法除了對搜索結(jié)果進(jìn)行排序外，還可
以應(yīng)用到其它方面，如估算網(wǎng)絡(luò)流量，向后鏈接的預(yù)測器，為用戶導(dǎo)航等。這篇文章 PageRank sculptin g.講述了當(dāng)前Google的一些改進(jìn).
后記，2001年9月，PageRank被
授予美國專利，專利被正式頒發(fā)給斯坦福大學(xué)，佩奇作為發(fā)明人列于文件中。最后要說的一點(diǎn)，分析PR算法，用到了離散數(shù)學(xué)，線性
代數(shù)，概率論，數(shù)值計算甚至隨機(jī)過程，所以看來數(shù)學(xué)確實(shí)很好很強(qiáng)大需要認(rèn)真學(xué)習(xí)啊。
from:
http://hi.baidu.com/alphahunters/blog/item/e0e8a92d1b2820321f3089a0.html
http://blog.csdn.net/boyplayee/archive/2009/09/13/4548930.aspx
posted on 2010-04-05 17:15
chatler 閱讀(719)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm