张 桃，吴小伟

（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收敛问题便可以得到解决。……