高 臣，高斐斐，張家健

（1.河海大學(xué) 商學(xué)院，江蘇 南京 210000；2.中國(guó)科學(xué)院 力學(xué)研究所，北京 100190；3.江蘇省郵電規(guī)劃設(shè)計(jì)院有限公司 江蘇南京210000）

基于更新網(wǎng)頁(yè)排名算法的研究

高 臣1，高斐斐2，張家健3

（1.河海大學(xué) 商學(xué)院，江蘇 南京 210000；2.中國(guó)科學(xué)院 力學(xué)研究所，北京 100190；3.江蘇省郵電規(guī)劃設(shè)計(jì)院有限公司 江蘇南京210000）

頁(yè)面內(nèi)容的內(nèi)容評(píng)分與PageRank評(píng)分都需要頻繁更新，以保證提供最新的結(jié)果。基于如何使得更新PageRank向量過程更為容易，并使得更為頻繁的更新成為可能這一問題，本文通過對(duì)更新算法的數(shù)學(xué)內(nèi)容分析，研究更新PageRank向量的問題，通過提出假設(shè)矩陣Qm×m的PageRank向量φT=（φ1，φ2，…，φm），文中立足于通過3種聚合更新算法來利用φT中的值計(jì)算G的更新后的πT，文中分析了近似聚合更新、精確聚合更新、迭代聚合更新的算法，并對(duì)3種更新算法各自的使用條件進(jìn)行分析。

PageRank；近似聚合更新；精確聚合更新；迭代聚合更新

網(wǎng)頁(yè)變化可以是網(wǎng)頁(yè)內(nèi)容的改變或是頁(yè)面出鏈的改變，研究表明，一半以上的網(wǎng)頁(yè)在一周內(nèi)發(fā)生了變化，而近三分之一的.com網(wǎng)頁(yè)每天都在發(fā)生變化[1]。相比于較小的網(wǎng)頁(yè)，大型網(wǎng)頁(yè)中的變化則更為頻繁[2]。對(duì)于新增的網(wǎng)頁(yè)，內(nèi)容和鏈接的更新可能發(fā)生在以小時(shí)計(jì)算的時(shí)間尺度上[3]。因此，反映頁(yè)面內(nèi)容的內(nèi)容評(píng)分與PageRank評(píng)分都需要頻繁更新，以保證提供最新的結(jié)果。如何使得更新過程更為容易，得到研究者越來越多的重視。

PageRank向量可能發(fā)生兩類更新：1）當(dāng)超鏈接被加入到萬維網(wǎng)中或從萬維網(wǎng)中被刪除時(shí)，超鏈接矩陣H的元素發(fā)生改變，而矩陣的大小未變。該類只有這一類型的更新，那么更新PageRank向量的問題就是鏈接更新問題；2）網(wǎng)頁(yè)本身可能被加入到萬維網(wǎng)中或從萬維網(wǎng)中被刪除，那么對(duì)于頁(yè)面更新問題而言，發(fā)生的狀態(tài)將被加入到馬爾科夫鏈中或者從鏈中被刪除，此時(shí)矩陣大小也會(huì)發(fā)生改變，此類型更新問題也更加復(fù)雜。將早期精確更新的理論結(jié)果用于PageRank問題[4]，計(jì)算結(jié)果對(duì)鏈接更新問題給出了理論上的答案，對(duì)于僅有一兩行發(fā)生改變而且沒有頁(yè)面被加入或刪除的情況而言，已知的精確鏈接更新公式是有用的，但是從計(jì)算角度分析，由于萬維網(wǎng)的動(dòng)態(tài)性，該方法對(duì)更為一般的更新而言實(shí)際價(jià)值較小[5-6]。由舊的PageRank向量開始重啟冪法對(duì)于鏈接更新問題而言作用也較小[7]，因?yàn)椴荒芎?jiǎn)單地對(duì)冪法進(jìn)行調(diào)整以處理更加復(fù)雜的頁(yè)面更新問題，因此僅靠?jī)绶ū旧韥碛膳f的PageRank向量重啟算法實(shí)際價(jià)值也較小。

1 近似聚合更新

狀態(tài)聚合作為近似聚合技術(shù)方法的一部分，可以用作估計(jì)近解耦鏈的穩(wěn)態(tài)分布。同理，可以利用一個(gè)機(jī)遇狀態(tài)聚合的近似方法估計(jì)PageRank[8-9]。雖然近似聚合只能給出πk的估計(jì)值，但是近似聚合的計(jì)算量小并且可以同時(shí)處理鏈接更新和頁(yè)面更新。利用已知分布（φT=（φ1，φ2，…，φm））以及G中的更新后的轉(zhuǎn)移概率構(gòu)建一個(gè)聚合馬爾可夫鏈，其轉(zhuǎn)移概率矩陣C比G更小，利用C的穩(wěn)態(tài)分布ξT估計(jì)更新分布πT，具體算法包括：

將更新的馬爾可夫鏈鏈的狀態(tài)空間S劃分為兩組，即S=L∪L，其中，補(bǔ)集L包括所有其他狀態(tài)，L是由穩(wěn)態(tài)概率可能受更新影響最大的狀態(tài)構(gòu)成的子集，如果新加入的狀態(tài)被自動(dòng)包含在L中，則將受影響的轉(zhuǎn)移概率設(shè)為0以處理刪除的狀態(tài)。需要注意，如果一個(gè)擾動(dòng)只涉及PageRank大的稀疏鏈中的少數(shù)狀態(tài)，那么它對(duì)于穩(wěn)態(tài)向量的影響將主要是局部性的，因此，大多數(shù)穩(wěn)態(tài)概率不會(huì)受到顯著影響。根據(jù)S=L∪L導(dǎo)出更新后的轉(zhuǎn)移矩陣及其對(duì)應(yīng)的穩(wěn)態(tài)分布的一個(gè)劃分：

該式中G11，的大小為l×l，l=|L|為I的勢(shì)，G22的大小為（n-l）×（n-l），原有分布φT中對(duì)應(yīng)于L中的狀態(tài)的穩(wěn)態(tài)概率被存入一個(gè)行向量ωT中，而L中的狀態(tài)被聚合為一個(gè)超級(jí)狀態(tài)，進(jìn)而得出一個(gè)更小的聚合馬爾可夫鏈，其轉(zhuǎn)移矩陣大小為（l+1）×（l+1），給出式子（e是全1列），進(jìn)而利用近似程序計(jì)算出的穩(wěn)態(tài)分布利用中的前I個(gè)元素以及ωT中的元素，得出產(chǎn)生精確的更新分布πT的一個(gè)近似，該近似值為由此可知，與獲得完整的更新PageRank向量πT的精確值，該方法使用一個(gè)較小的穩(wěn)態(tài)向量以構(gòu)建πT的近似。

馬爾科夫鏈可能會(huì)表現(xiàn)出對(duì)微小擾動(dòng)的敏感性，對(duì)于擾動(dòng)對(duì)馬爾可夫鏈的影響，目前可以衡量穩(wěn)態(tài)概率對(duì)于轉(zhuǎn)移概率中變化的敏感程度的度量包括：轉(zhuǎn)移矩陣次主特征的絕對(duì)值接近于1的程度、不同種類條件數(shù)的微小程度、平均首達(dá)時(shí)間的微小程度等。結(jié)合上述近似聚合更新的算法，需要適當(dāng)?shù)貥?gòu)造出劃分S=L∪，并保證δT的量級(jí)處于較小規(guī)模，那么將接近于C，因此其各自的穩(wěn)態(tài)分布和ξT也會(huì)相互接近，進(jìn)而保證對(duì)于i≤l，i相πi互接近。如果C所定義的鏈在以上任何一個(gè)度量下都是良態(tài)的，那么ξT對(duì)于微小擾動(dòng)將相對(duì)不敏感，即S=L∪L的恰當(dāng)程度能夠更加直接地體現(xiàn)i≤l，i≈πi的程度，因此計(jì)算的關(guān)鍵在于確定的良態(tài)程度。

2 精確聚合更新

對(duì)于一個(gè)不可約的n狀態(tài)馬爾可夫鏈，假設(shè)其狀態(tài)空間已被劃分為k個(gè)互不相交的部分S=L1∪L2∪…∪Lk，同時(shí)假設(shè)與之對(duì)應(yīng)的轉(zhuǎn)移概率矩陣具有分塊矩陣的形式：

該條由G所定義的父馬爾可夫鏈可誘導(dǎo)出k條更短的馬爾可夫鏈[10]，具體的誘導(dǎo)方法為：與Li這組狀態(tài)相對(duì)應(yīng)的受限馬爾可夫鏈定義為一個(gè)馬爾可夫過程，僅當(dāng)父鏈對(duì)Li中的狀態(tài)進(jìn)行訪問時(shí)，該過程才會(huì)記錄父鏈的位置，并忽略所有對(duì)Li之外的狀態(tài)的訪問。已知第i條受限鏈的轉(zhuǎn)移概率矩陣為第i個(gè)隨機(jī)補(bǔ)，由給出，其中，Gi*和G*i分別為Gii被移除后的第i行和第i列的分塊，通過去除第i行和第i列的分塊可得出G*i為G的主子矩陣。

為了獲得較小的k狀態(tài)聚合鏈，可以將每個(gè)組Li壓縮為一個(gè)單一的狀態(tài)，將父轉(zhuǎn)移矩陣G壓縮為聚合轉(zhuǎn)移矩陣]（該矩陣為隨機(jī)且不可約）

對(duì)于正則鏈，在由C所定義的聚合鏈中的狀態(tài)轉(zhuǎn)移，對(duì)應(yīng)當(dāng)未聚合的父鏈達(dá)到平衡時(shí)，在父鏈中的Li組之間的轉(zhuǎn)移，其中，允許父鏈被分解為k個(gè)小的受限鏈且可以獨(dú)立求解，由此解得的受限分布STi可以通過C的穩(wěn)態(tài)分布加以組合構(gòu)造出父鏈的穩(wěn)態(tài)分布 πT。

對(duì)于計(jì)算πT而言，其數(shù)值求解過程并非高效，原因在于要獲得受限分布STi需要計(jì)算隨機(jī)補(bǔ)，但是隨機(jī)補(bǔ)Si=Gii+Gi*（I-G*i）-1G*i中包含了計(jì)算成本較高的求逆運(yùn)算。解決這一問題可以對(duì)受限分布進(jìn)行一定程度的近似，具體包括：1）估計(jì)出隨機(jī)補(bǔ)Si，計(jì)算這些估計(jì)的分布以得到近似設(shè)限分布，得到近似聚合轉(zhuǎn)移矩陣，利用精確聚合定理計(jì)算πT的近似值；2）忽略隨機(jī)補(bǔ)，直接對(duì)設(shè)限分布STi進(jìn)行估計(jì)。

3 迭代聚合更新

迭代聚合是一種求解近解耦馬爾可夫鏈的算法[11-12]，假設(shè)某個(gè)不可約馬爾科夫鏈C的穩(wěn)態(tài)分布φT=（φ1，φ2，…，φm），對(duì)C進(jìn)行更新，令更新后的鏈的轉(zhuǎn)移概率矩陣和穩(wěn)態(tài)分布分別為G和πT=（π1，π2，…，πn），其中，更新后的G不可約，并且由于更新過程可能會(huì)新增或刪除狀態(tài)以及改變轉(zhuǎn)移概率，m不一定等于n。具體算法包括：將更新后的鏈的狀態(tài)劃分為S= L∪，對(duì)G進(jìn)行重排：

ωT對(duì)應(yīng)于L狀態(tài)的φT中的元素，給出式子C=進(jìn)而利用近似程序計(jì)算出C的穩(wěn)態(tài)分布進(jìn)而得出最后令以將循環(huán)移出不動(dòng)點(diǎn)χT。

迭代聚合更新的優(yōu)點(diǎn)為：當(dāng)使用一個(gè)良好的L-集是，相比于冪法，迭代聚合算法可以帶來明顯的改善，時(shí)間成本有效減少，并且隨著數(shù)據(jù)集規(guī)模的擴(kuò)大而越明顯[13-14]。其次，迭代聚合被用于更新方法時(shí)，在更新使得問題規(guī)模發(fā)生改變的同時(shí)不會(huì)帶來不利后果，因此，迭代聚合算法可以用于同時(shí)處理鏈接和頁(yè)面更新兩類更新的算法。迭代聚合更新的缺點(diǎn)為：首先，迭代聚合更新并不是一種普遍用途的方法，對(duì)于并非近解耦的鏈，迭代聚合更新一般不能獲得良好的運(yùn)行效果[15]。其次，向量χT是一個(gè)不動(dòng)點(diǎn)，如果直接利用χT重啟算法，在后續(xù)的迭代中將在該計(jì)算環(huán)節(jié)復(fù)制出相同的χT。最后，迭代聚合算法的收斂率直接依賴于主隨機(jī)補(bǔ)S=G22+G21（I-G11）-1G12，收斂率完全由S最大的次主特征值所決定。相比于冪法，迭代聚合算法的每次迭代都需要進(jìn)行更多的計(jì)算。

4 結(jié) 論

更新PageRank向量的研究已經(jīng)展現(xiàn)其有效性，研究方法和思路更加追求創(chuàng)新和效率，但是無論近似聚合更新、精確聚合更新、迭代聚合更新，目前的研究都還不盡完善。由于不同算法給出的矩陣彼此之間存在明顯差別，因此未來的研究工作可以將多個(gè)相互獨(dú)立的算法的結(jié)果加以融合。

[1]Junghoo Cho，Hector Garcia-Molina.The evolution of the Web and implications for an incremental crawler[C]//In Pro-ceedings of the Twenty-sixth International Conference on Very Large Databases，New York，2000：198-210.

[2]Dennis Fetterly，Mark Manasse.A large-scale study of the evolution of web pages[C]//In The Twelfth International World Wide Web Conference，2003.

[3]Konstantin Avrachenkov and Nelly Litvak[R].The effect of new links on Google PageRank.Technical report，INRIA，2014.

[4]Meyer C D，Shoaf J M.Updating finite Markov chains by using techniquesofgroup matrix inversion [J].Journal of Sta-tistical Computation and Simulation，1980：161-179.

[5]Cho G E，Meyer C D.Comparison of perturbation bounds for the stationary distribution of a Markov chain [J].Linear Algebra and Its Applications，2010：135-155.

[6]Eugene Seneta.Sensivity analysis， ergodicity coefficients and rank-one updates for finite Markov chains [J].In William J.Stewart， Editor，Numerical Solution of Markov chains，1991：121-130.

[7]Meyer C D.Matrix Analysis and Applied Linear Algebra[M].SIAM，Philadelphia，2009.

[8]Steve Chien，Cynthia Dwork.Towards exploiting link evolu-tion[M].In Workshop on Algorithms and Models for the Web Graph，2001.

[9]James H.Aggregation of variables in dynamic systems[J].Infor-mation Processing and Management，2013：111-139.

[10]Meyer C D.Stochastic complementation，uncoupling Markov chains and the theory of nearly reducible systems[J].SIAM Review，1989：240-270.

[11]Stewart W J.Introduction to the Numerical of Markov Chains[M].Princeton University Press， 2004.

[12]楊博，陳賀昌，朱冠宇，等.基于超鏈接多樣性分析的新型網(wǎng)頁(yè)排名算法 [J].計(jì)算機(jī)學(xué)報(bào)，2014（4）：833-847.

[13]Sergey Brin，Lawrence Page.The anatomy of a large-scale hypertextual Web search engine[J]. Computer Networks and ISDN Systems，1998（33）: 105-118.

[14]Ayman Farahat， Thomas Lofaro. Authority rankingsfrom HITS， PageRank， and SALSA: Existence，uniqueness，and effect of initialization [J].SIAM Journal on Scientific Com-puting，2006（27）:1181-1213.

[15]Matthew Richardson，Petro Domingos.The intelligent surfer:Probabilistic combination of link and content inform-ation in PageRank[J].Advances in Neural Information Proc-essing Systems，2002（14）: 1398-1406.

Research on updating PageRank vector

GAO Chen1，GAO Fei-fei2，ZHANG Jia-jian3
（1.Business School of Hohai University，Nanjing 210000，China；2.Institute of Mechanics，Chinese Academy of Sciences，Beijing 100190，China；3.Jiangsu Posts&Telecommunication Planning and Designing Institute Co.Ltd，Nanjing 210000，China）

The score of the page content and the PageRank will require frequent updates，to provide the latest results.How to make it easier to update the PageRank vector in order to make it possible to update more frequently In this paper，the problem of updating the PageRank vector is studied through the analysis of the mathematical content of the update algorithm.Based on the PageRank vector of the hypothesis matrix（Qm×m），we propose a new algorithm based on the three algorithms（φT=（φ1，φ2，…，φm））.Based on the three polymerization update algorithm，we use φTvalue in calculation of G into πT，this paper analyzes the approximate polymerization update，precise polymerization update，iterative aggregation update algorithm，and carries on the analysis to the three update algorithm respective application conditions.

pageRank；approximate polymerization update；precise polymerization update；iterative aggregation update

TN0

：A

：1674－6236（2017）01-0006-03

2016-03-29稿件編號(hào)：201603379

江蘇省社科聯(lián)研究基金（201035）

高 臣（1991—），男，山東泰安人，碩士。研究方向：企業(yè)管理、技術(shù)經(jīng)濟(jì)。