首先申明，本博文自原創，部分數據來源于網絡。

在google的 搜索結果中，PR值越 高的網頁排在越前面。

網頁權重的算法有很多種，為何我唯獨選擇了page rank來討論，不僅因為它是Google搜索引擎采用的搜索結果排名算法之核心，且它把整 個互聯網當做一個整體來對待且最終依靠經典的數學模型精準地得到web上 網頁的權重。

雖然今天的搜索引擎的排名系統遠遠要比這個算法復雜。域名數據，內容質量，用戶數據，建站時間等都可能被考慮進去，但是page rank算法仍然是核心的技術之一，使得Google名聲大噪。關于page rank的介紹性文章，在Google黑板報里的” 談 Page Rank – Google 的民主表決式網頁排名技術”。關于其更詳細的論述，可以參照Google 的兩個創始人拉里•佩奇 （Larry Page ）和謝爾蓋•布林 (Sergey Brin)的論文 ” The PageRank Citation Ranking: Bringing Order to the Web ”。

首先，page rank基 于以下的假設：”一個 網頁被引用 (即反向 鏈接)的次數越多，則 說明越重要; 一個網 頁雖然沒有被多次引用，但是被重要的網頁引用，則它也可能是很重要的；一個網頁的重要性被平均的傳遞到它所引用的網頁。”所以，為了說明問題的方便，就引出了下面這個簡化了的Page Rank算法。簡化版一：R(u) = cR(1)/N(1) + ……+cR(v)/N(v)。(v∈Bu)。 其中R(v)是網頁v的PR值，N(v)是 網頁v的正向鏈接數，B(u)是頁面u的反向鏈接的集合。c是 阻尼系數(Damping Factor)，它的值在0到1之間。因 此，阻尼系數的使用，減少了其它頁面對當前頁面A的排序貢獻。那么這個式子如何用數學的方法解答呢？首先可以認為整個互聯網是 一個大的有向圖G=(V,E)。V是所有頁面的集合，E是有向邊的集 合，(i,j)表示頁i有指向頁j的超鏈接。由于有向圖和矩陣在本質上 是可以互相轉換的，下面舉例是如何互轉的：

此有向連通圖模擬網頁間的超鏈接

鏈接源I D 鏈接目標 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

如果我們假設Aij＝1 ,if (從頁面 i 向頁面 j 「有 」 鏈接的情況) ；Aij＝0, if (從頁面 i 向頁面 j 「沒有」鏈接的情況) 。 則根據以上我們可以構造如下矩陣

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的 特征向量。只需求出最大特征根的特征向量，就是網頁集對應的最終PageRank值，這可以用迭代方法計算。如何迭代呢？如果 我們給定初始向量P^T1’做第一次迭代，就相當于用初始向量乘以上面的矩陣。第二次迭代就相當于用第一 迭代的結果再乘以上面的矩陣……實際上，在隨機過程的理論中，上述矩陣被稱為“轉移概率矩陣”。這種離散狀態按照離散時間的隨機轉移過程稱為馬爾可夫鏈(Markov chain)。設轉移概率矩陣為P，若存在正整數N，使得P_N>0(每 一個元素大于0)，這種鏈被稱作正則鏈，它存在唯一的極限狀態概率，并且與初始狀態無關。這篇”Google搜索與Inter網中的數學”文章 里，描述了馬氏鏈與page rank的關系。

最后可以看到，從最開始的矩陣A到矩陣M可以 很容易轉化得到(將A倒置后將各個數值除以各自的非零要素)。

現在考慮有一個頁面（比如是頁面7），它不含有任何的超鏈接，即它的前向 鏈接或者說出度為0，很顯然，方陣M的最后一行為全零，這樣，特征向量P^T也 為全零。我們也可以從圖論的角度來闡述這個問題。我們可以這樣定義一個有向圖：圖G的頂點集合為V={V1,V2,…,Vn}， 邊的集合為E={E_ij}。我們把有向圖G的每個頂點都給定一個權值P(Vi)， 即為它的PR值。有向邊AB的權值定義為A為B貢 獻的PageRank，也即網站A鏈接到網站B的概率。這樣，對于一個 頂點，若它的出度大于0，則從它出去的權值和為1（這一點可以從上述的方陣M中 的列可以看出，滿足了全概率）。顯然，如果圖中有一個頂點X的出度是0，那么經過有限次迭代后所有 頂點的PR值都將變為0。這是因為由于X不對外貢獻任何PR， 所以整體的PR總和在不斷減少，最終減為0。這個被拉里•佩奇和謝爾蓋 •布林稱為rank sink。 為了克服這個問題，就有了下面這個公式：Rank算 法簡化版二：R(u) = （1-c）+ cR(1)/N(1) + ……+cR(v)/N(v)。(v∈Bu)。 ……公式二

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

P = [(1-c)ee^T/n + cM]P (e^TP=n)。關于用矩陣方法來推導的更詳細的文章，可以參考這篇 "The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google" .

   現在可以想象一下整個web中 有250億不止的網頁，收斂速度是至關重要的。所以為什么作者拉里•佩奇 （Larry Page ）和謝爾蓋•布林 (Sergey Brin)要取c為0.85,在這篇文章 ”How Google Finds Your Needle in the Web's Haystack ”的最后部分討論到。

Pagerank算法除了對搜索結果進行排序外，還可 以應用到其它方面，如估算網絡流量，向后鏈接的預測器，為用戶導航等。這篇文章 PageRank sculptin g.講述了當前Google的一些改進.

    后記，2001年9月，PageRank被 授予美國專利，專利被正式頒發給斯坦福大學，佩奇作為發明人列于文件中。最后要說的一點，分析PR算法，用到了離散數學，線性 代數，概率論，數值計算甚至隨機過程，所以看來數學確實很好很強大需要認真學習啊。

from:

http://hi.baidu.com/alphahunters/blog/item/e0e8a92d1b2820321f3089a0.html

http://blog.csdn.net/boyplayee/archive/2009/09/13/4548930.aspx