DIV CSS 佈局教程網

PageRank算法詳解:谷歌曾經獨步天下的「倚天劍」
編輯:谷歌搜索算法     

PageRank算法

PageRank算法堪稱谷歌曾經獨步天下的「倚天劍」。它由Larry Page與Sergey Brin在斯坦福大學攻讀研究生期間共同發明,相關論文可查閱:The PageRank Citation Ranking: Bringing Order to the Web。

本文首先透過一些參考文獻引出問題,隨後給出PageRank的幾種實現算法,最後將其推廣至如何在MapReduce框架下實現PageRank算法。

PageRank的核心思想有兩點:

1. 如果一個網頁被眾多其他網頁鏈接到,說明這個網頁比較重要,其PageRank值也會相對較高;

2. 如果一個PageRank值很高的網頁鏈接到另一個網頁,那麼被鏈接網頁的PageRank值也會相應地因此提高。

下面這張來自WikiPedia的圖,每個球代表一個網頁,球的大小反映網頁PageRank值的高低。指向網頁B和網頁E的鏈接很多,所以B和E的PageRank值較高;此外,雖然很少有網頁指向C,但最重要的網頁B指向了C,所以C的PageRank值甚至比E還要大。

參考內容:

1. Wiki about PageRank

2. Google 的秘密 - PageRank 徹底解說 中文版

3. 數值分析與算法 Page 161 應用實例:Google的PageRank算法

4. Numeric Methods with Matlab 或者中文翻譯版本 Matlab數值計算

5. 使用 MapReduce 思想計算 PageRank Page 62 PageRank和馬爾可夫鏈


  1. 問題背景

來自參考內容3


2. 數學建模

來自參考內容3,理解網頁連接矩陣$G$、馬爾科夫過程(「網上沖浪」)、轉移矩陣$A$,以及概率$p$——即用戶點擊當前網頁中某個鏈接地址的概率(一般取0.85)。

最終得到一個等式$Ax=x$,這實際上就是求矩陣$A$特徵值為1的特徵向量!

下面的內容用圓盤定理解釋了1是矩陣$A$的主特徵值,因此我們可以使用冪法來求解。

關於冪法的詳細介紹,可參考另一篇文章《Numerical Methods Using Matlab: 第三章 矩陣特徵值和奇異值求解》。

3. 求解PageRank

假設有如上圖右側所示的網頁鏈接模型。

(1) 冪法

wiki上有一個PageRank的簡便算法,它不考慮轉移概率,而是採用迭代的方式,每次更新所有網頁的PageRank值——更新方式就是將每個網頁的PageRank值平攤給它指向的所有網頁,每個網頁累計所有指向它的網頁平攤給它的值,作為它該回合的PageRank值,直到所有網頁的PageRank值收斂,或滿足一定的閾值條件時停止。後面MapReduce框架下PageRank算法的實現,正是採用了這一思想。考慮轉移概率的情況與之類似,只需乘上轉移概率,再加上隨機跳轉的概率即可。

根據上面的思想,下面用Matlab代碼實現,即可得到各個網頁的PageRank值。

得到的向量$x$保存了各個網頁的PageRank值。雖然鏈接數目相同,但網頁①比網頁④和網頁⑤都高,而網頁②的PageRank值位列第二,因為網頁①鏈接到了它上面,相當於沾了網頁①的光。

這篇文章還給出了該算法的一個Python版本實現,作者使用第三方模塊python-graph。python-graph模塊實現了很多圖算法,使用前需先安裝,代碼如下:

Python版本的算法實現:

經過32次迭代之後得到的結果如下,與前面的結果一致:

(2) 利用馬爾可夫矩陣的特殊結構

來自參考內容4,其中$delta=frac{1-p}{n}$

也就是將矩陣$A$進行分解,並不需要顯式求出矩陣$A$,隨後便是求解一個線性方程組即可。

(3) 巧妙解法:逆迭代算法

巧妙利用Matlab中的精度誤差,導致原本是一個奇異矩陣的$I-A$變成非奇異矩陣,運行時只會有些警告提示,但運行結果與其他算法一致。

最後,附上參考內容4中給出的一份優質代碼,用於模擬隨機沖浪生成矩陣$G$:


4. MapReduce框架下PageRank算法的實現

利用前面wiki上迭代(或冪法)的思想來實現MapReduce框架下的PageRank算法十分簡單,可以先閱讀參考內容5。

這篇文章《using-mapreduce-to-compute-pagerank》更加詳細,可供參考。

以下是我在大數據課程中的一次作業,要求參考wiki上的簡便算法,實現MapReduce框架下的PageRank算法。給定的數據集是Twitter用戶之間的關係,可視作網頁之間的關係,但助教並未要求寫代碼並運行該數據集(有1G多),所以下面只是一個Python版本的理想可行版本,並未經過實際大數據集的驗證;另外,我當時還不太熟悉Python的mapreduce框架中的一些函數,所以實現的是一個簡明、可測試的PageRank算法。

1. 輸入輸出格式

map函數的輸入是〈節點,從該節點引出的邊列表〉,其中節點是一個類,包含其當前的PageRank值;輸出是〈節點,反向節點PageRank值/反向節點引出邊的總數〉;

reduce函數的輸入是〈節點,反向節點PageRank值/反向節點引出邊的總數〉,輸出是〈節點,從該節點引出的邊列表〉,其中節點包含其更新後的PageRank值。

偽代碼:(一時犯二寫了個英文形式的)

2. 示例演示

假設用戶1、2、3、4是如下圖所示的關係:

假設有2個mapper(A和B)和1個reducer(C),初始時4個節點的PageRank值都是0.25

其中,關於用戶1和2的數據由mapperA讀取並處理,關於用戶3和4的數據由mapperB讀取並處理(經驗證,即使一個用戶的數據由不同mapper讀取,最終收斂的結果也大致相同)

map的輸入輸出結果如下:

reduce的輸入輸出結果如下,輸入是2個mapper的輸出,輸出的結果中更新了節點的PageRank值

reducer處理完之後,又將結果輸入給mapper處理,直到迭代次數超過設定值,或兩次迭代後所有節點PageRank值之差的總和(也可取二範數)小於設定閾值為止。

3. 示例的實驗結果

(1) 首先使用Matlab以冪法計算出在$p=1.0$情況下示例得到的結果(其主要作用是驗證後面Python版本的正確性)

matlab源碼如下:

結果為:

(2) matlab版本的PageRank並未採用mapreduce思想進行迭代,所以我另外寫了一個Python版本、以mapreduce思想實現的PageRank算法(註:我並未使用Python的map和reduce函數,而是採用了更易於理解的實現方式),使用的閾值為0.0001,最多迭代100次。

得到的結果如下,總共迭代了15次

上面的結果與Matlab用冪法得到的PageRank值差別很小,可以認為是正確的,這也說明了採用這種mapreduce輸入輸出格式的正確性。

OK,差不多了,希望對需要理解PageRank算法的人有所幫助!


XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved