pageRank詳細(xì)解析(具體例子)

1、PageRank解釋方法1. PageRank 的核心思想(1) R(x)表示 x 的 PageRank，B(x)表示所有指向 x 的網(wǎng)頁。公式 (1)的意思是一個網(wǎng)頁的重要性等于指向它的所有網(wǎng)頁的重要性相加之和。粗看之下，公式(1)將核心思想準(zhǔn)確地表達(dá)出來了。但仔細(xì)觀察就會發(fā)現(xiàn)，公式(1)有一個缺陷：無論 J 有多少個超鏈接，只要 J指向 I，I 都將得到與 J一樣的重要性。當(dāng) J有多個超鏈接時，這個思想就會造 成不合理的情況。例如：一個新開的網(wǎng)站 N 只有兩個指向它的超鏈接，一個來自著名并且歷史 悠久的門戶網(wǎng)站 F，另一個來自不為人知的網(wǎng)站U。根據(jù)公式 (1)，就會得到 N 比 F 更優(yōu)質(zhì)

2、的結(jié)論。這個結(jié)論顯然不符合人們的常識。彌補這個缺陷的一個簡單方法是當(dāng) J 有多個超鏈接(假設(shè)個數(shù)為 N)，每個鏈接得到的重要性為 R(j)/N 。于是公式 (1)就變成公式( 2)：2) N(j) 表示 j 頁面的超鏈接數(shù)從圖 2可以看出，如果要得到 N 比 F更優(yōu)質(zhì)的結(jié)論，就要求 N 得到很多重要網(wǎng)站的超鏈接或者海量不知名網(wǎng)站的超鏈接。而這是可接受的。因此可以認(rèn)為公式(2)將核心思想準(zhǔn)確地表達(dá)出來了。為了得到標(biāo)準(zhǔn)化的計算結(jié)果，在公式(2)的基礎(chǔ)上增加一個常數(shù) C，得到公式 (3) ：(3)2. 計算，實例由公式 (3)可知， PageRank 是遞歸定義的。換句話就是要得到一個頁面的Page

3、Rank，就要先知道另一些頁面的 PageRank。因此需要設(shè)置合理的 PageRank 初始值。不過，如果有辦法得到合理的 PageRank初始值，還需要這個算法嗎或者說，這個嚴(yán)重依賴于初始值的算法有什么意義嗎 依賴于合理初始值的 PageRank 算法是沒意義的， 那么不依賴于初始值的 PageRank 算法就是有意 義的了。也就是說，如果存在一種計算方法， 使得無論怎樣設(shè)置初始值， 最后都會收斂到同一個 值就行了。要做到這樣，就要換一個角度看問題，從線性代數(shù)的角度看問題。將頁面看作節(jié)點，超鏈接看作有向邊，整個互聯(lián)網(wǎng)就變成一個有向圖了。此時，用鄰接矩陣 M 表示整個互聯(lián)網(wǎng)，若第 I 個頁面

4、有存在到第 J 個頁面的超鏈接，那么矩陣元素 mij=1 ，否則 mij=0 。對于圖 3 有矩形 M= 0, 1, 1, 0,0, 0, 0, 1,1, 0, 0, 0,1, 1, 1, 0圖3觀察矩陣 M 可發(fā)現(xiàn)， M 的第 I行表示第 I個網(wǎng)頁指向的網(wǎng)頁， M 的第 J列表示指向 J的網(wǎng)頁。如 果將 M 的每個元素都除于所在行的全部元素之和，然后再將 M 轉(zhuǎn)置(交換行和列)，得到 MT。 MT的每一行的全部元素之和不就正好是公式(3)中的 嗎例如圖 3 可以得到這樣的矩陣：MT= 0, 0, 1, 1/3,1/2, 0, 0, 1/3,1/2, 0, 0, 1/3,0, 1, 0, 0

5、將 R 看作是一個 N 行 1 列的矩陣，公式 (3) 變?yōu)楣? 4)R = C MT R(4)在公式 (4)中， R可以看作 M T的特征向量，其對應(yīng)的特征值為1 / C(看不明白這句話，可以回憶下線性代數(shù)中對特征向量的定義 對于矩陣 A，若存在著列向量 X 和一個數(shù) c，使得 AX=cX， 則 X 稱為 A 的特征向量， c 稱為 A 的特征值)。冪法 (power method )計算主特征向量與初始值 無關(guān)，因此只要把 R 看作主特征向量計算，就可以解決初始值的合理設(shè)置問題。冪法得到的結(jié)果與初始值無關(guān)， 是因為最終都會收斂到某個值。 因此使用冪法之前， 要確保能夠 收斂。但是，在互聯(lián)

6、網(wǎng)的超鏈接結(jié)構(gòu)中，一旦出現(xiàn)封閉的情況，就會使得冪法不能收斂。所謂的 封閉是指若干個網(wǎng)頁互相指向?qū)Ψ?，但不指向別的網(wǎng)頁，具體的例子如圖 4 所示：圖 4 來自 Soumya Sanyal 的 PPT上圖 4 個綠色網(wǎng)頁就是封閉情況。這種情況會使得這些網(wǎng)頁的 PageRank 在計算的時候不斷地累 加，從而使得結(jié)果不能收斂。仔細(xì)研究就會發(fā)現(xiàn)紅色網(wǎng)頁的 PageRank 給了綠色網(wǎng)頁后，綠色網(wǎng) 頁就將這些 PageRank 吞掉了。 Larry Page 將這種情況稱為 Rank Sink。如果沿著網(wǎng)頁的鏈接一直點下去， 發(fā)現(xiàn)老是在同樣的幾個網(wǎng)頁中徘徊， 怎么辦沒錯， 把當(dāng)前頁面 關(guān)掉，再開一個新的

7、網(wǎng)頁。上述情況正好與Rank Sink 類似，也就意味著可以借鑒這個思想解決Rank Sink。因此，在公式 (3)中的基礎(chǔ)上加一個逃脫因子E，得到：(5)E(i)表示第 i 個網(wǎng)頁的逃脫因子將(5)變成矩陣形式，可得：R = C MT R + CE = C( MT R + E )其中列向量 R的 1范數(shù)(即 R的全部矩陣元素相加 )為 1將上式重寫為R = C( MT + E * 1 ) R (6)1 是指一行 N 列的行向量，且每個元素都是 1在公式 (6)中，只要將 R看作 (MT + E * 1)的特征向量， 就可以同時解決初始值設(shè)置問題和封閉的 情況。3. 資料共享找資料是簡單的事，

8、 但要找到好資料就不那么容易了。 因此， 這一小節(jié)是分享我找到的一些比 較好的資料。1. PageRank 之父的文章 : The PageRank Citation Ranking Bringing Order to the Web一個對 PageRank進(jìn)行解釋的 PPT，講解得很好 : The PageRank Citation Ranking Redone不錯的 PageRank科普文 : Google 的秘密 - PageRank 徹底解說 中文版本文所用到的線性代數(shù)相關(guān)知識1 基本思想：如果網(wǎng)頁 T存在一個指向網(wǎng)頁 A 的連接，則表明 T的所有者認(rèn)為 A比較重要，從而把 T 的一部

9、分重要性得分賦予 A。這個重要性得分值為： PR（T） /L（T）其中 PR（T）為 T的 PageRank值， L（T）為T的出鏈數(shù)則A的 PageRank值為一系列類似于 T的頁面重要性得分值的累加。即一個頁面的 得票數(shù) 由所有鏈向它的頁面的重要性來決定， 到一個頁面的超鏈接相當(dāng)于 對該頁投一票。一個頁面的 PageRank是由所有鏈向它的頁面 （鏈入頁面） 的重要性經(jīng)過遞 歸算法得到的。 一個有較多鏈入的頁面會有較高的等級， 相反如果一個頁面沒有任何鏈入頁 面，那么它沒有等級。2 PageRank 簡單計算：假設(shè)一個由只有 4 個頁面組成的集合： A， B，C 和 D。如果所有頁面都鏈向

10、 A，那么 A的 PR（PageRank）值將是 B，C及 D 的和。繼續(xù)假設(shè) B也有鏈接到 C，并且 D也有鏈接到包括 A的 3個頁面。一個頁面不能投票 2 次。所以 B給每個頁面半票。 以同樣的邏輯， D投出的票只有三分之一算到了 A的 PageRan 上。換句話說，根據(jù)鏈出總數(shù)平分一個頁面的 PR 值。例子：如圖 1 所示的例子來說明 PageRank的具體計算過程。3 修正 PageRank 計算公式：由于存在一些出鏈為 0，也就是那些不鏈接任何其他網(wǎng)頁的網(wǎng)，也稱為孤立網(wǎng)頁，使得很多網(wǎng)頁能被訪問到。因此需要對 PageRank 公式進(jìn)行修正，即在簡單公式的基礎(chǔ)上增加 了阻尼系數(shù)( da

11、mping factor ) q， q 一般取值 q=。其意義是，在任意時刻，用戶到達(dá)某頁面后并繼續(xù)向后瀏覽的概率。 1- q= 就是用戶停 止點擊，隨機跳到新 URL 的概率)的算法被用到了所有頁面上，估算頁面可能被上網(wǎng)者放 入書簽的概率。最后，即所有這些被換算為一個百分比再乘上一個系數(shù)q。由于下面的算法，沒有頁面的 PageRank 會是 0 。所以， Google 通過數(shù)學(xué)系統(tǒng)給了每個頁面一個最小值。這個公式就是 .S Brin 和 L. Page 在 The Anatomy of a Large- scale Hypertextual Web Search Engine Compute

12、r Networks and ISDN Systems 定義的公式。所以一個頁面的 PageRank是由其他頁面的 PageRank 計算得到。 Google 不斷的重復(fù)計算 每個頁面的 PageRank。如果給每個頁面一個隨機 PageRank 值（非 0），那么經(jīng)過不斷的重 復(fù)計算，這些頁面的 PR值會趨向于正常和穩(wěn)定。這就是搜索引擎使用它的原因。4. PageRank 冪法計算 （線性代數(shù)應(yīng)用 ）完整公式：關(guān)于這節(jié)內(nèi)容，可以查閱： 谷歌背后的數(shù)學(xué)首先求完整的公式：Arvind Arasu 在 Junghoo Cho Hector Garcia - Molina, Andreas Paep

13、cke, Sriram Raghavan. Searching the Web 更加準(zhǔn)確的表達(dá)為：是被研究的頁面， 是 鏈入頁面的數(shù)量， 是 鏈出頁面的 數(shù)量，而 N 是所有頁面的數(shù)量。PageRank 值是一個特殊矩陣中的特征向量。這個特征向量為：為 n 維的全 11.R 是如下等式的一個解：如果網(wǎng)頁i 有指向網(wǎng)頁 j 的一個鏈接，則否則 0。使用冪法求 PageRank那我們 PageRank 公式可以轉(zhuǎn)換為求解 的值，其中矩陣為 A = q × P +一 ( 1 q) */N 。 P 為概率轉(zhuǎn)移矩陣，行. 則=冪法計算過程如下：X 設(shè)任意一個初始向量 , 即設(shè)置初始每個網(wǎng)頁的

14、PageRank 值均。一般為R = AX;while (1 )(if ( l X -R I <)直到最后兩次的結(jié)果近似或者相同，即R 最終收斂， R 約等于 X，此時計算停止。最終的 R 就是各個頁面的 PageRank 值。用冪法計算 PageRank 值總是收斂的，即計算的次數(shù)是有限的。Larry Page 和 Sergey Brin 兩人從理論上證明了不論初始值如何選取，這種算法都保證了 網(wǎng)頁排名的估計值能收斂到他們的真實值。由于互聯(lián)網(wǎng)上網(wǎng)頁的數(shù)量是巨大的，上面提到的二維矩陣從理論上講有網(wǎng)頁數(shù)目平方之 多個元素。如果我們假定有十億個網(wǎng)頁，那么這個矩陣 就有一百億億個元素。這樣大的矩 陣相乘，計算量是非常大的。 Larry Page和 Ser