Updating Markov Chains With an Eye on Google's 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 always converges independent of the starting vector.
Results of numerical experimental are presented.
- SIAM J. Matrix Anal. Appl.
- Vol 27, No. 4, pp. 968-987
- Amy N. Langville
- Carl D. Meyer
- THE PDF FILE
- Updating PageRank.pdf
Return To Meyer's Home Page
Return To Abstracts