一種改進(jìn)的PageRank算法

徐 京，陶 皖 （安徽工程大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖241000）

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

1 PageRank算法

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

其中，Oj是網(wǎng)頁j的鏈出數(shù)目。

互聯(lián)網(wǎng)鏈接結(jié)構(gòu)的形成都是自發(fā)和無序的，可能存在沉淀現(xiàn)象：一些網(wǎng)頁簇只鏈向簇內(nèi)的其他一些網(wǎng)頁，而不鏈向簇外的網(wǎng)頁；傳遞進(jìn)來的PageRank值滯留在網(wǎng)頁簇內(nèi)部，不能傳遞出去。解決辦法是：設(shè)定瀏覽者會(huì)隨機(jī)選擇一個(gè)鏈接繼續(xù)瀏覽的概率是d，設(shè)定瀏覽者不通過鏈接，而跳到另一個(gè)隨機(jī)網(wǎng)頁的概率是1－d。所得的公式為：

PageRank算法計(jì)算時(shí)使用冪迭代法，根據(jù)上述公式得出迭代公式為：

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

由于鏈接結(jié)構(gòu)的自發(fā)和無序性，矩陣A存在“黑洞效應(yīng)”：網(wǎng)絡(luò)鏈接圖中存在入度為0的網(wǎng)頁，經(jīng)過有限次迭代后，該鏈接圖中的所有網(wǎng)頁的PageRank值均為0。解決方法：對(duì)于沒有外鏈的網(wǎng)點(diǎn)，設(shè)定鏈接圖中其余所有的網(wǎng)點(diǎn)都是它的外鏈，即在鄰接矩陣中，某行全為0，則將全部元素值設(shè)為1／N。所得公式為：

PageRank公式即為：

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

2 MapReduce介紹

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

3 算法改進(jìn)及實(shí)現(xiàn)

3.1 算法改進(jìn)

結(jié)合了MapReduce的PageRank算法已在一定程度上減少了時(shí)間消耗，為進(jìn)一步減少時(shí)間消耗，筆者將結(jié)合了MapReduce的PageRank算法再結(jié)合Gauss－Seidel，在并行的基礎(chǔ)上減少迭代次數(shù)，從而進(jìn)一步減少時(shí)間消耗。

1）Jacobi迭代法 PageRank算法使用的冪迭代法實(shí)質(zhì)是特殊的Jacobi迭代法。

DX ＝b的Jacobi計(jì)算公式［6］如下：

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

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

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

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

3.2 算法的具體實(shí)現(xiàn)

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

4 結(jié)果與評(píng)價(jià)

使用Matlab、分布式計(jì)算工具箱和ncm工具箱［8.9］模擬改進(jìn)后的PageRank算法。分布式計(jì)算工具箱用在4核處理器計(jì)算機(jī)上模擬Hadoop平臺(tái)下的MapReduce，ncm工具箱中的Harvard500（訪問哈佛大學(xué)的網(wǎng)頁，所生成的網(wǎng)絡(luò)連接關(guān)系）作為測(cè)試改進(jìn)的PageRank算法所用的數(shù)據(jù)集。Harvard500數(shù)據(jù)集包含500個(gè)節(jié)點(diǎn)和2636個(gè)鏈接。

使用ncm工具箱中的所提供的500個(gè)節(jié)點(diǎn)。用Power Method和改進(jìn)的PageRank算法：Gauss－Seidel Method，用不同迭代精度進(jìn)行迭代，選取4個(gè)處理機(jī)最大的迭代次數(shù)進(jìn)行比較，如表1所示。

表1 不同精度所得迭代次數(shù)

圖1 迭代次數(shù)比較曲線

Power Method和Gauss－Seidel Method迭代次數(shù)比較的曲線如圖1所示。由表1和圖1可以得出：隨著計(jì)算精度的提高，Gauss－Seidel Method迭代速度快的優(yōu)勢(shì)越來越明顯。由此得出：當(dāng)Web頁面越來越龐大時(shí)，改進(jìn)的PageRank算法優(yōu)勢(shì)越來越明顯，即計(jì)算各個(gè)網(wǎng)頁的權(quán)威值時(shí)間減少，效率提高。

［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數(shù)據(jù)挖掘 ［M］.俞勇，薛貴榮，韓定一 （譯）.北京：清華大學(xué)出版社，2009.

［4］吳家麒，譚永基.PageRank算法的優(yōu)化和改進(jìn) ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，（16）：56－58.

［5］劉鵬 .云計(jì)算 ［M］.北京：電子工業(yè)出版社，2011.

［6］李慶揚(yáng)，王能超，易大義 .數(shù)值分析 ［M］.北京：清華大學(xué)出版社，2008.

［7］向令，王鵬 .并行迭代算法的研究及應(yīng)用 ［J］.成都信息工程學(xué)院學(xué)報(bào)，2007（S）：109－111.

［8］Cleve B M.Matlab數(shù)值計(jì)算 ［M］.喻文健 （譯）.北京：機(jī)械工業(yè)出版社，2006.

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