Updating Markov Chains with an Eye on Google's PageRank
Updating Markov Chains with an Eye on Google's PageRank
复制标题
DOI：
10.1137/040619028
复制
发表时间：
2005-12
期刊：
影响因子：
--
通讯作者：
A. Langville;C. D. Meyer
中科院分区：
文献类型：
--
作者：
A. Langville;C. D. Meyer
基于聚合/解聚原理，提出了一种更新有限齐次不可约马氏链平稳分布的迭代算法。重点是大规模的问题，其特点是由谷歌的PageRank应用程序，但该算法在一般情况下工作良好。该算法是灵活的，因为它允许改变的转移概率，以及为创建或删除的状态。除了建立收敛速度，它被证明是全局收敛的算法。数值实验的结果。
An iterative algorithm based on aggregation/disaggregation principles is presented for updating the stationary distribution of a finite homogeneous irreducible Markov chain. The focus is on large-scale problems of the kind that are characterized by Google's PageRank application, but the algorithm is shown to work well in general contexts. The algorithm is flexible in that it allows for changes to the transition probabilities as well as for the creation or deletion of states. In addition to establishing the rate of convergence, it is proven that the algorithm is globally convergent. Results of numerical experiments are presented.