顧傳青,邵晨晨

(上海大學(xué)理學(xué)院,上海 200444)

·快報·

求解PageRank問題的GMRES-Inout方法

顧傳青,邵晨晨

(上海大學(xué)理學(xué)院,上海 200444)

PageRank算法已經(jīng)成為網(wǎng)絡(luò)搜索中的核心技術(shù).首先基于內(nèi)外迭代法,運(yùn)用預(yù)處理的思想,提出GMRES-Inout方法,即重啟的GMRES方法修正的內(nèi)外迭代法;然后,詳細(xì)介紹該方法的具體過程及收斂性分析;最后,通過數(shù)值實驗說明該方法的有效性.

PageRank;GMRES方法;內(nèi)外迭代法;收斂性

Google搜索引擎以其著名的PageRank算法成為近年來最成功的搜索引擎之一[1]. 1998年P(guān)ageRank算法由斯坦福大學(xué)的Page等[2]提出,該算法通過分析網(wǎng)絡(luò)的鏈接結(jié)構(gòu)獲得網(wǎng)頁的重要程度排名.PageRank問題就是求解Google矩陣A的首特征值1所對應(yīng)的特征向量,即線性系統(tǒng)

的解,其中α∈(0,1)為阻尼因子,e=(1,1,···,1)T∈Rn,v=e/n,矩陣P由網(wǎng)頁的超鏈接結(jié)構(gòu)[3]所定義,n為矩陣P的維數(shù).

自PageRank問題提出以來,出現(xiàn)了很多求解該問題的方法,其中最原始的就是經(jīng)典的Power算法[2].Power算法采用迭代的思想計算矩陣的特征向量,其優(yōu)點是方法簡單、單次迭代的運(yùn)算量小,缺點是線性收斂速度慢,尤其當(dāng)阻尼因子α接近1時.因此,冪法的加速方法應(yīng)運(yùn)而生,比如二次外推法[3]、內(nèi)外迭代法[4]、修正的冪外推法[5]、多步冪法修正的內(nèi)外迭代法[6]等.另外,PageRank問題可以轉(zhuǎn)化為求解線性方程組的問題,因此一些Krylov子空間方法被用于求解PageRank問題,例如廣義極小殘量(generalized minimal residual,GMRES)方法[7]、預(yù)處理和外推加速的GMRES方法[8]等.為了加快PageRank問題的求解速度,本工作基于內(nèi)外迭代法,運(yùn)用預(yù)處理的思想,提出了GMRES-Inout方法,即重啟的GMRES修正的內(nèi)外迭代法.

1 內(nèi)外迭代法和重啟的GMRES方法

因為eTx=1,由式(1)可得特征值問題x=Ax可以轉(zhuǎn)化為求線性方程組

的解.根據(jù)PageRank問題中阻尼因子α越小,收斂速度越快的性質(zhì),Gleich等[4]通過引入比α更小的參數(shù)β,0＜β＜α,將式(2)轉(zhuǎn)化為等價方程組

求解系數(shù)矩陣為(I?βP)的線性系統(tǒng)仍然是困難的.接著,Gleich等[4]提出了采用Richardson迭代法計算x(k+1).將式(4)的右端項記為f,即

來判斷迭代何時終止.式(8)中,參數(shù)η和τ分別是內(nèi)、外迭代的收斂精度.

Saad等[7]提出的GMRES方法是一種求解稀疏線性系統(tǒng)的經(jīng)典迭代方法.令b=(1?α)v,由式(2)可得

由于GMRES方法的時間復(fù)雜度和空間復(fù)雜度都較大,因此大多采用重啟的GMRES方法[7-9].

算法1(重啟的GMRES方法)

2 重啟的GMRES方法修正的內(nèi)外迭代法及收斂性分析

為了加快PageRank問題的求解速度,本工作提出一種新的算法:重啟的GMRES方法修正的內(nèi)外迭代(GMRES-Inout)方法.GMRES-Inout方法結(jié)合了內(nèi)外迭代法和重啟的GMRES方法的優(yōu)點,基本思想如下:給定一個初始向量,利用重啟的GMRES方法得到一個粗糙的解,若所求的解未達(dá)到收斂精度,則將解向量作為內(nèi)外迭代法的初始向量,利用內(nèi)外迭代法繼續(xù)求解;否則重復(fù)上述過程,直至達(dá)到收斂精度.

算法2(GMRES-Inout方法)

步驟一給定重啟步數(shù)m,初始向量x0,內(nèi)、外迭代收斂精度η,τ,參數(shù)α1,α2,maxit用來控制內(nèi)外迭代法的重啟數(shù),外迭代誤差r=1,restart=0.

步驟二將算法1運(yùn)行2～3次,若殘差范數(shù)達(dá)到收斂精度τ,算法停止;否則繼續(xù).

步驟三將由重啟的GMRES方法得到的近似解x1作為內(nèi)外迭代法的初始向量,

3 數(shù)值實驗

下面給出幾種方法的數(shù)值實驗結(jié)果.所有的數(shù)值實驗都是在內(nèi)存為4 GB、主頻為1.8 GHz、處理器為AMD E2-3000M的計算機(jī)上使用Matlab(R2012b)進(jìn)行的.

為了保證實驗的公平性,所有方法均選取相同的初始向量x(0)=v(見式(1)).因為從理論和實踐的角度,2-范數(shù)都是一種較好的選擇,所以在本實驗中將2-范數(shù)作為算法的終止準(zhǔn)則.

為了測試算法的相對加速效果,定義加速比為

算例選取測試矩陣Web-Stanford,共包含281 903個網(wǎng)頁和2 312 497個鏈接,其稠密度為0.291×10?2.表1給出了Inout方法、PIO方法、AIO方法、GIO方法的運(yùn)算時間和矩陣向量積數(shù).在GIO方法中,選取α1=α?0.1,α2=α?0.1,maxit=15.

表1 對于測試矩陣Web-Stanford采用4種算法的比較結(jié)果Table 1 Comparison of various methods for the test matrix Web-Stanford

從表1中可以看出,GIO方法的運(yùn)算時間最短,且相對于AIO方法有顯著的改善.

[1]WU G,WEI Y M.A Power-Arnoldi algorithm for computing PageRank[J].Numerical Linear Algebra with Applications,2007,14(7):521-546.

[2]PAGE L,BRIN S,MOTWANI R,et al.The PageRank citation ranking:bring order to the web[R/OL].(2016-12-24)[2017-03-22].http://homepages.dcc.ufmg.br/vnivio/cursos/rill/sources/ pagerank.pdf.

[3]KAMVAR S D,HAVELIWALA T H,MANNING C D,et al.Extrapolation methods for accelerating PageRank computations[C]//12th International World Wide Web Conference.2003:261-270.

[4]GLEICH D F,GRAY A P,GREIF C,et al.An inner-outer iteration method for computing Page-Rank[J].SIAM Journal on Scientific Computing,2010,32(1):349-371.

[5]顧傳青,王磊.一類修正的冪外推法加速PageRank計算[J].上海大學(xué)學(xué)報(自然科學(xué)版),2013, 19(2):150-153.

[6]顧傳青,馬先磊.求解PageRank問題的多步冪法修正的內(nèi)外迭代法[J].應(yīng)用數(shù)學(xué)與計算數(shù)學(xué)學(xué)報, 2014,28(4):454-460.

[7]SAAD Y,SCHULTZ M H.GMRES:a generalized minimal residual algorithm for solving nonsymmetric linear systems[J].SIAM Journal on Scientific and Statistical Computing,1986,7(3): 856-869.

[8]PU B Y,HUANG T Z,WEN C.A preconditioned and extrapolation-accelerated GMRES method for PageRank[J].Applied Mathematics Letters,2014,37(11):95-100.

[9]蔣爾雄.矩陣計算[M].北京:科學(xué)出版社,2008.

[10]HAVELIWALA T H,KAMVAR A D.The second eigenvalue of the google matrix[R/OL].(2016-11-21)[2016-012-20].http://ilpubs.stanford.edu:8090/582.

[11]GU C Q,XIE F,ZHANG K.A two-step splitting iteration for computing PageRank[J].Journal of Computational and Applied Mathematics,2015,278:19-28.

[12]GU C Q,WANG W W.An Arnoldi-Inout algorithm for computing PageRank problems[J]. Journal of Computational and Applied Mathematics,2017,309:219-229.

A GMRES-Inout algorithm for computing PageRank problems

GU Chuanqing,SHAO Chenchen
(College of Sciences,Shanghai University,Shanghai 200444,China)

The PageRank algorithm for determining the importance of Web pages has become a central technique in Web search.Based on the inout method,a GMRESInout algorithm which modifying the inner-outer method preconditioned with the restarted GMRES algorithm is proposed.Description and convergence analysis of the proposed algorithm are given.Numerical results are reported to demonstrate the efficiency of the proposed algorithm.

PageRank;GMRES algorithm;inner-outer iteration;convergence

TP 391.9;O 242.2

A

1007-2861(2017)02-0179-06

10.3969/j.issn.1007-2861.2016.07.010

2016-12-24

國家自然科學(xué)基金資助項目(11371243);上海市教委科研創(chuàng)新資助項目(13ZZ068);上海市重點學(xué)科建設(shè)資助項目(S30104)

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

E-mail:cqgu@staff.shu.edu.cn