pagerank算法怎么理解

pagerank算法怎么理解，相信很多沒有經驗的人對此束手無策，為此本文總結了問題出現的原因和解決方法，通過這篇文章希望你能解決這個問題。

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上。

例子：

        如圖1 所示的例子來說明PageRank的具體計算過程。  

     這個公式就是.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值是一個特殊矩陣中的特征向量。這個特征向量為：

如果網頁i有指向網頁j的一個鏈接，則

＝0。

4.2 使用冪法求PageRank

      那我們PageRank 公式可以轉換為求解 /N 。 P 為概率轉移矩陣，=

      ) { //如果最后兩次的結果近似或者相同，返回R

                  return R;

           }    else   {

                X =R;

               R = AX;

         }

    }

4.3 求解步驟：

一、 P概率轉移矩陣的計算過程:

        先建立一個網頁間的鏈接關系的模型,即我們需要合適的數據結構表示頁面間的連接關系。

      1) 首先我們使用圖的形式來表述網頁之間關系：

       現在假設只有四張網頁集合：A、B、C，其抽象結構如下圖1：

         圖2  網頁鏈接矩陣：                                      圖3  網頁鏈接概率矩陣：  

                         圖4  P’ 的轉置矩 陣

二、 A矩陣計算過程。

      1）P概率轉移矩陣  :

       /N 為：

     /N = 0.85  × P + 0.15  *

      初始每個網頁的 PageRank值均為1 ， 即X~t = ( 1 ， 1 ， 1 ) 。 

三、 循環迭代計算PageRank的過程

       第一步：

       繼續迭代這個過程...

      直到最后兩次的結果近似或者相同，即R最終收斂，R 約等于X，此時計算停止。最終的R 就是各個頁面的 PageRank 值。

用冪法計算PageRank 值總是收斂的，即計算的次數是有限的。

      Larry Page和Sergey Brin 兩人從理論上證明了不論初始值如何選取，這種算法都保證了網頁排名的估計值能收斂到他們的真實值。

      由于互聯網上網頁的數量是巨大的，上面提到的二維矩陣從理論上講有網頁數目平方之多個元素。如果我們假定有十億個網頁，那么這個矩陣 就有一百億億個元素。這樣大的矩陣相乘，計算量是非常大的。Larry Page和Sergey Brin兩人利用稀疏矩陣計算的技巧，大大的簡化了計算量。

5. PageRank算法優缺點

優點：

        是一個與查詢無關的靜態算法，所有網頁的PageRank值通過離線計算獲得；有效減少在線查詢時的計算量，極大降低了查詢響應時間。

缺點：

       1）人們的查詢具有主題特征，PageRank忽略了主題相關性，導致結果的相關性和主題性降低

        2）舊的頁面等級會比新頁面高。因為即使是非常好的新頁面也不會有很多上游鏈接，除非它是某個站點的子站點。

看完上述內容，你們掌握pagerank算法怎么理解的方法了嗎？如果還想學到更多技能或想了解更多相關內容，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！