Article ID: | iaor20112617 |
Volume: | 72 |
Issue: | 2 |
Start Page Number: | 342 |
End Page Number: | 352 |
Publication Date: | Feb 2011 |
Journal: | Automation and Remote Control |
Authors: | Polyak T, Nazin V |
Keywords: | heuristics |
Consideration was given to estimation of the eigenvector corresponding to the greatest eigenvalue of a stochastic matrix. There exist numerous applications of this problem arising at ranking the results of search, coordination of the multiagent system actions, network control, and data analysis. The standard technique for its solution comes to the power method with an additional regularization of the original matrix. A new randomized algorithm was proposed, and a uniform–over the entire class of the stochastic matrices of a given size–upper boundary of the convergence rate was validated. It is given by {ie342‐1}, where