首先申明，本博文自原創(chuàng)，部分?jǐn)?shù)據(jù)來源于網(wǎng)絡(luò)。

在google的 搜索結(jié)果中，PR值越 高的網(wǎng)頁排在越前面。

網(wǎng)頁權(quán)重的算法有很多種，為何我唯獨選擇了page rank來討論，不僅因為它是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......];

則，可以得出P^{T =} cMP^T，其中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;

]

所以，P^T為M的特征根為c的 特征向量。只需求出最大特征根的特征向量，就是網(wǎng)頁集對應(yīng)的最終PageRank值，這可以用迭代方法計算。如何迭代呢？如果 我們給定初始向量P^T1’做第一次迭代，就相當(dāng)于用初始向量乘以上面的矩陣。第二次迭代就相當(dāng)于用第一 迭代的結(jié)果再乘以上面的矩陣……實際上，在隨機(jī)過程的理論中，上述矩陣被稱為“轉(zhuǎn)移概率矩陣”。這種離散狀態(tài)按照離散時間的隨機(jī)轉(zhuǎn)移過程稱為馬爾可夫鏈(Markov chain)。設(shè)轉(zhuǎn)移概率矩陣為P，若存在正整數(shù)N，使得P_N>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的最后一行為全零，這樣，特征向量P^T也 為全零。我們也可以從圖論的角度來闡述這個問題。我們可以這樣定義一個有向圖：圖G的頂點集合為V={V1,V2,…,Vn}， 邊的集合為E={E_ij}。我們把有向圖G的每個頂點都給定一個權(quán)值P(Vi)， 即為它的PR值。有向邊AB的權(quán)值定義為A為B貢 獻(xiàn)的PageRank，也即網(wǎng)站A鏈接到網(wǎng)站B的概率。這樣，對于一個 頂點，若它的出度大于0，則從它出去的權(quán)值和為1（這一點可以從上述的方陣M中 的列可以看出，滿足了全概率）。顯然，如果圖中有一個頂點X的出度是0，那么經(jīng)過有限次迭代后所有 頂點的PR值都將變?yōu)?。這是因為由于X不對外貢獻(xiàn)任何PR， 所以整體的PR總和在不斷減少，最終減為0。這個被拉里•佩奇和謝爾蓋 •布林稱為rank sink。 為了克服這個問題，就有了下面這個公式：Rank算 法簡化版二：R(u) = （1-c）+ cR(1)/N(1) + ……+cR(v)/N(v)。(v∈Bu)。 ……公式二

(1-c)實際上為了服從概率分布。這樣可以推導(dǎo)出P = (1-c)e + cMP，即

P = [(1-c)ee^T/n + cM]P (e^TP=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ā)明人列于文件中。最后要說的一點，分析PR算法，用到了離散數(shù)學(xué)，線性 代數(shù)，概率論，數(shù)值計算甚至隨機(jī)過程，所以看來數(shù)學(xué)確實很好很強(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