史 倩，張家健，張 偉

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

加速PageRank計算的方法研究

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

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

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

PageRank；自適應冪法；外插方法；聚合方法

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

1　基本模型

如何準確并快速地在巨量的信息世界中尋找到對自己有價值的內容？當然這離不開搜索引擎，影響搜索引擎有效性的因素有許多，但從根本上說，關鍵在于搜索引擎自身的鏈接算法設計。網絡信息檢索是在世界上最大且相互鏈接的文檔集中進行的搜索，大多數搜索引擎依賴于以下基本模型中的一種或者多種：

1）布爾搜索引擎

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

2）向量空間模型引擎

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

1.2自適應冪法優(yōu)缺點分析

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

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

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

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

冪法計算就需要大量時間。外插方法可以解決這一問題，即：

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

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

3）概率模型搜索引擎

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

4）元搜索引擎

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

1.1自適應冪法

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

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

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

可以利用近解耦鏈分析BlockRank方法的聚合原理，在此先給出7結點的圖。由于結點1，2，3和7之間有強內部關聯，可將其視為主站1；而結點4，5和6則構成了主站2。BlockRank算法將這個7結點的圖聚合為一個更小的2結點的主站圖，與主站圖相關聯的轉移矩陣為：

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

圖1　7個網頁所構成的網絡近解耦圖

計算每個主站的局部PageRank向量，對主站1，超鏈接矩陣為：

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

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

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

BlockRank聚合方法的優(yōu)點為：首先該方法實現了兩個加速為目標，即減少迭代次數以及每次迭代中的計算量［12］。其次，網絡鏈在一定程度上是解耦的，因此只要進行了適當程度的主站聚合，BlockRan聚合方法就能夠良好運行，而且對于近解耦馬爾可夫鏈［13-14］，該方法可以減少計算穩(wěn)態(tài)向量的工作量；BlockRank聚合方法的缺點為：BlockRank聚合方法得出的結果是有冪法計算所得的真實PageRank向量的一個近似［15］，因為該方法的每一步都忽略了某些鏈接，即某些有價值的信息在壓縮或聚合的步驟中被丟失。大小的HostRank向量，其中

4　結　論

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

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

［2］宋濤，基于二次聚類和隱馬爾可夫鏈的持卡消費行為預測［J］.計算機應用，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稿件編號：201602117

江蘇省社科聯研究基金（201035）；中央高?；究蒲袠I(yè)務費項目（2010B10714）

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