1. PageRank算法概述
???????? PageRank,即網頁排名，又稱網頁級別、Google左側排名或佩奇排名。
??????? 是Google創始人拉里·佩奇和謝爾蓋·布林于1997年構建早期的搜索系統原型時提出的鏈接分析算法，自從Google在商業上獲得空前的成功后，該算法也成為其他搜索引擎和學術界十分關注的計算模型。眼下許多重要的鏈接分析算法都是在PageRank算法基礎上衍生出來的。PageRank是Google用于用來標識網頁的等級/重要性的一種方法，是Google用來衡量一個站點的好壞的唯一標準。在揉合了諸如Title標識和Keywords標識等全部其他因素之后，Google通過PageRank來調整結果，使那些更具“等級/重要性”的網頁在搜索結果中另站點排名獲得提升，從而提高搜索結果的相關性和質量。其級別從0到10級，10級為滿分。PR值越高說明該網頁越受歡迎（越重要）。比如：一個PR值為1的站點表明這個站點不太具有流行度，而PR值為7到10則表明這個站點很受歡迎（或者說極其重要）。一般PR值達到4，就算是一個不錯的站點了。Google把自己的站點的PR值定到10，這說明Google這個站點是很受歡迎的，也能夠說這個站點很重要。
?
2. 從入鏈數量到 PageRank
??????? 在PageRank提出之前，已經有研究者提出利用網頁的入鏈數量來進行鏈接分析計算，這樣的入鏈方法如果一個網頁的入鏈越多，則該網頁越重要。早期的非常多搜索引擎也採納了入鏈數量作為鏈接分析方法，對于搜索引擎效果提升也有較明顯的效果。 PageRank除了考慮到入鏈數量的影響，還參考了網頁質量因素，兩者相結合獲得了更好的網頁重要性評價標準。
對于某個互聯網網頁A來說，該網頁PageRank的計算基于下面兩個基本如果：
????? 數量如果：在Web圖模型中，如果一個頁面節點接收到的其它網頁指向的入鏈數量越多，那么這個頁面越重要。
????? 質量如果：指向頁面A的入鏈質量不同，質量高的頁面會通過鏈接向其它頁面傳遞很多其它的權重。所以越是質量高的頁面指向頁面A，則頁面A越重要。
?????? 利用以上兩個如果，PageRank算法剛開始賦予每一個網頁同樣的重要性得分，通過迭代遞歸計算來更新每一個頁面節點的PageRank得分，直到得分穩定為止。 PageRank計算得出的結果是網頁的重要性評價，這和用戶輸入的查詢是沒有不論什么關系的，即算法是主題無關的。如果有一個搜索引擎，其相似度計算函數不考慮內容相似因素，全然採用PageRank來進行排序，那么這個搜索引擎的表現是什么樣子的呢？這個搜索引擎對于隨意不同的查詢請求，返回的結果都是同樣的，即返回PageRank值最高的頁面。
?
3. PageRank算法原理
???? ?PageRank的計算充分利用了兩個如果：數量如果和質量如果。過程例如以下：
????? 1）在初始階段：網頁通過鏈接關系構建起Web圖，每一個頁面設置同樣的PageRank值，通過若干輪的計算，會得到每一個頁面所獲得的終于PageRank值。隨著每一輪的計算進行，網頁當前的PageRank值會不斷得到更新。
????? 2）在一輪中更新頁面PageRank得分的計算方法：在一輪更新頁面PageRank得分的計算中，每一個頁面將其當前的PageRank值平均分配到本頁面包括的出鏈上，這樣每一個鏈接即獲得了對應的權值。而每一個頁面將全部指向本頁面的入鏈所傳入的權值求和，就可以得到新的PageRank得分。當每一個頁面都獲得了更新后的PageRank值，就完畢了一輪PageRank計算。?
?
3.2 基本思想：
?????? 假設網頁T存在一個指向網頁A的連接，則表明T的全部者覺得A比較重要，從而把T的一部分重要性得分賦予A。這個重要性得分值為：PR（T）/L(T)
??? 當中PR（T）為T的PageRank值，L(T)為T的出鏈數
??????? 則A的PageRank值為一系列類似于T的頁面重要性得分值的累加。
??????? 即一個頁面的得票數由全部鏈向它的頁面的重要性來決定，到一個頁面的超鏈接相當于對該頁投一票。一個頁面的PageRank是由全部鏈向它的頁面（鏈入頁面）的重要性經過遞歸算法得到的。一個有較多鏈入的頁面會有較高的等級，相反假設一個頁面沒有不論什么鏈入頁面，那么它沒有等級。
3.3 PageRank簡單計算：
?????? 如果一個由僅僅有4個頁面組成的集合：A，B，C和D。如果全部頁面都鏈向A，那么A的PR（PageRank）值將是B，C及D的和。
?????? 
?????? 繼續如果B也有鏈接到C，而且D也有鏈接到包含A的3個頁面。一個頁面不能投票2次。所以B給每一個頁面半票。以相同的邏輯，D投出的票僅僅有三分之中的一個算到了A的PageRank上。
?????? 
????? 換句話說，依據鏈出總數平分一個頁面的PR值。
?????? 
樣例：
??????? 如圖1 所看到的的樣例來說明PageRank的詳細計算過程。??
???????
????????????????????
???????
?
3.4? 修正PageRank計算公式：
?????????因為存在一些出鏈為0，也就是那些不鏈接不論什么其它網頁的網， 也稱為孤立網頁，使得非常多網頁能被訪問到。因此須要對 PageRank公式進行修正，即在簡單公式的基礎上添加了阻尼系數（damping factor）q， q一般取值q=0.85。
????? 其意義是，在隨意時刻，用戶到達某頁面后并繼續向后瀏覽的概率。?1- q= 0.15就是用戶停止點擊，隨機跳到新URL的概率）的算法被用到了全部頁面上，估算頁面可能被上網者放入書簽的概率。
????? 最后，即全部這些被換算為一個百分比再乘上一個系數q。因為以下的算法，沒有頁面的PageRank會是0。所以，Google通過數學系統給了每一個頁面一個最小值。
????? 
???? 這個公式就是.S Brin 和 L. Page 在《The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems 》定義的公式。
???? 所以一個頁面的PageRank是由其它頁面的PageRank計算得到。Google不斷的反復計算每一個頁面的PageRank。假設給每一個頁面一個隨機PageRank值（非0），那么經過不斷的反復計算，這些頁面的PR值會趨向于正常和穩定。這就是搜索引擎使用它的原因。
?
4. PageRank冪法計算(線性代數應用)
4.1 完整公式：
關于這節內容，能夠查閱：谷歌背后的數學
首先求完整的公式：
Arvind Arasu 在《Junghoo Cho Hector Garcia - Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》 更加準確的表達為：
?
是被研究的頁面，
是
鏈入頁面的數量，
是
鏈出頁面的數量，而N是全部頁面的數量。
PageRank值是一個特殊矩陣中的特征向量。這個特征向量為：
?
R是例如以下等式的一個解：
假設網頁i有指向網頁j的一個鏈接，則
否則
＝0。
4.2 使用冪法求PageRank
????? 那我們PageRank 公式能夠轉換為求解
的值，
????? 當中矩陣為 A =?q??× P + ( 1 一 q) *?
/N 。 P 為概率轉移矩陣，
為 n? 維的全 1 行.?則?=
????? 
???? 冪法計算步驟例如以下：
????? X? 設隨意一個初始向量,?即設置初始每一個網頁的?PageRank值均。一般為1.
???? R = AX;
???? while? (1 )(
??????????? if?( l?X -?R I? <??
) { //假設最后兩次的結果近似或者同樣，返回R
???? ???????????? return R;
????????? ?}??? else?? {
??????????????? X =R;
?????????????? R = AX;
???????? }
??? }
4.3 求解步驟：
一、 P概率轉移矩陣的計算過程:
??????? 先建立一個網頁間的鏈接關系的模型,即我們須要合適的數據結構表示頁面間的連接關系。
????? 1) 首先我們使用圖的形式來表述網頁之間關系：
?????? 如今如果僅僅有四張網頁集合：A、B、C，其抽象結構例如以下圖1：
??????? 
??????????????????????? ???????????? 圖1?網頁間的鏈接關系
????? 顯然這個圖是強連通的（從任一節點出發都能夠到達另外不論什么一個節點）。
????? 2）我們用矩陣表示連通圖：
?? ??? 用鄰接矩陣?P表示這個圖中頂點關系 ，假設頂（頁面）i向頂點（頁面）j有鏈接情況 ，則pij?? =?? 1 ，否則pij?? =?? 0 。如圖2所看到的。假設網頁文件總數為N?， 那么這個網頁鏈接矩陣就是一個N x N? 的矩 陣 。?
????? 3）網頁鏈接概率矩陣
???????然后將每一行除以該行非零數字之和，即（每行非0數之和就是鏈接網個數）則得到新矩陣P’，如圖3所看到的。 這個矩陣記錄了 每一個網頁跳轉到其它網頁的概率，即當中i行j列的值表示用戶從頁面i 轉到頁面j的概率。圖1 中A頁面鏈向B、C，所以一個用戶從A跳轉到B、C的概率各為1/2。
??????4）概率轉移矩陣P
?????? 採用P’ 的轉置矩?陣進行計算，?也就是上面提到的概率轉移矩陣P 。? 如圖4所看到的：
?????
??????
?
???????????????????????? 圖4? P’ 的轉置矩?陣
?
二、 A矩陣計算過程。
??????1）P概率轉移矩陣??:
?????? 
??????2）/N 為：
???? 
????? 3）A矩陣為：q??× P + ( 1 一 q) *? /N = 0.85? × P?+ 0.15??* /N
???? 
????? 初始每一個網頁的?PageRank值均為1 ， 即X~t = ( 1 ， 1 ， 1 ) 。?
三、?循環迭代計算PageRank的過程
?????? 第一步：
???????
????????? 由于X 與R的區別較大。 繼續迭代。
????????? 第二步：
?????????? 
?????? 繼續迭代這個過程...
??????直到最后兩次的結果近似或者同樣，即R終于收斂，R 約等于X，此時計算停止。終于的R 就是各個頁面的 PageRank 值。
用冪法計算PageRank 值總是收斂的，即計算的次數是有限的。
?
??????Larry Page和Sergey Brin 兩人從理論上證明了不論初始值怎樣選取，這樣的算法都保證了網頁排名的預計值能收斂到他們的真實值。
????? 因為互聯網上網頁的數量是巨大的，上面提到的二維矩陣從理論上講有網頁數目平方之多個元素。假設我們假定有十億個網頁，那么這個矩陣 就有一百億億個元素。這樣大的矩陣相乘，計算量是很大的。Larry Page和Sergey Brin兩人利用稀疏矩陣計算的技巧，大大的簡化了計算量。
?
5. PageRank算法優缺點
長處：
????????是一個與查詢無關的靜態算法，全部網頁的PageRank值通過離線計算獲得；有效降低在線查詢時的計算量，極大降低了查詢響應時間。
缺點：
?????? 1）人們的查詢具有主題特征，PageRank忽略了主題相關性，導致結果的相關性和主題性減少
??????? 2）舊的頁面等級會比新頁面高。由于即使是非常好的新頁面也不會有非常多上游鏈接，除非它是某個網站的子網站。
?
?
?參考文獻：
維基百科http://en.wikipedia.org/wiki/Page_rank
PageRank算法的分析及實現
《這就是搜索引擎:核心技術具體解釋》
?
?
)
)
