一種改進的PageRank算法

徐 京，陶 皖 （安徽工程大學計算機與信息學院，安徽 蕪湖241000）

21世紀，搜索引擎成為獲取信息的重要工具。而隨著Web數量的急劇增加，搜索引擎如何以較快的速度給用戶提供權威的相關網頁。下面，筆者將提出一種改進的PageRank算法，即在傳統的PageRank算法［1］中加入MapReduce和Gauss－Seidel，以減少迭代次數，減少時間消耗，提高并行效率。

1 PageRank算法

PageRank算法用于計算網頁的權威值，該值是Google對檢索的網頁進行排序的一個重要依據［2］。PageRank算法由Sergey Brin和Larry Page在1998年4月舉行的第7屆國際萬維大會 （WWW7）上提出［3］。PageRank的基本思想如下：網頁A鏈向網頁B是網頁A對網頁B的認可，視為網頁A對網頁B投了一票。一個網頁得票越多，網頁的權威值越大。網頁i的權威值Pi按照以上的思想化為公式：

其中，Oj是網頁j的鏈出數目。

互聯網鏈接結構的形成都是自發和無序的，可能存在沉淀現象：一些網頁簇只鏈向簇內的其他一些網頁，而不鏈向簇外的網頁；傳遞進來的PageRank值滯留在網頁簇內部，不能傳遞出去。解決辦法是：設定瀏覽者會隨機選擇一個鏈接繼續瀏覽的概率是d，設定瀏覽者不通過鏈接，而跳到另一個隨機網頁的概率是1－d。所得的公式為：

PageRank算法計算時使用冪迭代法，根據上述公式得出迭代公式為：

其中，P為各個網點的PageRank值，是n行1列矩陣；E是一個全為1的n×n方陣；A是鏈接矩陣，每行和為1，即把每行做求和分解，Aij表示節點i鏈向節點j。

由于鏈接結構的自發和無序性，矩陣A存在“黑洞效應”：網絡鏈接圖中存在入度為0的網頁，經過有限次迭代后，該鏈接圖中的所有網頁的PageRank值均為0。解決方法：對于沒有外鏈的網點，設定鏈接圖中其余所有的網點都是它的外鏈，即在鄰接矩陣中，某行全為0，則將全部元素值設為1／N。所得公式為：

PageRank公式即為：

PageRank算法中使用的冪迭代法［4］，計算簡單但收斂速度慢，時間消耗較大。對于這個問題一些學者提出使用MapReduce并行處理，減少時間消耗。

2 MapReduce介紹

MapReduce是Google提出的一個軟件架構，是一種處理海量數據的并行編程模式，用于大規模數據集 （通常大于1TB）的并行運算［5］。MapReduce分為 “Map（映射）”階段和 “Reduce（化簡）”階段。MapReduce過程：首先將輸入文件分成互相獨立的N塊，每塊分配給一個執行Map函數的處理器，Map：（in＿key，in＿value）→ ｛（keyj，valuej）｜j＝1…k｝｝。執行Reduce函數的處理器將每個 Map函數所產生的中間結果進行合并，Reduce：（key，［value1，…，valuem］）→ （key，final＿value）。各個執行Reduce函數的處理器也可以并行［3］。

3 算法改進及實現

3.1 算法改進

結合了MapReduce的PageRank算法已在一定程度上減少了時間消耗，為進一步減少時間消耗，筆者將結合了MapReduce的PageRank算法再結合Gauss－Seidel，在并行的基礎上減少迭代次數，從而進一步減少時間消耗。

1）Jacobi迭代法 PageRank算法使用的冪迭代法實質是特殊的Jacobi迭代法。

DX ＝b的Jacobi計算公式［6］如下：

式中，D 為系數矩陣且非奇異，dii≠0；b＝ （b1，b2，…，bnT）。當dii＝1，bi＝0時Jacobi迭代法即為PageR－ank算法中的冪迭代法。即PageRank算法中的冪迭代法可轉化為求方程組（P－E）X＝0。

Jacobi計算簡單但收斂速度慢，而Gauss－Seidel收斂快于Jacobi，所以下面將討論把鄰接矩陣轉化為大型稀疏矩陣線性方程組后采用MapReduce并行編程方法和Gauss－Seidel相結合，使迭代次數更低，并行效率更高。

2）Gauss－Seidel迭代法 系數矩陣D為非奇異，且dii≠0。DX ＝b的Gauss－Seidel的計算公式［6］如下：

Gauss－Seidel迭代可以看成是對Jacobi迭代的一種改進［7］。Gauss－Seidel使用最新信息計算，收斂快，減少了迭代次數。

3.2 算法的具體實現

按照MapReduce編程方法，MapReduce函數首先對矩陣進行分塊處理，將m至n列分為一塊，其中n＞m。然后由Master節點將各個分塊矩陣和序號為m至n的頁面的初始權威值分派給各個Map worker節點。根據Gauss－Seidel的迭代次數少的優點，在 Map函數中使用Gauss－Seidel迭代方法。Gauss－Seidel迭代：計算時，使用（j＜i）和（j≥i）。因為Pj（k＋1）中的j＜i，所以只要順序循環，將上輪循環所得的值Pj（k＋1）（j＜i）放入下輪循環中參與計算即可［7］。Map函數處理完成后，由Master節點將結果分配給Reduce worker節點。Reduce函數所得的結果即為各個Web頁面的權威值。偽代碼如下：

4 結果與評價

使用Matlab、分布式計算工具箱和ncm工具箱［8.9］模擬改進后的PageRank算法。分布式計算工具箱用在4核處理器計算機上模擬Hadoop平臺下的MapReduce，ncm工具箱中的Harvard500（訪問哈佛大學的網頁，所生成的網絡連接關系）作為測試改進的PageRank算法所用的數據集。Harvard500數據集包含500個節點和2636個鏈接。

使用ncm工具箱中的所提供的500個節點。用Power Method和改進的PageRank算法：Gauss－Seidel Method，用不同迭代精度進行迭代，選取4個處理機最大的迭代次數進行比較，如表1所示。

表1 不同精度所得迭代次數

圖1 迭代次數比較曲線

Power Method和Gauss－Seidel Method迭代次數比較的曲線如圖1所示。由表1和圖1可以得出：隨著計算精度的提高，Gauss－Seidel Method迭代速度快的優勢越來越明顯。由此得出：當Web頁面越來越龐大時，改進的PageRank算法優勢越來越明顯，即計算各個網頁的權威值時間減少，效率提高。

［1］Page L，Brin S，Motwani R，et al.The PageRank citation ranking：Bring order to the Web ［N］.Stanford Digital Libraries Working Paper，1998.

［2］Amy N L，Carl D M.Deeper Inside PageRank ［J］.Internet Mathematic，2005，1 （3）：335－380.

［3］Liu Bing.Web數據挖掘 ［M］.俞勇，薛貴榮，韓定一 （譯）.北京：清華大學出版社，2009.

［4］吳家麒，譚永基.PageRank算法的優化和改進 ［J］.計算機工程與應用，2009，（16）：56－58.

［5］劉鵬 .云計算 ［M］.北京：電子工業出版社，2011.

［6］李慶揚，王能超，易大義 .數值分析 ［M］.北京：清華大學出版社，2008.

［7］向令，王鵬 .并行迭代算法的研究及應用 ［J］.成都信息工程學院學報，2007（S）：109－111.

［8］Cleve B M.Matlab數值計算 ［M］.喻文健 （譯）.北京：機械工業出版社，2006.

［9］張德豐 .MATLAB數值分析與仿真案例 ［M］.北京：清華大學出版社，2011.