基于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收斂問題便可以得到解決?！?br>