PageRank算法的二級加速優(yōu)化方案

劉健雄，王曉程，毛俐旻

(1.中國航天科工集團二院研究生院，北京 100854；2.中國航天科工集團二院706所，北京 100854)

0 引 言

本文將討論當(dāng)今最具研究價值的主流網(wǎng)頁排序算法——PageRank算法，并對其進行改進。本算法由Larry Page和Sergey Brin提出，其思想是通過分析網(wǎng)絡(luò)的鏈接結(jié)構(gòu)來獲得網(wǎng)絡(luò)中網(wǎng)頁的重要性排名，且該算法已應(yīng)用于Google搜索引擎[1]，成為其評價網(wǎng)頁好壞的唯一標準。不過，該算法的執(zhí)行速度和資源損耗等方面已無法適應(yīng)當(dāng)今信息爆炸的時代特性，所以如何更有效更快速地提升該算法的運行效率成為研究該算法的重中之重。

如今對于PageRank算法優(yōu)化研究多種多樣，可從改善網(wǎng)絡(luò)圖結(jié)構(gòu)、加快算法收斂速度、實現(xiàn)算法并行化等各種角度提高算法效率。Héctor Migallón等利用啟發(fā)式松弛外推法對原算法中冪法實施加速[2]；Lanying Li等利用TopK算法刪除網(wǎng)絡(luò)圖冗余節(jié)點得到優(yōu)化子圖進行網(wǎng)頁評估[3]；Arne Koschel等利用Hadoop分布式計算網(wǎng)絡(luò)圖節(jié)點值[4]。上述各方案均對PageRank算法的某一方面進行單次加速，加速效果有待提升。

本文將通過多級加速冪法迭代收斂的方式繼續(xù)提升PageRank算法的執(zhí)行效率。其中，原點平移法和Aitken加速算法已被證明為加速冪法收斂的有效方法，所以本文將提出一種基于以上方法的二級加速優(yōu)化算法，通過仿真實驗分析該方案的加速效果，并且原理上可與算法并行化等其它優(yōu)化方案相結(jié)合，擁有更高的普適性、可行性，從而達到完善PageRank算法優(yōu)化的目的。

1 PageRank算法研究

1.1 算法原理

PageRank算法基于網(wǎng)頁的入鏈數(shù)量和網(wǎng)頁質(zhì)量兩方面進行分析計算[5]，即一個網(wǎng)頁接收到其它網(wǎng)頁指向的鏈接越多，或指向它的網(wǎng)頁的質(zhì)量越高，則該網(wǎng)頁越重要，PageRank值越高。使頁面i的PageRank值由PR(i)表示，則最終PageRank表達式為

(1)

其中，p1，p2,…,pN為所有被研究的頁面，q為阻尼系數(shù)，L(pj)為頁面pj鏈出頁面的數(shù)量，N為所有被研究頁面數(shù)量。

PageRank向量代表用戶在任意特定網(wǎng)頁中隨機點擊鏈接所到達頁面的概率分布。經(jīng)修正后的網(wǎng)頁相互鏈接狀態(tài)所構(gòu)建的概率矩陣滿足馬爾科夫矩陣特性，故而求解Page-Rank向量的過程即為計算該概率矩陣最大特征值所對應(yīng)特征向量的過程。而通過冪法計算已被證明為解決該問題最有效的方式。所以，本文將針對冪法計算這一過程進行加速，從而達到優(yōu)化整個PageRank算法的目的。

1.2 應(yīng)用冪法求解

冪法是一種計算矩陣主特征值(即矩陣按模最大的特征值)及相應(yīng)特征向量的迭代方法，尤其適用大型稀疏矩陣。因此，當(dāng)下搜索引擎應(yīng)用PageRank算法進行網(wǎng)頁排序時，多應(yīng)用冪法進行計算PageRank向量。

(2)

即迭代向量。則最終可推導(dǎo)出

(3)

利用式vk+1=Pvk不斷進行迭代，直到vk+1與vk值近似時停止，此時vk即為符合精確標準的所求特征向量近似值。其中所需迭代次數(shù)越少表明冪法收斂速度越快，整體PageRank算法的處理數(shù)據(jù)效率越高。

現(xiàn)有PageRank算法的優(yōu)化方案多僅對冪法計算進行一次加速，優(yōu)化效果有待提升，因此，本文將對冪法計算實施二級加速，首先對原始矩陣進行預(yù)處理，得到計算起來收斂更快的等效矩陣；再對等效矩陣的冪法計算應(yīng)用改進的Aitken算法進行加速，并通過實驗驗證加速兩次的效果比現(xiàn)今多數(shù)類似優(yōu)化方案加速效果更明顯。

2 基于原點平移法的一級加速方案

原點平移的加速方法是一種矩陣變換方法，將原始矩陣轉(zhuǎn)化為計算主特征值時收斂速度更快的等效矩陣，從而實現(xiàn)加速。將該方法應(yīng)用到PageRank算法矩陣的計算中，不會破壞原矩陣的稀疏性，同時依然可以應(yīng)用其它加速算法繼續(xù)加速冪法收斂，相互結(jié)合使用，從而達到多級加速的效果。

該方法核心在于引進等效矩陣B=P-bI，其中b為選擇參數(shù)，矩陣I為單位矩陣。原矩陣P的特征值為λ1，λ2，…，λn，則矩陣B相應(yīng)的特征值為λ1-b，λ2-b，…，λn-b，同時矩陣P與B的特征向量相同。若計算矩陣B特征向量時的收斂速度比矩陣P的快，即可達到預(yù)想的加速效果。

首先，由上式(4)可知

(4)

其中，(vk)i表示向量vk的第i個分量。(vk+1)i/(vk)i→λ1的收斂速度由比值r=|λ2/λ1|確定，r越小收斂越快，當(dāng)r=|λ2/λ1|≈1時，收斂將十分緩慢[6]。

因此，在保證選擇參數(shù)b使λ1-b仍然是矩陣B的主特征值的同時，還應(yīng)滿足

(5)

即計算矩陣B主特征值對應(yīng)的特征向量時的收斂速度比計算矩陣P時的要快。

由于矩陣P的特征值滿足|λ1|>|λ2|≥|λ3|≥…≥|λn|，且當(dāng)特征值為正時，則λ1>λ2≥λ3≥…≥λn，因此矩陣B=P-bI的主特征值必為λ1-b或λn-b。當(dāng)求矩陣P的特征值λ1對應(yīng)的特征向量時，則b首先應(yīng)滿足|λ1-b|>|λn-b|，同時收斂速度的比值盡量最小，即

(6)

所以，當(dāng)(λ2-b)/(λ1-b)=-(λn-b)/(λ1-b)，即b=(λ2+λn)/2時，收斂速度的比值最小，收斂最快。

需要注意的是，真實網(wǎng)絡(luò)鄰近矩陣P的特征值不一定均為正，增加了選取合適b值的難度，只有通過對網(wǎng)絡(luò)矩陣分布的了解來粗略地估計最佳b值的相似值，依然能進行加速收斂，同樣可大量減少處理真實網(wǎng)絡(luò)龐大數(shù)據(jù)的時間。另外，預(yù)估b值首先需要預(yù)估出矩陣P的λ2、λn值，這也增加了許多處理數(shù)據(jù)的計算量。當(dāng)下信息極速膨脹，熱點實時更新，網(wǎng)頁的相互引用關(guān)系不斷變化，導(dǎo)致一段時間需重新預(yù)估矩陣P的λ2、λn值，進一步削弱了該方案的加速效果。

可以看出，基于原點平移法的一級加速方案具有一定的局限性，實際加速效果仍需實例仿真進行驗證。因此，在我們將矩陣P預(yù)處理轉(zhuǎn)化為等效矩陣B后，還需進一步優(yōu)化計算過程，對收斂過程實施二級加速。

3 Aitken加速算法研究

Aitken加速算法是一種提高迭代法收斂速度的有效算法。該方法應(yīng)用弦截法根據(jù)已迭代計算出的值來獲取新的近似迭代值序列，且新序列的收斂速度比原序列要快，從而達到加速收斂的效果。因此，研究該算法并在此基礎(chǔ)上進行改進，是提高PageRank算法效率的重要途徑。

由式(3)可知，vk為主特征值對應(yīng)的特征向量x1的近似值，并且每迭代一次，vk越趨近于x1的精確值。應(yīng)用迭代公式迭代一次可得vk+1=φ(vk)，繼續(xù)迭代可得vk+2=φ(vk+1)。應(yīng)用微分中值定理，有vk+1-x1=φ(vk)-φ(x1)=φ′(ξ)(vk-x1)，其中φ′(ξ)變化微小，可粗略近似為定值[7]，因此，將多式聯(lián)立可推導(dǎo)出

(7)

進而

(8)

(9)

4 基于改進Aitken算法的二級加速方案

(10)

(11)

下面給出理論證明

比較兩序列(9)、(10)，則有

(12)

從而推出

(13)

所以

由上式可得出，改進的Aitken加速算法比標準算法收斂速度更快，因此，對于整個PageRank算法的執(zhí)行效率提升更大。綜合上文所述兩種加速方案，則可看出該二級加速方案比現(xiàn)有類似的優(yōu)化方案加速效果更加明顯，且可與并行化等其它方案結(jié)合使用，更具實際操作價值。

5 二級加速優(yōu)化方案實現(xiàn)

5.1 方案描述

(1)矩陣公式化真實網(wǎng)絡(luò)網(wǎng)頁鏈接狀態(tài)，得到網(wǎng)絡(luò)圖鄰近矩陣G=[gij]i,j=1。

(2)構(gòu)建矩陣G的躍遷矩陣P，其中pij=gij/ci，再加入阻尼系數(shù)q，對矩陣P進行修正，得到最終矩陣P=qP+(1-q)eeT/N。

(3)引進選擇系數(shù)b，將矩陣P進行原點平移，得到加速矩陣B=P-bI，通過計算加速矩陣B主特征值所對應(yīng)的特征向量，得到矩陣P相應(yīng)的特征向量。

(4)利用冪法計算矩陣B主特征值對應(yīng)的特征向量，其中應(yīng)用改進的Aitken算法加速冪法計算中的收斂速度，即可得到矩陣P相應(yīng)的特征向量，從而求得各網(wǎng)頁的Page-Rank值[9,10]。

下面給出該算法的偽代碼：

Function ImprovedPowerMethod( ) {

Initialize(v0);

B=P-bI; //矩陣預(yù)處理

k=1;

while(error>=ε){

vk=Bvk-1;

k=k+1;

}

}

5.2 實例仿真

實際搜索引擎處理網(wǎng)頁排序的規(guī)模十分巨大，例如Google的存儲網(wǎng)頁數(shù)量已到109級別，由于硬件條件限制，本文擬選用較小規(guī)模的web網(wǎng)頁鏈接情況進行測試[6]。以下提供的鏈接情況來源于網(wǎng)絡(luò)爬蟲抓取的固定站點(sogou.com)內(nèi)的10 000條鏈接。由于固定站點內(nèi)網(wǎng)頁相互鏈接頻繁，可避免大量的孤立網(wǎng)頁存在，提高本實驗的普適性。另外，為了體現(xiàn)本文提出的改進算法的效果，將阻尼系數(shù)q設(shè)為0.99，盡量減少該系數(shù)對收斂效果的影響，從而更能體現(xiàn)改進算法的作用。

圖1測試所應(yīng)用計算機參數(shù)為內(nèi)存6 GB，處理器Core i5-4200U，主頻1.60 GHz，測試矩陣為基于上述抓取網(wǎng)頁鏈接所構(gòu)成的10 000*10 000矩陣，將選擇參數(shù)b分別設(shè)為0.1、0.3、0.6，得到3個預(yù)處理后的等效矩陣，使用標準冪法分別計算原矩陣及以上3個矩陣，得到各矩陣冪法計算的收斂曲線并進行比較。

圖1 測試結(jié)果1

由圖1可看出，利用原點平移法得到的等效矩陣冪法計算時收斂速度有所增加，當(dāng)選擇系數(shù)b取不同值時，加速效果不同。當(dāng)b=0.3時，加速效果最明顯，即當(dāng)?shù)?0次時的誤差和標準冪法迭代70次時的誤差相近，提高效率近40%；當(dāng)b=0.1時，則曲線基本重合，提高效率近8%。因此，選擇系數(shù)的選取對于該方案的加速效果至關(guān)重要。

圖2顯示分別使用傳統(tǒng)Aitken算法和改進的Aitken算法來計算該矩陣的特征向量時的收斂曲線，其中硬件條件及被測矩陣與圖1實驗相同。

圖2 測試結(jié)果2

由圖2可看出，改進的Aitken算法收斂速度較傳統(tǒng)算法收斂速度略有提高[9]，其中改進算法在迭代50次時的誤差和傳統(tǒng)算法迭代65次時的誤差相近；迭代75次時的誤差和傳統(tǒng)算法迭代93次時的誤差相近；迭代100次時的誤差和傳統(tǒng)算法迭代120次時的誤差相近，可計算出改進的Aitken加速算法分別提高了30%、24%，20%左右的效率，可知改進后算法迭代初始時加速效果明顯，到迭代后期趨于平緩，根據(jù)日常迭代需求，可大致估算出該改進算法提高效率在25%左右。

圖3顯示分別使用標準冪法、本文提出的改進算法以及某啟發(fā)式松弛外推法[2]加速的冪法計算該矩陣最大特征值1對應(yīng)的特征向量的收斂曲線，其中硬件條件及被測矩陣與圖1實驗相同，所引用其它優(yōu)化方案根據(jù)所引文獻中給出的核心算法編寫大致程序。

圖3 測試結(jié)果3

由圖3可看出，相對于原PageRank算法，應(yīng)用本文提出的改進算法加速后的冪法收斂速度大大提高，其中改進算法加速后的冪法在迭代50次時的誤差和標準冪法迭代80次時的誤差相近；迭代75次時的誤差和標準冪法迭代120次時的誤差相近；迭代100次時的誤差和標準冪法迭代150次時的誤差相近，可計算出改進后的冪法分別提高了60%、60%，50%左右的效率，可知改進算法加速效果明顯，基本穩(wěn)定在60%左右的加速效率。另外，在實際計算中，計算機的內(nèi)存使用率一般在40%左右，改進算法的內(nèi)存損耗略高但并不明顯，可以忽略。相對于所比較的某啟發(fā)式松弛外推法，本文提出的改進算法對于冪法收斂速度的加速效果略為顯著，其中本文改進算法加速后的冪法在迭代50次時的誤差和其它改進算法加速后的冪法迭代55次時的誤差相近；迭代75次時的誤差和對比的冪法迭代80次時的誤差相近；迭代100次時的誤差和對比的冪法迭代110次時的誤差相近，可計算出改進后的冪法分別提高了10%、6.67%，10%左右的效率，可知本文改進算法相比于類似其他優(yōu)化方案加速效果略有提高。

6 結(jié)束語

PageRank算法作為當(dāng)今搜索引擎中網(wǎng)頁排序的主流算法，其本質(zhì)是求解網(wǎng)絡(luò)鄰近矩陣最大特征值對應(yīng)的特征向量，而冪法則是解決該問題最有效的方法[10]。因此本文主要針對冪法計算提出了一種二級加速優(yōu)化方案，并在小規(guī)模真實網(wǎng)頁抓取過程中測試該方案的性能，實例驗證了該方案的加速效果明顯。不過，基于原點平移法的一級加速程序優(yōu)化效果受原矩陣元素分布的影響較大，在處理大規(guī)模網(wǎng)頁數(shù)據(jù)矩陣過程中，系數(shù)的選擇和加速的效果方面同樣待驗證。所以，仍需對此進行更全面深入的研究，并設(shè)計更完善穩(wěn)定的加速程序。另外，在改進Aitken算法方面，也有進一步提升加速效果的空間。