求解PageRank問題的Arnold i-P IO算法

顧傳青,聶影,王金波

(1.上海大學理學院,上海200444;2.保密通信重點實驗室,成都610041)

求解PageRank問題的Arnold i-P IO算法

顧傳青1,聶影1,王金波2

(1.上海大學理學院,上海200444;2.保密通信重點實驗室,成都610041)

PageRank算法能幫助用戶快速、準確地在巨量雜亂無章的信息中檢索出有用的信息.兩步分裂迭代法是用冪法來修正內外分裂(power-inner-outer,PIO)迭代法以加速PageRank算法.基于兩步分裂迭代法,將預處理思想運用于求解PageRank問題,提出了求解Page-Rank問題的深度重啟的Arnoldi算法加速的兩步分裂迭代法,然后對此算法的收斂性進行了證明.數值實驗結果證明,該算法的計算速度要快于兩步分裂迭代法.

內外迭代法;兩步分裂迭代法;深度重啟的Arnoldi算法

網絡是人們獲取信息的重要來源,如何快速準確地從互聯網上檢索出需要的信息已成為判斷搜索引擎優劣的重要指標.搜索引擎最核心的部分是搜索算法的設計.PageRank算法是用于網頁排序的算法,是當今網絡搜索引擎Google的核心技術.Google矩陣A定義如下:

式中,α∈(0,1)為阻尼因子,矩陣P由網絡的超鏈接結構所定義,E=veT,e=(1,1,···,1)T∈Rn,其中v=e/n,n為矩陣A的維數.PageRank算法就是求解矩陣A對應的特征向量,即線性系統

冪法[1]是研究PageRank問題最經典的算法,但也存在線性收斂速度慢的不足.于是一些迭代算法被提出來解決這個問題.G leich等[2]提出利用內外迭代法求解PageRank問題.Gu等[3]提出了將冪法與內外迭代法結合的兩步迭代法.Wu等[4]提出用重啟的Arnoldi算法來修正冪法.

1 兩步分裂迭代法和深度重啟的Arnold i算法

1.1 內外迭代法

給定∥x∥=1(∥x∥為向量x的二范數)的初始向量,而x=Ax=(αP+(1-α)veT)x,則PageRank問題可以轉化為求線性方程

的解.因為eTx=1,G leich等[2]引入參數β,把式(3)變成

并用如下不動點迭代求解:

用Richardson迭代計算x(k+1),

定義內線性系統(I-βP)y=f,應用Richardson內迭代可得

1.2 兩步分裂迭代法

在內外迭代法的基礎上,Gu等[3]提出了運用兩步分裂迭代法求解PageRank問題,具體格式如下:給定一個初值x(0),計算

到序列{x(k)}.

1.3 深度重啟的Arno ld i算法

深度重啟的Arnoldi算法[4-5]可選擇不同的初始向量,收斂到不同的特征值,具有更大的靈活性,算法過程如下.

步驟1給定K rylov子空間維數m,所需求的特征對的個數p≤m,控制精度tol和單位初始向量v1.

步驟2運行m步關于A和v1的Arnoldi過程,得到Vm+1,~Hm,Hm.計算Hm的所有特征對(~λi,yi),i=1,2,···,m.將Hm的特征值按模數遞減排序,從中選出前p個最大的特征對,轉向步驟5.

步驟3以vp+1為初始向量運行m-p步Arnoldi過程,得到Vm+1,,Hm.計算Hm的所有特征對,i=1,2,···,m.將Hm的特征值按模數遞減排序,選擇前p個特征對.

步驟4檢驗收斂性.對于得到的最大的Ritz值λ1和Ritz向量y1計算其殘量.若滿足計算精度,則選取~x1=Vmy1作為PageRank向量的近似解,算法停止,否則繼續.

步驟5將選出的p個特征向量yi,i=1,2,···,p,正交化為2范數的單位向量.如果特征向量yi是復向量,需要實部和虛部分開存取,構造m×p階矩陣Wp=[w1,w2,···,wp].如果有必要,可調整p的大小(比如使p增加或減少1).

步驟6通過在Wp的底部增加一行0形成(m+1)×p的矩陣=[Wp;0].令Wp+1= [~Wp,em+1],em+1是(m+1)×(m+1)階單位矩陣Im+1的最后一列.顯然(m+1)×(p+1)的矩陣Wp+1是正交矩陣.

步驟7使用步驟2得到的Vm+1和形成新的Vm+1和.返回步驟3.

2 求解PageRank問題的預處理兩步分裂迭代法

本工作結合兩步分裂迭代法和深度重啟的Arnoldi算法,提出求解PageRank問題的深度Arnoldi重啟的兩步分裂迭代法.本算法的基本思想如下:給定一個初始向量,利用深度重啟的Arnoldi算法得到一個粗糙的解;如果所求解還是沒有達到收斂精度,則將深度重啟的Arnoldi算法求得的解向量作為兩步分裂迭代法的初始向量,利用兩步分裂迭代法繼續求解;重復上述過程,直到達到收斂精度.在此算法中,本工作利用參數α1,α2,restart和maxit控制兩步分裂迭代法和深度重啟的Arnoldi算法的轉換.定義ratio=rcurr/rpre,ratio1=dcurr/dpre,利用ratio和ratio1保證算法的穩定性.選擇α1=α-0.1或α-0.2,α2=α-0.1或α-0.2,提出以下Arnoldi-內外(Arnoldi-power-inner-outer,Arnoldi-PIO)迭代法.

(1)開始.給定初始向量v,選取K rylov子空間的維數m=8,期望的特征向量數p=4,參數α,β1和β2.參數α1,maxit用來控制兩步分裂迭代法的重啟數,restart=0,外迭代的誤差r=1.

(2)運行深度重啟的Arnoldi(2～3次).若是第1次,則運行1.3節中的步驟2～步驟7,否則運行步驟3～步驟7.如果殘差范數滿足收斂精度,算法停止,否則繼續.

(3)由深度重啟的Arnoldi算法得到的PageRank向量的近似解~x1作為兩步分裂迭代法的初始向量.

restart=0;

while restartτ

x=x/∥x∥1;z=Px;

r=∥αz+(1-α)v-x∥2;

r0=r;r1=r;ratio=0;

while ratio<α1&r>τ

x=αz+(1-α)v;

z=Px;

f=(α-β)z+(1-α)v;

ratio1=0;

while ratio1<α2&d>η

x=f+βz;

d=∥f+βz-x∥2;

ratio1=d/d0;

d0=d;

end

r=∥αz+(1-α)v-x∥2;

ratio=r/r0;

r0=r;

end

x=αz+(1-α)v;

x=x/∥x∥1;

if r/r1>α1

restart=restart+1;

end

end

如果r<τ,則算法停止,否則轉向步驟2.

3 算法收斂性的證明

Gu[3]給出了兩步分裂迭代法的收斂性證明.Morgan[6]和Sorensen等[7]已經對深度重啟的Arnoldi算法的收斂性給出證明.本工作將對Arnoldi-PIO算法給出一定的理論分析,證明其收斂性.將通過深度重啟的Arnoldi算法求得的PageRank向量v1作為兩步分裂迭代法的初始向量.通過兩步分裂迭代法得到的向量為=,其中k≥maxit, G=(I-βP)-1((α-β)PA+A-αP),ω為規范化因子,n為P的維數.將作為m步標準Arnoldi過程(即深度重啟的Arnoldi算法的第一步迭代)的初始向量,形成新的K rylov子空間:

下面通過定理1可以證明上述過程的收斂性.

定理1假設矩陣A是可對角化矩陣,~Pm是Km(A,v?1)上的正交投影,則

證明假設~Pm是Km上的正交投影,那么對任意的u∈Km,存在q(x)∈Lm-1使得

4 數值實驗

本工作通過數值實驗說明深度重啟的兩步分裂迭代法的有效性.所有的數值實驗是在內存為4GB,主頻為2.6 GHz,操作系統為W indows 8,處理器為Intel(R)Core(TM)i5-3230MCPU的計算機上使用MATLAB(R2014a)進行的.用tCPU表示運算時間,以s為單位,Mat-Vec表示矩陣向量積數.對于內外迭代法,選取適當的參數有利于體現算法的有效性.數值實驗選取β=0.5和η=10-2.為了保證數值實驗的公平性,在兩步分裂迭代法和深度重啟的兩步分裂迭代法中同樣取η=10-2.為了說明測試算法的相對加速效果,定義

4.1 數值算例1

算例1的測試矩陣Hollins包括6 012個網頁和23 875個鏈接.本算例給出了內外(Innout)迭代法、兩步分裂(PIO)迭代法和深度重啟的兩步分裂(Arnoldi-PIO)迭代法的計算時間與矩陣向量積數.表1給出了3種算法的數值結果,圖1根據不同的α繪制了3種算法的收斂曲線.

表1 關于Hollins矩陣3種算法的數值結果(τ=10-8)Tab le 1 Numerical resu lts of three algorithms for Hollinsmatrix(τ=10-8)

算例1的實驗結果表明,Arnoldi-PIO算法性能相對于其他兩種算法有顯著的改善.對于矩陣Hollins,當α=0.998時,Arnoldi-PIO算法僅用0.177 5 s就達到了精度要求,PIO算法用了0.685 0 s、Inn-out用了0.949 6 s才達到精度要求.由圖1中殘量范數和迭代步數的關系可觀察到,Arnoldi-PIO算法的收斂速度是最快的,由此可驗證深度重啟的兩步分裂迭代法的有效性.

4.2 數值算例2

算例2選取的測試矩陣是Stanford-Berkeley,包含683 446個網頁和7 583 376個鏈接.表2給出了Inn-out,PIO和Arnoldi-PIO 3種迭代算法的的數值結果.圖2根據不同的α繪制了隨著迭代步數的增加,殘差范數的變化情況.

圖1 關于Hollins矩陣3種算法的收斂性分析(τ=10-8)Fig.1 Convergence analysis of three algorithms for Hollinsmatrix(τ=10-8)

表2 關于Stan ford-Berkeley矩陣3種算法的數值結果(τ=10-8)Tab le 2 Numerical resu lts of three algorithms for Stanford-Berkeley matrix(τ=10-8)

圖2 關于Stanford-Berkeley矩陣3種算法的收斂性分析(τ=10-8)Fig.2 Convergence analysis of three algorithms for Stan ford-Berkeley matrix(τ=10-8)

由表2可知,Arnoldi-PIO算法相比另兩種算法使用了更少的計算時間與矩陣向量積數,效果卻最好.圖2描述了當α=0.990,0.993,0.995,0.998時3種算法的迭代次數,可知Arnoldi-PIO算法的收斂速度是最快的.因此,Arnoldi-PIO算法的有效性得以驗證.

[1]PAGE L,BRIN S,MOTWANI R,et al.The PageRank citation ranking:bring order to the web[R/OL].(2001-10-30)[2014-06-20].http://ilpubs.stan ford.edu:8090/422/1/1999-66.pd f.

[2]GLEICH D,GRAY A,GREIF C,et al.An inner-outer iteration method for computing PageRank[J].SIAMJ Sci Compute,2010,32(1):349-371.

[3]GU C Q,X IE F,ZHANG K.Atwo-stepsplitting iteration for computing PageRank[J].Journal of Computational and Applied Mathematics,2015,278:19-28.

[4]W U G,W EI Y M.APower-Arnoldi algorithmfor compuring PageRank[J].Numer Linear Algebra Appl,2007,14:521-546.

[5]W U K,SIMON H.Thick-restart Lanczosmethod for large symmetric eigenvalue problems[J]. SIAMJournal on Matrix Analysis and Applications,2000,22:602-616.

[6]MORGAN R.Aharmonic restarted Arnoldialgorithmfor calculating eigenvalues and determing multiplicity[J].Linear Algebra and Its Applications,2006,415:96-113.

[7]SORENSEN D.Implicit application of polynomial fi lters in a k-stepArnoldimethod[J].SIAMJournal on Matrix Analysis and Applications,1992,13:357-385.

Arnold i-PIO algorithmfor PageRank

GU Chuanqing1,NIE Ying1,WANG Jinbo2
(1.College of Sciences,Shanghai University,Shanghai 200444,China; 2.Science and Technology on Communication Security Laboratory,Chengdu 610041,China)

The PageRank algorithmplays an important role in determining the importance of Web pages.The power-inner-outer(PIO)method is a two-stepsplitting iteration framework that combines the inner-outer scheme with the classical power method to accelerate the computation of PageRank algorithm.This paper proposes an Arnoldi-PIO algorithm,which is a PIO iteration algorithmmodified with the thick restarted Arnoldi method.Description and convergence of the proposed algorithmare discussed in details. Numerical resu lts show effi ciency and convergence behaviors of the algorithm.

inner-outer iteration;two-stepsplitting iteration;thick restarted Arnoldi algorithm

O 212

A

1007-2861(2017)04-0555-08

DO I:10.12066/j.issn.1007-2861.1867

2016-10-13

國家自然科學基金資助項目(11371243);上海市重點學科建設資助項目(S30104);中國電子科技集團公司第三十研究所委托項目

顧傳青(1955—),男,教授,博士生導師,研究方向為數值逼近、數值代數及其應用.

E-mail:cqgu@shu.edu.cn