求解PageRank問(wèn)題的GMRES-Inout方法

顧傳青,邵晨晨

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

·快報(bào)·

求解PageRank問(wèn)題的GMRES-Inout方法

顧傳青,邵晨晨

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

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

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

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

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

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

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

因?yàn)閑Tx=1,由式(1)可得特征值問(wèn)題x=Ax可以轉(zhuǎn)化為求線性方程組

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

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

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

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

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

算法1(重啟的GMRES方法)

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

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

算法2(GMRES-Inout方法)

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

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

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

3 數(shù)值實(shí)驗(yàn)

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

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

為了測(cè)試算法的相對(duì)加速效果,定義加速比為

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

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

從表1中可以看出,GIO方法的運(yùn)算時(shí)間最短,且相對(duì)于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]顧傳青,王磊.一類(lèi)修正的冪外推法加速PageRank計(jì)算[J].上海大學(xué)學(xué)報(bào)(自然科學(xué)版),2013, 19(2):150-153.

[6]顧傳青,馬先磊.求解PageRank問(wèn)題的多步冪法修正的內(nèi)外迭代法[J].應(yīng)用數(shù)學(xué)與計(jì)算數(shù)學(xué)學(xué)報(bào), 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]蔣爾雄.矩陣計(jì)算[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

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

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

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