PageRank 大規(guī)模實(shí)現(xiàn)中的存儲(chǔ)問題研究

史倩，張家健，張偉

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

PageRank 大規(guī)模實(shí)現(xiàn)中的存儲(chǔ)問題研究

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

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

基于PageRank模型擴(kuò)展到網(wǎng)絡(luò)大小的規(guī)模時(shí)會(huì)面臨諸如如何存儲(chǔ)矩陣、PageRank的解的精度、收斂準(zhǔn)則、懸掛節(jié)點(diǎn)如何處理等問題，本文通過對(duì)鏈接分析算法的數(shù)學(xué)內(nèi)容分析，研究了PageRank部分的數(shù)學(xué)元素的存儲(chǔ)問題、懸掛結(jié)點(diǎn)以及后退按鈕建模的算法和優(yōu)缺點(diǎn)，在此基礎(chǔ)上，對(duì)壓縮鄰接鏈表信息的兩種方法進(jìn)行對(duì)比分析，總結(jié)出不同方法的使用條件。選擇新的算法以恢復(fù)每個(gè)懸掛結(jié)點(diǎn)各自的評(píng)分并去除排名中的有偏性，并對(duì)后退按鈕建模的回彈模型進(jìn)行分析。

PageRank；存儲(chǔ)問題；懸掛結(jié)點(diǎn)；后退按鈕建模

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

表1　PageRank問題的存儲(chǔ)需求

1　存儲(chǔ)問題

設(shè)計(jì)表1中的項(xiàng)目以計(jì)算PageRank向量，其中nnz（H）是H中的非零元素的個(gè)數(shù)，是懸掛結(jié)點(diǎn)的個(gè)數(shù)，而n是網(wǎng)絡(luò)圖中網(wǎng)頁的數(shù)量。當(dāng)個(gè)性化向量vT為均勻分布向量（vT= eT/n）時(shí)，其存儲(chǔ)不需要任何空間。以平均計(jì)算，每個(gè)頁面包含約10條出鏈，因此nnz（H）約為10 n，由此可知表1所開列的項(xiàng)目中，稀疏的超鏈接矩陣H需要最大的存儲(chǔ)空間。

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

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

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

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

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

表2　頁面100對(duì)應(yīng)的鄰接鏈表

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

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

圖1　鄰接鏈表Pi對(duì)鄰接鏈表Pj的表示

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

2　懸掛結(jié)點(diǎn)算法

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

假設(shè)H的行和列的下標(biāo)均被重新排序，使得對(duì)應(yīng)于懸掛結(jié)點(diǎn)的行處在矩陣的底部。

該式中，ND是非懸掛結(jié)點(diǎn)的集合，而D是懸掛結(jié)點(diǎn)的集合。此時(shí)，稀疏線性系統(tǒng)形式πT（I-αH）=vT，且πT=X/XTe中的系數(shù)矩陣變?yōu)椋?/p>

它的逆為：

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

該式中，個(gè)性化向量vT被相應(yīng)地劃分為非懸掛部分（）和懸掛部分（）。

該計(jì)算PageRank向量的算法利用了懸掛結(jié)點(diǎn)調(diào)整的秩一結(jié)構(gòu)以及可聚性，從而可以僅使用網(wǎng)絡(luò)中的非懸掛部分來完成計(jì)算，該算法較為簡(jiǎn)單。對(duì)于在H的子矩陣中找到更多的0T行，可以通過將定位全零行的過程遞歸地重復(fù)應(yīng)用于H的趨于小的子矩陣之上，直至獲得一個(gè)沒有任何全零行的子矩陣位置。小的子系統(tǒng)XT1（I-αH）=vT可使用直接法或迭代大求解。該懸掛結(jié)點(diǎn)PageRank算法具有漸進(jìn)收斂率，由于其運(yùn)行于一個(gè)規(guī)模較小的問題之上，因此所需的時(shí)間少于標(biāo)準(zhǔn)的PageRank冪法。

3　后退按鈕建模

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

圖2　后退按鈕模型中原來的6結(jié)點(diǎn)圖

圖3　后退按鈕模型中原來的6結(jié)點(diǎn)圖

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

4　結(jié)論

PageRank模型擴(kuò)展到網(wǎng)絡(luò)大小的規(guī)模時(shí)面臨的問題的研究已經(jīng)展現(xiàn)其有效性，研究方法和思路更加追求創(chuàng)新和效率，但是無論存儲(chǔ)矩陣、PageRank的解的精度、收斂準(zhǔn)則、懸掛節(jié)點(diǎn)等問題，目前的研究都還不盡完善。由于不同算法給出的列表彼此之間存在明顯差別，因此未來的研究工作可以將多個(gè)相互獨(dú)立的算法的結(jié)果加以融合。

［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稿件編號(hào)：201602157

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

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