基于PageRank的馬爾可夫鏈研究

張 桃，吳小偉

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

基于PageRank的馬爾可夫鏈研究

張 桃1，吳小偉2

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

PageRank向量是一個離散時間、有限狀態(tài)馬爾可夫鏈的穩(wěn)態(tài)分布。同時，馬爾可夫鏈理論已經(jīng)得到了充分發(fā)展，利用馬爾可夫鏈可以更好地理解和分析有關(guān)PageRank的問題。本文基于循環(huán)或者排名下沉所造成的PageRank收斂問題，通過對馬爾可夫鏈的數(shù)學(xué)內(nèi)容進(jìn)行研究的方法，得出不可約馬爾可夫鏈的暫態(tài)行為和極限行為，并對不可約馬爾可夫鏈的特征進(jìn)行總結(jié)。

PageRank；不可約馬爾可夫鏈；極限行為

馬爾可夫鏈理論已經(jīng)得到了充分發(fā)展，而且適用于PageRank問題。利用馬爾可夫理論，可以對PageRank向量方程加以修正，以確保得到預(yù)期的結(jié)果、收斂性質(zhì)等。冪法的傳統(tǒng)終止準(zhǔn)則指出，當(dāng)相鄰兩次迭代所得結(jié)果的差別小于某個預(yù)先給定的容許限時，算法停止。但是研究者近期的研究結(jié)果表明，迭代應(yīng)該在冪法所得的PageRank向量近似值的排序達(dá)到收斂時停止[1]。實驗表明，在某些數(shù)據(jù)集上，節(jié)省的迭代次數(shù)加大，有效的提高了運(yùn)算效率。即使減少了幾次迭代數(shù)量，考慮到PageRank問題的規(guī)模，也是值得肯定利用的[2]。因此，對于任何初始向量，如果其是隨機(jī)、不可約且非周期性的，則應(yīng)用馬爾可夫矩陣P的冪法將收斂到唯一一個穩(wěn)態(tài)向量的正向量[3-5]。因此，如果將H修改為具有預(yù)期結(jié)果性質(zhì)的馬爾可夫矩陣，那么由于循環(huán)或者排名下沉所造成的PageRank收斂問題便可以得到解決。文中通過對馬爾可夫鏈的數(shù)學(xué)內(nèi)容分析，對不可約馬爾可夫鏈的暫態(tài)行為和極限行為進(jìn)行研究分析。

1 PageRank迭代過程中的問題

1.1 排名下沉

利用π（0）T=1/neT開始迭代過程，其中 eT是一個所有元素值均為1的全1行向量。在利用該初始向量執(zhí)行方程 π（k+1）T=π（k）TH 時，排名下沉問題就會出現(xiàn)，即那些在各次迭代中累計起越來越多的PageRank的頁面，它們最終壟斷了得分，并拒絕與其他頁面分享PageRank。如圖1所示，結(jié)點(diǎn)4、5和6所形成的團(tuán)簇將會共同囤積PageRank。對方程π（k+1）T=π（k）TH經(jīng)過13次迭代后，π（13）T（0 0 0 2/3 1/3 1/5）。同時，隨著結(jié)點(diǎn)積累了PageRank，某些結(jié)點(diǎn)可能會完全無法獲得得分。因此，當(dāng)大多數(shù)結(jié)點(diǎn)都被賦予了一個值為0的PageRank時，根據(jù)PageRank值來進(jìn)行結(jié)點(diǎn)的排名就不僅運(yùn)算規(guī)模大，同時成本較高。

圖1 具有6個頁面的網(wǎng)絡(luò)有向圖

1.2 循環(huán)問題

如圖2所示，頁面1僅指向頁面2，反之亦然，因此就形成一個無限的環(huán)路或者循環(huán)。假設(shè)方程π（k+1）T=π（k）TH 的迭代過程由π（0）T=（1 0）開始，則不論這一過程運(yùn)行過長時間，迭代都不會收斂。迭代值π（k）T將在兩個值之間進(jìn)行無限次翻轉(zhuǎn)：當(dāng)k是偶數(shù)時，值為（1 0）；當(dāng)k時奇數(shù)時，值為（0 1）。

圖2 存在循環(huán)的簡單圖

2 不可約馬爾可夫鏈

分析圖3可知，當(dāng)上網(wǎng)者隨機(jī)選擇當(dāng)前正在瀏覽頁面中的鏈接時，便可以獲取一條馬爾可夫鏈，它由這個鏈接結(jié)構(gòu)上的隨機(jī)游走所定義，其轉(zhuǎn)移概率矩陣為不可約隨機(jī)矩陣H：

此時，超鏈接矩陣H是隨機(jī)的，如果存在一個懸掛節(jié)點(diǎn)，則H將具有一個全0行，此時H將不再是隨機(jī)的，而該過程也不再是一條馬爾可夫鏈。

圖3 微型的3頁面網(wǎng)絡(luò)

2.1 暫態(tài)行為

假設(shè)初始分布向量PT（0）=（P1（0）P2（0）...Pn（0）），那么首先需要計算第一次轉(zhuǎn)移后處于任意給定狀態(tài)的概率，即確定 PT（1）=（p1（1）p2（1）...pn（1）），需要注意，該次計算需要在第二次轉(zhuǎn)移前進(jìn)行[9]。令∧和∨分別表示邏輯與和邏輯或，那么由此可得，對于每個j，

由以上計算可知，PT（1）=PT（0）P描述了由初始分布到一步之后的分布之間的演化過程，根據(jù) “無記憶”的馬爾科夫性[10]，進(jìn)而可得兩步之后的情形，即將PT（1）作為初始分布按上述計算方法重聚計算。因此，PT（2）=PT（1）P，PT（3）=PT（2）P，進(jìn)而可得 PT（k）=PT（0）Pk。若，則PT（k）=PT（0）Pk中可得，對每個i=1，2，...，n，有由此可知，若P是一條定義于狀態(tài){S1，S2，…，Sn}上的馬爾可夫鏈的轉(zhuǎn)移概率矩陣，則矩陣Pk表示k步轉(zhuǎn)移概率矩陣，即它的（I，j）元素是由Si經(jīng)過k步轉(zhuǎn)移到 Si的概率，第k步分布向量由PT（k）=PT（0）Pk得出。

2.2 極限行為

對馬爾可夫鏈的極限性質(zhì)進(jìn)行分析，需要將隨機(jī)矩陣族分為P不可約且存在和P不可約且不存在兩種互不相交的類型[11-13]，具體分析如下：

2.3 不可約馬爾可夫鏈的特征總結(jié)

令P為狀態(tài){S1，S2，…，Sn}上的不可約馬爾可夫鏈的轉(zhuǎn)移概率矩陣，并πTP=πT，‖π‖1=1。因此，對于每個初始分布PT（0），則可知：

1）k步轉(zhuǎn)移矩陣為Pk，第k步分布向量為PT（K）=PT（0）Pk；

3）無論P(yáng)是素矩陣還是非素矩陣，πT的第j個元素πj都對應(yīng)了足夠長時間內(nèi)鏈處于Sj的時間比例，且向量πT是鏈的唯一的穩(wěn)態(tài)分布向量[14-15]。

3 結(jié) 論

馬爾可夫鏈的研究已經(jīng)展現(xiàn)其有效性，研究方法和思路更加追求創(chuàng)新和效率，但是無論暫態(tài)行為或者極限行為，目前的研究都還不盡完善。由于不同算法給出的矩陣彼此之間存在明顯差別，因此未來的研究工作可以將多個相互獨(dú)立的算法的結(jié)果加以融合。

[1]Grace E.Cho and Carl D.Meyer.Aggregation/ disaggregation errors for nearly uncoupled Markov chains[C]//Technical report，NCSU Tech.Report. 2013.

[2]李稚楹.PageRank算法研究綜述[J].計算機(jī)科學(xué)，2011（38）:185-188.

[3]榮騰中.高階馬爾可夫鏈平穩(wěn)分布的存在唯一性[J].系統(tǒng)工程理論與實踐，2013（33）:2016-2019.

[4]肖敬偉.基于PageRank的緩存替換策略[J].信息技術(shù)，2016（6）:107-110.

[5]宮秀文.基于PageRank的社交網(wǎng)絡(luò)影響最大化傳播模型與算法研究[J].計算機(jī)科學(xué)，2013（40）:136-140.

[6]夏雙志.目標(biāo)存在狀態(tài)變量的非齊次馬爾可夫鏈模型[J].西安電子科技大學(xué)學(xué)報，2013（40）:49-54.

[7]Carl D.Meyer and James M.Shoaf.Updating finite Markov chains by using techniques of group matrix inversion.Journal of Statistical Computation and Simulation，1980：161-179.

[8]William J.Stewart Numerical experiments with iteration and aggregation for Markov chains.ORSA Journal on Computing，2011，4（3）:336-50.

[9]Cleve B.Moler.Numerical Computing with MATLAB [M].SIAM，2004.

[10]Grace E.Cho and Carl D.Meyer.Aggregation/ disaggregation errors for nearly uncoupled.

[11]William J.Stewart.Introduction to the Numerical Solution of Markov Chains[M].Princeton University Press，2014.

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

[13]Grace E.Cho and Carl D.Meyer.Comparison of perturbation bounds for the stationary distribution of a Markov chain[M].Linear Algebra and Its Applications，2010：135-155.

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

[15]Carl D.Meyer.Matrix Analysisand Applied Linear Algebra[M].SIAM.Philadelphia，2000.

The study of Markov chains based on PageRank

ZHANG Tao1，WU Xiao-wei2
（1.Business School of HOHAI University，Nanjing 210000，China；2.Jiangsu Posts& Telecommunication Planning And Designing Institute Co.Ltd，Nanjing 210019，China）

PageRank vector is a discrete-time，finite-state Markov Chains steady state distribution.At the same time，the theory of Markov Chains has been fully developed，with which we can understand and analyze the problem about PageRank.Based on convergence of PageRank resulted from loops or sinking rank，this paper analyzes transient behavior and limited behavior of irreducible Markov Chains and concludes the feature of them with the study of overarching ideas of Markov Chains.

PageRank；irreducible markov chains；limited behavior

TN0

A

1674-6236（2017）09-0036-03

2016-07-11稿件編號：201607090

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

張 桃（1992—），女，江蘇徐州人，碩士。研究方向：企業(yè)管理、市場營銷。