加速PageRank計(jì)算的方法研究

史 倩，張家健，張 偉

（1.河海大學(xué) 商學(xué)院，江蘇 南京210000；2.江蘇省郵電規(guī)劃設(shè)計(jì)院有限公司 江蘇 南京210000）

加速PageRank計(jì)算的方法研究

史 倩1，張家健2，張 偉2

（1.河海大學(xué) 商學(xué)院，江蘇 南京210000；2.江蘇省郵電規(guī)劃設(shè)計(jì)院有限公司 江蘇 南京210000）

網(wǎng)絡(luò)矩陣的規(guī)模以及稀疏性導(dǎo)致了對(duì)求解方法的限制，并使得冪法占據(jù)了主導(dǎo)地位。但是冪法的收斂速度是緩慢的，尤其在網(wǎng)絡(luò)規(guī)模的矩陣上運(yùn)行的每次冪法迭代的時(shí)間和成本是高昂的。因此，其他加速PageRank計(jì)算的方法逐漸得到研究者的重視。文中首先對(duì)布爾搜索引擎、向量空間模型引擎、概率模型搜索引擎、元搜索引擎等基本搜索引擎模型進(jìn)行綜述，總結(jié)各基本搜索引擎模型的特征和優(yōu)缺點(diǎn)。文中立足于加速PageRank計(jì)算的方法研究，并總結(jié)出自適應(yīng)冪法、外插方法、BlockRank聚合方法的特征和優(yōu)缺點(diǎn)。

PageRank；自適應(yīng)冪法；外插方法；聚合方法

網(wǎng)絡(luò)矩陣的規(guī)模以及稀疏性導(dǎo)致了對(duì)求解方法的限制，并使得冪法占據(jù)了主導(dǎo)地位。但是冪法的收斂速度是緩慢的，尤其在網(wǎng)絡(luò)規(guī)模的矩陣上運(yùn)行的每次冪法迭代的時(shí)間和成本是高昂的。減少迭代方法計(jì)算負(fù)荷的途徑包括減少每次迭代中的計(jì)算量或者減少總的迭代次數(shù)，但是，兩種途徑的目標(biāo)存在明顯對(duì)立，即減少迭代次數(shù)會(huì)導(dǎo)致每次迭代中計(jì)算量的上升，反之亦然。因此，保持該額外計(jì)算量為最小值，那么加速方法即為可行。本文立足于加速PageRank計(jì)算的方法研究，包括自適應(yīng)冪法、外插方法、BlockRank聚合方法。

1　基本模型

如何準(zhǔn)確并快速地在巨量的信息世界中尋找到對(duì)自己有價(jià)值的內(nèi)容？當(dāng)然這離不開(kāi)搜索引擎，影響搜索引擎有效性的因素有許多，但從根本上說(shuō)，關(guān)鍵在于搜索引擎自身的鏈接算法設(shè)計(jì)。網(wǎng)絡(luò)信息檢索是在世界上最大且相互鏈接的文檔集中進(jìn)行的搜索，大多數(shù)搜索引擎依賴(lài)于以下基本模型中的一種或者多種：

1）布爾搜索引擎

信息檢索的布爾模型是最早最簡(jiǎn)單的檢索方法之一，它使用嚴(yán)格匹配來(lái)將文檔與用戶的查詢(xún)進(jìn)行比對(duì)。該模型經(jīng)過(guò)改良的派生方法為大多數(shù)圖書(shū)館所使用。信息檢索的布爾模型工作原理是考察在文檔中有哪些關(guān)鍵詞出現(xiàn)了或未曾出現(xiàn)，并據(jù)此判定文檔與檢索相關(guān)或無(wú)關(guān)［1］。但是標(biāo)準(zhǔn)的布爾引擎無(wú)法返回那些語(yǔ)義相關(guān)但關(guān)鍵詞未被包括在原始查詢(xún)中的文檔。許多布爾搜索引擎要求用戶熟悉布爾運(yùn)算符以及引擎的特殊語(yǔ)法。布爾模型的各種變體構(gòu)成了許多搜索引擎的基礎(chǔ)，其優(yōu)點(diǎn)包括：建立并編寫(xiě)布爾引擎是直接的；查詢(xún)處理迅速，可以采用并行方式對(duì)文檔的關(guān)鍵詞文件進(jìn)行快速掃描；布爾模型可以很好地?cái)U(kuò)展到大的文檔集［2］。

2）向量空間模型引擎

該模型中，向量空間模型被用于避開(kāi)前述的若干信息檢索難題［3］。向量空間模型將文本數(shù)據(jù)變換為數(shù)值向量和矩陣，使用矩陣分析方法來(lái)發(fā)現(xiàn)文檔集之中的關(guān)鍵特征和聯(lián)系。一旦成立，即當(dāng)相鄰迭代所得的值之間的差別足夠小時(shí)，便可鎖定元素i，其中ε是一個(gè)微觀容許限，自適應(yīng)PageRank方法會(huì)鎖定該部分頁(yè)面，并且在之后的迭代中不再計(jì)算該部分頁(yè)面。

1.2自適應(yīng)冪法優(yōu)缺點(diǎn)分析

自適應(yīng)冪法的優(yōu)點(diǎn)為：該算法對(duì)PageRank向量的計(jì)算進(jìn)行了中等程度的提速，通過(guò)嘗試減少冪法在每次迭代中的計(jì)算量，自適應(yīng)算法為PageRank的加速計(jì)算做出了具有實(shí)用意義的貢獻(xiàn)；自適應(yīng)冪法的缺點(diǎn)為：盡管自適應(yīng)冪法在若干數(shù)據(jù)集上表明它存在收斂，但是依然存在問(wèn)題。首先，收斂性并未得到證明，算法可能收斂也可能不收斂。其次，即使存在收斂，最后的答案也有可能存在錯(cuò)誤。因?yàn)樵诖_定鎖定的決策過(guò)程中，該算法僅考慮了短期的動(dòng)態(tài)行為，所以并不清楚算法最終是否會(huì)收斂到真實(shí)的PageRank值上，或者收斂在某個(gè)比較粗略的估值上。最后，近解耦鏈的每個(gè)簇都會(huì)顯示出短期的穩(wěn)定性進(jìn)而經(jīng)過(guò)一段時(shí)間到達(dá)全局平衡點(diǎn)，最終的全局平衡點(diǎn)常常不具有類(lèi)似于短期平衡點(diǎn)的性質(zhì)，這就意味著自適應(yīng)方法可能會(huì)過(guò)早地停止，并對(duì)耦鏈給出一個(gè)不精確的答案。

2　外插方法及其優(yōu)缺點(diǎn)分析

該算法旨在減少冪法的迭代次數(shù)，冪法的期望迭代次數(shù)由次主特征所決定。假設(shè)G可對(duì)角化，并且。冪法的迭代如下：

式中Xi和Yi分別是G對(duì)應(yīng)于λi的右特征向量和左特征向量，且γi=π（0）TXi。該式子表明，λK2γ2YT2在冪法中一直發(fā)揮作用，πT一直存在著，直到λK2→0，而當(dāng)較大時(shí)，

冪法計(jì)算就需要大量時(shí)間。外插方法可以解決這一問(wèn)題，即：

在該式中，（*）2表示對(duì)向量（*）逐元求平方。同理，如果λ2和λ3成復(fù)共軛，那么可以將其擱置，進(jìn)行二次外插。

外插方法的優(yōu)點(diǎn)為：外插方法可以實(shí)現(xiàn)中等程度的加速，二次外插能夠以最少的額外計(jì)算將PageRank的計(jì)算時(shí)間有效縮短。外插方法的缺點(diǎn)為：首先，由于外插需要額外計(jì)算并保存接下去兩次迭代的數(shù)據(jù)，因此它應(yīng)該是每隔一段時(shí)間才使用一次。如果λ2和λ3成復(fù)共軛，即些高級(jí)向量空間模型能夠訪問(wèn)文檔集中隱含的語(yǔ)義結(jié)構(gòu)［4］。該模型的優(yōu)點(diǎn)包括：相關(guān)性評(píng)分，通過(guò)給每個(gè)文檔賦予一個(gè)0到1之間的數(shù)，向量空間模型允許進(jìn)行文檔的部分匹配查詢(xún)。該數(shù)值可以被解釋為文檔與查詢(xún)之間的相關(guān)似然度。進(jìn)而檢索到的文檔集可以根據(jù)相關(guān)程度進(jìn)行排序。按照這一方式，向量空間模型以有序的列表返回結(jié)果文檔，按照相關(guān)性的分?jǐn)?shù)排序，返回的第一個(gè)文檔被認(rèn)為是與用戶查詢(xún)最為相關(guān)者，一些向量空間搜索引擎以相似度比例的形式給出相關(guān)性的評(píng)分。該模型的缺點(diǎn)為：必須計(jì)算每個(gè)文檔和查詢(xún)之間的距離度量，隨著文檔集的增大，矩陣分解的開(kāi)銷(xiāo)將使模型不再具有可行性［5］；向量空間模型無(wú)法很好地?cái)U(kuò)展，它僅局限于小文檔集。

3）概率模型搜索引擎

概率模型試圖對(duì)用戶找到某個(gè)特定相關(guān)文檔的概率進(jìn)行估計(jì)，檢索得到的文檔根據(jù)它們的相關(guān)幾率進(jìn)行排名。概率模型以遞歸的方式運(yùn)行，并要求算法能夠猜測(cè)得到初始參數(shù)，進(jìn)而逐次嘗試改善這一初始猜測(cè)，以得到最終的相關(guān)幾率的排位［6］。概率模型的缺點(diǎn)為：構(gòu)建和編程難度較大，因此限制了其擴(kuò)展性。同時(shí)該模型要求做出若干不現(xiàn)實(shí)的假設(shè)。該模型的優(yōu)點(diǎn)在于概率框架可以自然地納入先驗(yàn)偏好，可以做到針對(duì)單個(gè)用戶的偏好調(diào)整搜索結(jié)果。

4）元搜索引擎

該模型將以上3種模型相結(jié)合，其工作原理是用一個(gè)搜索引擎來(lái)搜索可以完成任務(wù)時(shí)，用兩個(gè)或以上搜索引擎搜索的效果更顯著。一個(gè)搜索引擎可能在某個(gè)任務(wù)上十分出色，而第二個(gè)搜索引擎則可能在另一項(xiàng)任務(wù)上表現(xiàn)好于第一個(gè)搜索引擎。元搜索引擎可以充分利用許多單獨(dú)的搜索引擎各自具有的最佳特性，可以同時(shí)將一個(gè)查詢(xún)發(fā)送至數(shù)個(gè)搜索引擎，并將所有這些搜索引擎的結(jié)果以一個(gè)統(tǒng)一的列表返回。元搜索引擎可以應(yīng)用于某個(gè)特定學(xué)科內(nèi)的搜索［7］。

1.1自適應(yīng)冪法

PageRank的目的是計(jì)算G的穩(wěn)態(tài)向量πT，從技術(shù)分析可知，迭代求冪π（K）T，使得‖π（K）T-π（K-1）T‖1<τ，其中，τ是一個(gè)可接受的收斂判據(jù)。在整個(gè)迭代過(guò)程中，有兩種方法可以得出每次迭代π（K）T與最終的解πT之間的距離：1）宏觀的視角分析，計(jì)算‖π（K）T-πT‖1，并從宏觀的角度考察當(dāng)前迭代π（K）T與πT之間的距離，使用以上范數(shù)，各個(gè)元素位置上的誤差被歸總為一個(gè)單一的標(biāo)量，進(jìn)而可以得出總誤差［8］。標(biāo)準(zhǔn)的冪法在每次迭代中采取該宏觀視角，利用總誤差‖π（K）T-π（K-1）T‖1來(lái)測(cè)試收斂情況，其中，頁(yè)面以宏觀的視角考慮收斂的標(biāo)準(zhǔn)冪法不能迅速的收斂到頁(yè)面中所屬的PageRank值。2）微觀的視角分析，測(cè)量?jī)蓚€(gè)向量的各個(gè)單獨(dú)元素在每次迭代中，π（K）T與πi之間的距離。其中，大多數(shù)頁(yè)面都可以迅速收斂到它們最終的PageRank值，有些頁(yè)面會(huì)比其他頁(yè)面更快地收斂到它們的PageRank值［9］。值得注意，由于一小部分的頁(yè)面需要更長(zhǎng)的時(shí)間才能收斂到最終的PageRank值，因此冪法的運(yùn)行時(shí)間被延時(shí)。隨著PageRank向量的各個(gè)元素逐漸收斂，一時(shí)，該方法將占用較高的時(shí)間成本。其次，雖然二次外插可以有效減少計(jì)算時(shí)間，但是二次外插的計(jì)算代價(jià)高昂，只能每隔一段時(shí)間使用一次。

3　BlockRank聚合方法及優(yōu)缺點(diǎn)分析

BlockRank聚合方法以實(shí)現(xiàn)兩個(gè)加速為目標(biāo)，即減少迭代次數(shù)以及每次迭代中的計(jì)算量，它將萬(wàn)維網(wǎng)的不同部分依據(jù)主站而歸總到一起。在BlockRank開(kāi)始時(shí)，它首先獲取網(wǎng)絡(luò)圖，然后將其壓縮為一個(gè)主站圖。主站是高層網(wǎng)頁(yè)，其下鏈接則是主站間的鏈接，他們將不同的主站鏈接起來(lái)，在全局的主站圖中，內(nèi)部鏈接可以被忽略。當(dāng)PageRank模型應(yīng)用于該主站圖是，就會(huì)輸出一個(gè)HostRank向量。主站I的HostRank排名給出了該主站的相對(duì)重要性。由于HostRank問(wèn)題規(guī)模以原來(lái)的PageRank的問(wèn)題小，由此可知，單個(gè)頁(yè)面的重要性，而不是單個(gè)主站的重要性。為了獲取全局PageRank向量，可以先計(jì)算每個(gè)獨(dú)立站點(diǎn)內(nèi)的頁(yè)面的PageRank向量，這一過(guò)程僅使用內(nèi)部鏈接，PageRank模型可以被應(yīng)用于高層網(wǎng)頁(yè)的每個(gè)主站。由此，可得到一個(gè)全局的為主站的數(shù)量，以及個(gè)局部PageRank向量，每個(gè)向量的大小為，其中為主站Hi中的頁(yè)面數(shù)量。通過(guò)將主站Hi的局部PageRan向量乘以該主站的訪問(wèn)概率即可得出全局PageRan向量的近似值，訪問(wèn)概率可由HostRank向量的第i個(gè)元素給出［10-11］。

可以利用近解耦鏈分析BlockRank方法的聚合原理，在此先給出7結(jié)點(diǎn)的圖。由于結(jié)點(diǎn)1，2，3和7之間有強(qiáng)內(nèi)部關(guān)聯(lián)，可將其視為主站1；而結(jié)點(diǎn)4，5和6則構(gòu)成了主站2。BlockRank算法將這個(gè)7結(jié)點(diǎn)的圖聚合為一個(gè)更小的2結(jié)點(diǎn)的主站圖，與主站圖相關(guān)聯(lián)的轉(zhuǎn)移矩陣為：

取值α=0.9和υT=（0.5 0.5），可知，該主站圖的HostRank向量即主站圖的谷歌矩陣的穩(wěn)態(tài)向量（0.367 6 0.632 4），即在36.76%的時(shí)間內(nèi)，隨機(jī)瀏覽者均會(huì)訪問(wèn)主站1下的某個(gè)狀態(tài)，即網(wǎng)頁(yè)1，2，3和7。

圖1　7個(gè)網(wǎng)頁(yè)所構(gòu)成的網(wǎng)絡(luò)近解耦圖

計(jì)算每個(gè)主站的局部PageRank向量，對(duì)主站1，超鏈接矩陣為：

在此過(guò)程中，求取H1時(shí)僅使用了主站內(nèi)的鏈接，而所有主站之間的鏈接均被忽略，即3→4被忽略。對(duì)于α=0.9和VT=（0.250.250.250.25），主站1的局部PageRank向量為（0.167 10.317 50.348 30.167 1）。進(jìn)一步分析，主站2的局部超鏈接矩陣為：

而主站2的局部PageRank向量為（1/31/31/3）。

最后的去聚合步驟將使用這3個(gè)較小的向量產(chǎn)生一個(gè)1×7階的向量π～T，它近似與精確的PageRank向量πT，其中：

BlockRank聚合方法的優(yōu)點(diǎn)為：首先該方法實(shí)現(xiàn)了兩個(gè)加速為目標(biāo)，即減少迭代次數(shù)以及每次迭代中的計(jì)算量［12］。其次，網(wǎng)絡(luò)鏈在一定程度上是解耦的，因此只要進(jìn)行了適當(dāng)程度的主站聚合，BlockRan聚合方法就能夠良好運(yùn)行，而且對(duì)于近解耦馬爾可夫鏈［13-14］，該方法可以減少計(jì)算穩(wěn)態(tài)向量的工作量；BlockRank聚合方法的缺點(diǎn)為：BlockRank聚合方法得出的結(jié)果是有冪法計(jì)算所得的真實(shí)PageRank向量的一個(gè)近似［15］，因?yàn)樵摲椒ǖ拿恳徊蕉己雎粤四承╂溄樱茨承┯袃r(jià)值的信息在壓縮或聚合的步驟中被丟失。大小的HostRank向量，其中

4　結(jié)　論

盡管不同的加速計(jì)算方法對(duì)加速PageRank計(jì)算提供幫助的這一方面已經(jīng)展現(xiàn)了有效性，但是無(wú)論是自適應(yīng)冪法、外插方法或是BlockRank，目前的研究都還不盡完善，盡管取得了進(jìn)展，但都僅僅只是開(kāi)始而已，如果實(shí)時(shí)個(gè)性化搜索能夠得以實(shí)現(xiàn)，那就必須獲得速度上的極大改進(jìn)，這一改進(jìn)也許通過(guò)創(chuàng)新型的新算法以達(dá)到，或許將當(dāng)前的許多加速方法簡(jiǎn)單地合并為一個(gè)算法而得以實(shí)現(xiàn)。

［1］方永鋒，陳建軍.多狀態(tài)可修復(fù)k/n系統(tǒng)的隨時(shí)間響應(yīng)可靠性研究［J］.高技術(shù)通訊，2016（2）：32-37.

［2］宋濤，基于二次聚類(lèi)和隱馬爾可夫鏈的持卡消費(fèi)行為預(yù)測(cè)［J］.計(jì)算機(jī)應(yīng)用，2016（5）:15-29.

［3］Gerard Salton and Chris Buckley.Introduction to Modern Information Retrieval［M］.McGraw-Hill，New York，2003.

［4］Susan T.Dumais.Improving the retrieval of information from external sources［C］∥ Behavior Research Methods，Instru ments and Computers，1991：221-246.

［5］Carl D.Meyer.Matrix Analysis and Applied Linear Algebra［C］∥SIAM，Philadelphia，2000.

［6］MichaelW.Berry and Murray Browne.Understanding Search Engines:Mathematical Modeling andText Retrieval［J］. SIAM，Philadelphia，2an edition，2005（16）:78-93.

［7］Paolo Boldiand Sebastiano Vigna.TheWebGraph framework II.Codes for the World Wide Web［C］∥ Technical Report 286-03，Universita diMilano，Dipartimento diScienze dell' Informazione Engineering，2013.

［8］Matthew Richardson，Petro Domingos.The intelligent surfer: Probabilistic combination of link and content information in PageRank［J］.Advances in Neural Information Processing Systems，2012（14）:1398-1399.

［9］Sepandar D.Kamvar，Taher H.Haveliwala，Christopher D. Manning，et al.Extrapolationmethods for accelerating PageRank computations［C］∥In Twelfth International World WideWeb Conference，New York，2003.

［10］Grace E.Cho and Carl D.Meyer.Aggregation/disaggregation errors for nearly uncoupled Markov chains［R］.Technical report，NCSU Tech.Report，2013.

［11］William J.Stewart Numerical experimentswith iteration and aggregationfor Markov chains［J］.ORSAJournal on Computing，2011，4（3）:50-336.

［12］Cleve B.Moler.Numerical computing with MATLAB［M］. SIAM，2004.

［13］Grace E.Cho，Carl D.Meyer.Aggregation/disaggregation errors for nearly uncoupled Markov chains［R］.Technical report，NCSU Tech，2013.

［14］William J.Stewart.Introduction to the numerical solution of markov chains［M］.Princeton University Press，2014.

［15］Ilse CF，Ipsen.Convergence analysis of a PageRank updatingalgorithm by Langvilleand Meyer［J］.SIAM Journaln Matrix Analysis and Applications，2006，27（14）：952-967.

Study ofmethod about accelerating PageRank calculation

SHIQian1，ZHANG Jia-jian2，ZHANGWei2
（1.Business School of Hohai University，Nanjing 210000，China；2.Jiangsu Posts&Telecommunication Planning and Designing Institute Co.Ltd，Nanjing 210000，China）

Scale and sparse network matrix led to restrictions on solvingmethod，andmakes the powermethod to occupy the dominantposition.Butconvergence speed is slow，especially in the network every time powermethod to run on the size of the matrix iterative time and cost is high.Therefore，other accelerate PageRank calculationmethod gradually got the attention of the researchers.This paper summarizes the basic characteristics and advantages and disadvantages of search enginemodel，including the Boolean search engine，vector spacemodel engines，search engines，metasearch engines.Finally，this paper analyzes the accelerate the PageRank calculation method of study，Summed up the characteristics and advantages and disadvantages including adaptive powermethod，extrapolationmethod，polymerizationmethod.

PageRank；adaptive power law；extrapolationmethod；polymerizationmethods

TN98

A

1674-6236（2016）19-0004-03

2016-02-24稿件編號(hào)：201602117

江蘇省社科聯(lián)研究基金（201035）；中央高校基本科研業(yè)務(wù)費(fèi)項(xiàng)目（2010B10714）

史 倩（1987—），女，江蘇南京人，碩士。研究方向：企業(yè)管理、技術(shù)經(jīng)濟(jì)。