共計(jì) 3427 個(gè)字符，預(yù)計(jì)需要花費(fèi) 9 分鐘才能閱讀完成。

pagerank 算法怎么理解，相信很多沒有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個(gè)問題。

1. PageRank 算法概述

  PageRank, 即網(wǎng)頁(yè)排名，又稱網(wǎng)頁(yè)級(jí)別、Google 左側(cè)排名或佩奇排名。

  是 Google 創(chuàng)始人拉里 middot; 佩奇和謝爾蓋 middot; 布林于 1997 年構(gòu)建早期的搜索系統(tǒng)原型時(shí)提出的鏈接分析算法，自從 Google 在商業(yè)上獲得空前的成功后，該算法也成為其他搜索引擎和學(xué)術(shù)界十分關(guān)注的計(jì)算模型。目前很多重要的鏈接分析算法都是在 PageRank 算法基礎(chǔ)上衍生出來的。PageRank 是 Google 用于用來標(biāo)識(shí)網(wǎng)頁(yè)的等級(jí) / 重要性的一種方法，是 Google 用來衡量一個(gè)網(wǎng)站的好壞的唯一標(biāo)準(zhǔn)。在揉合了諸如 Title 標(biāo)識(shí)和 Keywords 標(biāo)識(shí)等所有其它因素之后，Google 通過 PageRank 來調(diào)整結(jié)果，使那些更具“等級(jí) / 重要性”的網(wǎng)頁(yè)在搜索結(jié)果中另網(wǎng)站排名獲得提升，從而提高搜索結(jié)果的相關(guān)性和質(zhì)量。其級(jí)別從 0 到 10 級(jí)，10 級(jí)為滿分。PR 值越高說明該網(wǎng)頁(yè)越受歡迎（越重要）。例如：一個(gè) PR 值為 1 的網(wǎng)站表明這個(gè)網(wǎng)站不太具有流行度，而 PR 值為 7 到 10 則表明這個(gè)網(wǎng)站非常受歡迎（或者說極其重要）。一般 PR 值達(dá)到 4，就算是一個(gè)不錯(cuò)的網(wǎng)站了。Google 把自己的網(wǎng)站的 PR 值定到 10，這說明 Google 這個(gè)網(wǎng)站是非常受歡迎的，也可以說這個(gè)網(wǎng)站非常重要。

2. 從入鏈數(shù)量到 PageRank

  在 PageRank 提出之前，已經(jīng)有研究者提出利用網(wǎng)頁(yè)的入鏈數(shù)量來進(jìn)行鏈接分析計(jì)算，這種入鏈方法假設(shè)一個(gè)網(wǎng)頁(yè)的入鏈越多，則該網(wǎng)頁(yè)越重要。早期的很多搜索引擎也采納了入鏈數(shù)量作為鏈接分析方法，對(duì)于搜索引擎效果提升也有較明顯的效果。PageRank 除了考慮到入鏈數(shù)量的影響，還參考了網(wǎng)頁(yè)質(zhì)量因素，兩者相結(jié)合獲得了更好的網(wǎng)頁(yè)重要性評(píng)價(jià)標(biāo)準(zhǔn)。
對(duì)于某個(gè)互聯(lián)網(wǎng)網(wǎng)頁(yè) A 來說，該網(wǎng)頁(yè) PageRank 的計(jì)算基于以下兩個(gè)基本假設(shè)：
?  數(shù)量假設(shè)：在 Web 圖模型中，如果一個(gè)頁(yè)面節(jié)點(diǎn)接收到的其他網(wǎng)頁(yè)指向的入鏈數(shù)量越多，那么這個(gè)頁(yè)面越重要。
?  質(zhì)量假設(shè)：指向頁(yè)面 A 的入鏈質(zhì)量不同，質(zhì)量高的頁(yè)面會(huì)通過鏈接向其他頁(yè)面?zhèn)鬟f更多的權(quán)重。所以越是質(zhì)量高的頁(yè)面指向頁(yè)面 A，則頁(yè)面 A 越重要。
  利用以上兩個(gè)假設(shè)，PageRank 算法剛開始賦予每個(gè)網(wǎng)頁(yè)相同的重要性得分，通過迭代遞歸計(jì)算來更新每個(gè)頁(yè)面節(jié)點(diǎn)的 PageRank 得分，直到得分穩(wěn)定為止。PageRank 計(jì)算得出的結(jié)果是網(wǎng)頁(yè)的重要性評(píng)價(jià)，這和用戶輸入的查詢是沒有任何關(guān)系的，即算法是主題無(wú)關(guān)的。假設(shè)有一個(gè)搜索引擎，其相似度計(jì)算函數(shù)不考慮內(nèi)容相似因素，完全采用 PageRank 來進(jìn)行排序，那么這個(gè)搜索引擎的表現(xiàn)是什么樣子的呢？這個(gè)搜索引擎對(duì)于任意不同的查詢請(qǐng)求，返回的結(jié)果都是相同的，即返回 PageRank 值最高的頁(yè)面。

3. PageRank 算法原理

   PageRank 的計(jì)算充分利用了兩個(gè)假設(shè)：數(shù)量假設(shè)和質(zhì)量假設(shè)。步驟如下：
  1）在初始階段：網(wǎng)頁(yè)通過鏈接關(guān)系構(gòu)建起 Web 圖，每個(gè)頁(yè)面設(shè)置相同的 PageRank 值，通過若干輪的計(jì)算，會(huì)得到每個(gè)頁(yè)面所獲得的最終 PageRank 值。隨著每一輪的計(jì)算進(jìn)行，網(wǎng)頁(yè)當(dāng)前的 PageRank 值會(huì)不斷得到更新。

  2）在一輪中更新頁(yè)面 PageRank 得分的計(jì)算方法：在一輪更新頁(yè)面 PageRank 得分的計(jì)算中，每個(gè)頁(yè)面將其當(dāng)前的 PageRank 值平均分配到本頁(yè)面包含的出鏈上，這樣每個(gè)鏈接即獲得了相應(yīng)的權(quán)值。而每個(gè)頁(yè)面將所有指向本頁(yè)面的入鏈所傳入的權(quán)值求和，即可得到新的 PageRank 得分。當(dāng)每個(gè)頁(yè)面都獲得了更新后的 PageRank 值，就完成了一輪 PageRank 計(jì)算。 

3.2 基本思想：

  如果網(wǎng)頁(yè) T 存在一個(gè)指向網(wǎng)頁(yè) A 的連接，則表明 T 的所有者認(rèn)為 A 比較重要，從而把 T 的一部分重要性得分賦予 A。這個(gè)重要性得分值為：PR（T）/L(T)

  其中 PR（T）為 T 的 PageRank 值，L(T) 為 T 的出鏈數(shù)

  則 A 的 PageRank 值為一系列類似于 T 的頁(yè)面重要性得分值的累加。

  即一個(gè)頁(yè)面的得票數(shù)由所有鏈向它的頁(yè)面的重要性來決定，到一個(gè)頁(yè)面的超鏈接相當(dāng)于對(duì)該頁(yè)投一票。一個(gè)頁(yè)面的 PageRank 是由所有鏈向它的頁(yè)面（鏈入頁(yè)面）的重要性經(jīng)過遞歸算法得到的。一個(gè)有較多鏈入的頁(yè)面會(huì)有較高的等級(jí)，相反如果一個(gè)頁(yè)面沒有任何鏈入頁(yè)面，那么它沒有等級(jí)。

3.3 PageRank 簡(jiǎn)單計(jì)算：

  假設(shè)一個(gè)由只有 4 個(gè)頁(yè)面組成的集合：A，B，C 和 D。如果所有頁(yè)面都鏈向 A，那么 A 的 PR（PageRank）值將是 B，C 及 D 的和。

  繼續(xù)假設(shè) B 也有鏈接到 C，并且 D 也有鏈接到包括 A 的 3 個(gè)頁(yè)面。一個(gè)頁(yè)面不能投票 2 次。所以 B 給每個(gè)頁(yè)面半票。以同樣的邏輯，D 投出的票只有三分之一算到了 A 的 PageRank 上。

例子：

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

  這個(gè)公式就是.S Brin 和 L. Page 在《The Anatomy of a Large- scale Hypertextual Web Search Engine Computer Networks and ISDN Systems》定義的公式。

  所以一個(gè)頁(yè)面的 PageRank 是由其他頁(yè)面的 PageRank 計(jì)算得到。Google 不斷的重復(fù)計(jì)算每個(gè)頁(yè)面的 PageRank。如果給每個(gè)頁(yè)面一個(gè)隨機(jī) PageRank 值（非 0），那么經(jīng)過不斷的重復(fù)計(jì)算，這些頁(yè)面的 PR 值會(huì)趨向于正常和穩(wěn)定。這就是搜索引擎使用它的原因。

4. PageRank 冪法計(jì)算 (線性代數(shù)應(yīng)用)

4.1 完整公式：

關(guān)于這節(jié)內(nèi)容，可以查閱：谷歌背后的數(shù)學(xué)

首先求完整的公式：

Arvind Arasu 在《Junghoo Cho Hector Garcia – Molina, Andreas Paepcke, Sriram Raghavan. Searching the Web》更加準(zhǔn)確的表達(dá)為：

  是被研究的頁(yè)面，鏈入頁(yè)面的數(shù)量，鏈出頁(yè)面的數(shù)量，而 N 是所有頁(yè)面的數(shù)量。

PageRank 值是一個(gè)特殊矩陣中的特征向量。這個(gè)特征向量為：

如果網(wǎng)頁(yè) i 有指向網(wǎng)頁(yè) j 的一個(gè)鏈接，則

=0。

4.2 使用冪法求 PageRank

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

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

    return R;

   }  else  {

  X =R;

  R = AX;

  }

  }

4.3 求解步驟：

一、P 概率轉(zhuǎn)移矩陣的計(jì)算過程:

  先建立一個(gè)網(wǎng)頁(yè)間的鏈接關(guān)系的模型, 即我們需要合適的數(shù)據(jù)結(jié)構(gòu)表示頁(yè)面間的連接關(guān)系。

  1) 首先我們使用圖的形式來表述網(wǎng)頁(yè)之間關(guān)系：

  現(xiàn)在假設(shè)只有四張網(wǎng)頁(yè)集合：A、B、C，其抽象結(jié)構(gòu)如下圖 1：

  圖 2   網(wǎng)頁(yè)鏈接矩陣：  圖 3   網(wǎng)頁(yè)鏈接概率矩陣： 

  圖 4   P’的轉(zhuǎn)置矩   陣

二、A 矩陣計(jì)算過程。

 1）P 概率轉(zhuǎn)移矩陣  :

  /N 為：

  /N = 0.85  times; P + 0.15 *

  初始每個(gè)網(wǎng)頁(yè)的  PageRank 值均為 1，即 X~t = (1，1，1)。 

三、  循環(huán)迭代計(jì)算 PageRank 的過程

  第一步：

  繼續(xù)迭代這個(gè)過程 …

  直到最后兩次的結(jié)果近似或者相同，即 R 最終收斂，R 約等于 X，此時(shí)計(jì)算停止。最終的 R 就是各個(gè)頁(yè)面的 PageRank 值。

用冪法計(jì)算 PageRank 值總是收斂的，即計(jì)算的次數(shù)是有限的。

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

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

5. PageRank 算法優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

  是一個(gè)與查詢無(wú)關(guān)的靜態(tài)算法，所有網(wǎng)頁(yè)的 PageRank 值通過離線計(jì)算獲得；有效減少在線查詢時(shí)的計(jì)算量，極大降低了查詢響應(yīng)時(shí)間。

缺點(diǎn)：

  1）人們的查詢具有主題特征，PageRank 忽略了主題相關(guān)性，導(dǎo)致結(jié)果的相關(guān)性和主題性降低

  2）舊的頁(yè)面等級(jí)會(huì)比新頁(yè)面高。因?yàn)榧词故欠浅：玫男马?yè)面也不會(huì)有很多上游鏈接，除非它是某個(gè)站點(diǎn)的子站點(diǎn)。

看完上述內(nèi)容，你們掌握 pagerank 算法怎么理解的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注丸趣 TV 行業(yè)資訊頻道，感謝各位的閱讀！