基于PageRank的馬爾可夫鏈研究

張 桃，吳小偉

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

基于PageRank的馬爾可夫鏈研究

張 桃1，吳小偉2

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

PageRank向量是一個離散時間、有限狀態馬爾可夫鏈的穩態分布。同時，馬爾可夫鏈理論已經得到了充分發展，利用馬爾可夫鏈可以更好地理解和分析有關PageRank的問題。本文基于循環或者排名下沉所造成的PageRank收斂問題，通過對馬爾可夫鏈的數學內容進行研究的方法，得出不可約馬爾可夫鏈的暫態行為和極限行為，并對不可約馬爾可夫鏈的特征進行總結。

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

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

1 PageRank迭代過程中的問題

1.1 排名下沉

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

圖1 具有6個頁面的網絡有向圖

1.2 循環問題

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

圖2 存在循環的簡單圖

2 不可約馬爾可夫鏈

分析圖3可知，當上網者隨機選擇當前正在瀏覽頁面中的鏈接時，便可以獲取一條馬爾可夫鏈，它由這個鏈接結構上的隨機游走所定義，其轉移概率矩陣為不可約隨機矩陣H：

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

圖3 微型的3頁面網絡

2.1 暫態行為

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

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

2.2 極限行為

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

2.3 不可約馬爾可夫鏈的特征總結

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

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

3）無論P是素矩陣還是非素矩陣，πT的第j個元素πj都對應了足夠長時間內鏈處于Sj的時間比例，且向量πT是鏈的唯一的穩態分布向量[14-15]。

3 結 論

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

[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].計算機科學，2011（38）:185-188.

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

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

[5]宮秀文.基于PageRank的社交網絡影響最大化傳播模型與算法研究[J].計算機科學，2013（40）:136-140.

[6]夏雙志.目標存在狀態變量的非齊次馬爾可夫鏈模型[J].西安電子科技大學學報，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

江蘇省社科聯研究基金（201035）

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