PageRank 大規模實現中的存儲問題研究

史倩，張家健，張偉

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

PageRank 大規模實現中的存儲問題研究

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

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

基于PageRank模型擴展到網絡大小的規模時會面臨諸如如何存儲矩陣、PageRank的解的精度、收斂準則、懸掛節點如何處理等問題，本文通過對鏈接分析算法的數學內容分析，研究了PageRank部分的數學元素的存儲問題、懸掛結點以及后退按鈕建模的算法和優缺點，在此基礎上，對壓縮鄰接鏈表信息的兩種方法進行對比分析，總結出不同方法的使用條件。選擇新的算法以恢復每個懸掛結點各自的評分并去除排名中的有偏性，并對后退按鈕建模的回彈模型進行分析。

PageRank；存儲問題；懸掛結點；后退按鈕建模

PageRank模型擴展到網絡大小的規模時會面臨諸如如何存儲矩陣、PageRank的解的精度、收斂準則、懸掛節點如何處理等問題。搜索引擎需要巨量的存儲設施，以將網頁及其位置、倒排索引和圖像索引、內容評分、PageRank評分以及超鏈接圖等信息加以存檔。同時，開始進行PageRank的大規模實現時，必須在設計方面做出決策以確定如何處理懸掛結點問題，與懸掛結點相關的便是后退按鈕的問題，這些問題得到研究者越來越多的重視，并從不同研究角度給出了有效的研究方法。

表1　PageRank問題的存儲需求

1　存儲問題

設計表1中的項目以計算PageRank向量，其中nnz（H）是H中的非零元素的個數，是懸掛結點的個數，而n是網絡圖中網頁的數量。當個性化向量vT為均勻分布向量（vT= eT/n）時，其存儲不需要任何空間。以平均計算，每個頁面包含約10條出鏈，因此nnz（H）約為10 n，由此可知表1所開列的項目中，稀疏的超鏈接矩陣H需要最大的存儲空間。

進一步分析的存儲問題，對于萬維網的小規模子集，當H矩陣能夠被存放在主存中時，PageRank向量的計算可以用常規方式來計算。但是，當H矩陣不能被容納在主存中時，當一個大的超鏈接矩陣超出了機器的內存容量時，可以采取如下方法：1）對所需的數據進行壓縮，使得數據的壓縮表達能夠被容納在主存中，然后實現一個應用于壓縮表達上的PageRank的改進版本；2）保持數據的未壓縮形式不變，進而專門針對大規模未壓縮數據計算的高效實現開發出I/O。當超鏈接矩陣H是中等網絡規模并且能夠被容納在主存時，1）對于隨機上網者模型，H矩陣可以被分解為對應于結點出度的對角陣D的逆與元素值為0或1的鄰接矩陣兩者的乘積。首先，進行簡單的分解H=D-1L以節約存儲空間，其中，當i為非懸掛結點時［D-1］ii=1/dii，否則為0。可知，與存放nnz（H）個雙精度浮點型的實數相比，可以存儲n個整數和nnz（H）個整數，此時整數比雙精度浮點數需要的空間更少；其次，H=D-1L減少了每次PageRank冪法迭代中的計算量，此時的冪法迭代以如下方式進行：

其中，計算量最大的部分是向量-矩陣乘法π（k）TH，需要nnz（H）次乘法和nnz（H）次加法。利用向量diag（D-1），π（k）TH的計算可以按π（k）TD-1L=（π（k）T）.*（diag（D-1））L的方式完成，其中.*表示兩個向量的逐元素乘法。第一個部分（xT）.*（diag（D-1））需要n次乘法。由于L是一個鄰接矩陣，（π（k）T）.*（diag（D-1））L只需要n次乘法和nnz（H）次加法；2）對于智能上網者模型，可以使用行壓縮存儲或列壓縮存儲等其他的緊湊存儲方案，需要注意的是，對于每種壓縮格式，在節省了一定存儲空間的同時，在進行矩陣運算時需要更多額外的計算量［1］。

PageRank模型將H或L矩陣存放于矩陣各列中的元素所對應的鄰接鏈表中［2］，為了計算PageRank向量，PageRank冪法需要在每次迭代k中計算向量-矩陣乘法π（k）TH［3］，因此，需要加速算法以實現對矩陣H或L的列的迅速訪問［4］。

壓縮鄰接鏈表信息的方法：

1）間隔法。間隔法利用了通過超鏈接連在一起的文檔之間所具有的局域性，其中，局域性所指向的事實即通過某個超鏈接聯系起來的原頁面和目標頁面，其頁面序數通常是比較接近的［5］。編號100的頁面常常擁有一些序數接近的入鏈，這些入鏈更可能來自頁面112、113、116和117，并非來自頁面924和4 931 010。由此可知，頁面100對應的鄰接鏈表中的信息可按以下方式存儲，如表2。

表2　頁面100對應的鄰接鏈表

頁面100的第一個入鏈頁面的編號——即112——被保存下來，而在它之后，僅保存后續的入鏈頁面編號與前一個頁面編號之間的間隔。由于這些間隔通常都是較小的整數，因此保存它們只需要較少的存儲時間。

2）壓縮方法。壓縮方法利用網頁之間的相似性，如果頁面Pi和Pj具有相似的鄰接鏈表，那么就可以利用鄰接鏈表Pi中的項來表示鄰接鏈表Pj，從而達到壓縮的目的此時Pi稱為Pj的參考頁。例如圖1。

圖1　鄰接鏈表Pi對鄰接鏈表Pj的表示

Pj頁面的鄰接鏈表與Pi的鄰接鏈表相似，兩個頁面均具有指向頁面5，12，101和190的出鏈，因此，需要構造一個有1和0構成的共享向量和一個整型的差異向量以利用該重復性。二值得共享向量的大小和Pi的鄰接鏈表的大小相同，如果的Pi鄰接鏈表中的第k個條目出現在了Pj的鄰接鏈表中，則共享向量的第k個位置上的值為1；參考編碼中的第二個向量則是Pj的鄰接鏈表中沒有出現Pi的鄰接鏈表中的那些條目所構成的鏈表。需要指出，Pj的共享向量的存儲開銷將少于Pj的鄰接鏈表，因此，壓縮方法的有效性依賴于差異頁面的多少。如果Pi和Pj的鄰接鏈表中頁面的重復率很高，則差異向量將很短，Pi有可能是Pj的一個有效參考頁面。但是需要注意，為索引中的每個頁面都確定一個參考頁面的難度較高［6-7］。

2　懸掛結點算法

對于大部分的懸掛結點而言，其相似度較高，其對應的H以及S和G中的行是相似的［8］。同時，一旦隨機上網者到達了一個懸掛結點，那么其行為方式總是相同的，不論其是處于哪個特定的懸掛結點，該上網者總是立即跳轉到一個新的頁面［9］。其中，如果vT=eT/T，即為隨機跳轉，如果vT≠eT/T，則根據相應的跳轉概率跳轉。由此可知，如果把所有單個的懸掛結點匯聚成一個新的轉跳狀態，將極大縮小懸掛結點問題的規模，特別是當懸掛結點所占的比例很高時。但是，當系統較小時該做法會面臨新的問題：1）排名評分只能對非懸掛頁面加上一個歸總的跳轉狀態來給出；2）這個較小的排名集合是有偏的。在此本文選擇新的算法以恢復每個懸掛結點各自的評分并去除排名中的有偏性［10］。

假設H的行和列的下標均被重新排序，使得對應于懸掛結點的行處在矩陣的底部。

該式中，ND是非懸掛結點的集合，而D是懸掛結點的集合。此時，稀疏線性系統形式πT（I-αH）=vT，且πT=X/XTe中的系數矩陣變為：

它的逆為：

因此，未歸一化的PageRank向量的πT=vT（I-αH）-1可以寫為:

該式中，個性化向量vT被相應地劃分為非懸掛部分（）和懸掛部分（）。

該計算PageRank向量的算法利用了懸掛結點調整的秩一結構以及可聚性，從而可以僅使用網絡中的非懸掛部分來完成計算，該算法較為簡單。對于在H的子矩陣中找到更多的0T行，可以通過將定位全零行的過程遞歸地重復應用于H的趨于小的子矩陣之上，直至獲得一個沒有任何全零行的子矩陣位置。小的子系統XT1（I-αH）=vT可使用直接法或迭代大求解。該懸掛結點PageRank算法具有漸進收斂率，由于其運行于一個規模較小的問題之上，因此所需的時間少于標準的PageRank冪法。

3　后退按鈕建模

與懸掛結點相關的便是后退按鈕的問題。對網絡瀏覽器上的后退按鈕進行建模，可以在PageRank模型中對后退按鈕進行有限度使用，同時保持馬爾可夫框架［11-12］。在整個模型中，一旦隨機上網者到達懸掛結點，他將立刻回到他所來自的那個頁面，這個回彈式的特性盡在懸掛結點上對后退按鈕進行建模，因此需要為指向每個懸掛結點的每條入鏈增加一個新的結點［13-14］，可以通過以下例子分析該回彈模型，圖2對應的超鏈接矩陣H為：

圖2　后退按鈕模型中原來的6結點圖

圖3　后退按鈕模型中原來的6結點圖

對每個指向懸掛結點的入鏈，生成一個回彈結點。將有nnz（H12）個這樣的回彈結點，而不是懸掛結點集合中的個結點。如果每個懸掛結點都有不止一條入鏈，在存在很多懸掛結點的前提下，將極大增加矩陣的規模［15］?；貜棾溄泳仃嚨姆謮K形式：

4　結論

PageRank模型擴展到網絡大小的規模時面臨的問題的研究已經展現其有效性，研究方法和思路更加追求創新和效率，但是無論存儲矩陣、PageRank的解的精度、收斂準則、懸掛節點等問題，目前的研究都還不盡完善。由于不同算法給出的列表彼此之間存在明顯差別，因此未來的研究工作可以將多個相互獨立的算法的結果加以融合。

［1］Barrett R，Berry M.Templates for the Solution of Linear Systems:Building Blocks for Iterative Methods［M］.SIAM，Philadephia，2nd edition，1994.

［2］Sriram Raghavan and Hector Garcia-Molina.Compressing the graph structure of the Web［M］.In Proceedings of the IEEE Conference on Data Compression，2001：211-215.

［3］Cleve B.Moler.Numerical Computing with MATLAB［M］.SIAM，2004.

［4］Sriram Raghavan and Hector Garcia-Molina.Representing web graphs［C］11In Proceedings of the 19th IEEE Conference on Data Engineering，Bangalore，India，2003.

［5］Krishna Bharat，Andrei Broder.The connectivity server:Fast access to linkage information on the Web［C］//In The Seventh WorldWideWebConference，Australia，1998：467-51.

［6］Paolo Boldi and Sebasiano Vigna.The WebGraph framework:Codes for the World Wide Web［R］.Technical Report 291-96，Universita di Milano，Dipartimento di Scienze dell' Informazione Engineering，2003.

［7］Paolo Boldi and Sebasiano Vigna.The WebGraph framework: Compression techniques［C］11 In The Thirteenth International World Wide Web Conference，New York，2004：590-610.

［8］William J.Stewart.Introduction to the Numerical Solution of Markov Chains［M］.Princeton University Press，2014.

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

［10］Chris Pan-Chi Lee and Gene H.Golub.A fast two-stage algorithm for computing PageRank and its extensions［R］.Technical Report SCCM-2009-15，Scientific Computation and Computational Mathematics，Stanford University，2009.

［11］Ronald Fagin and Anna R.Random walks with”back buttons”［C］//In 32nd ACM Symposium on Theory of Computing，2000.

［12］GraceE.ChoandCarlD.Meyer.Aggregation/ disaggregation errors for nearly uncoupled Markov chains［R］.Technical report，NCSU Tech.Report.2013.

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

［14］Michael W.Berry and Murray Browne.Understanding Search Engines:Mathematical Modeling and Text Retrieval［J］.SIAM，Philadelphia，2005（16）:78-93.

［15］PaoloBoldiandSebastianoVigna.TheWebGraph framework II.Codes for the World Wide Web［C］//Technical Report286-03，UniversitadiMilano，Dipartimento diScienze dell'Informazine Engineering，2013.

The study of PageRank mass storage problems

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

PageRank model is expanded to the size of the network size when faced with how to store solution accuracy，convergence criteria of the matrix，hanging nodes.Search engine will require a huge amount of storage facilities to archive the web and its location，inverted index and image index，content，grading，PageRank score and hyperlink graph information.At the same time，PageRank large-scale implementation must make decisions on design to determine how to deal with hanging nodes problem.In this paper，we study mathematics content of link analysis algorithm and the mathematical elements PageRank part of storage，hanging nodes and modeling problem of the back button.

PageRank；storage problem；hanging nodes；modeling problem of the back button

TN0

A

1674－6236（2016）17-0004-03

2016-02-26稿件編號：201602157

江蘇省社科聯研究基金（201035）；中央高校基本科研業務費項目（2010B10714）

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