Red Light Green Light Method for Solving Large Markov Chains
Abstract
Discrete-time discrete-state finite Markov chains are versatile mathematical models for a wide range of real-life stochastic processes. One of most common tasks in studies of Markov chains is computation of the stationary distribution. We propose a new general controlled, easily distributed algorithm for this task. The algorithm includes as special cases a wide range of known, very different, and previously disconnected methods including power iterations, versions of Gauss-Southwell formerly restricted to substochastic matrices, and online distributed algorithms. We prove exponential convergence of our method, demonstrate its high efficiency, and derive straightforward control strategies that achieve convergence rates faster than state-of-the-art algorithms.
References
[1]
Abiteboul, S., Preda, M., Cobena, G.: Adaptive on-line page importance computation. In: Proceedings of the 12th international conference on World Wide Web, pp. 280–290. ACM (2003)
[2]
Andersen, R., Borgs, C., Chayes, J., Hopcraft, J., Mirrokni, V.S., Teng, S.H.: Local computation of PageRank contributions. In: International Workshop on Algorithms and Models for the Web-Graph, pp. 150–165. Springer (2007)
[3]
Andersen, R., Chung, F., Lang, K.: Local graph partitioning using PageRank vectors. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 475–486. IEEE (2006)
[4]
Avrachenkov K, Chebotarev P, and Rubanov D Similarities on graphs: Kernels versus proximity measures Eur. J. Comb. 2019 80 47-56
[5]
Avrachenkov K, Litvak N, Nemirovsky D, and Osipova N Monte Carlo methods in PageRank computation: When one iteration is sufficient SIAM J. Numer. Anal. 2007 45 2 890-904
[6]
Avrachenkov, K., Mishenin, A., Gonçalves, P., Sokol, M.: Generalized optimization framework for graph-based semi-supervised learning. In: Proceedings of the 2012 SIAM International Conference on Data Mining, pp. 966–974. SIAM (2012)
[7]
Avron H, Druinsky A, and Gupta A Revisiting asynchronous linear solvers: Provable convergence rate through randomization Journal of the ACM (JACM) 2015 62 6 51
[8]
Bajović, D., Xavier, J., Sinopoli, B.: Products of stochastic matrices: Large deviation rate for Markov chain temporal dependencies. In: Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on, pp. 724–729. IEEE (2012)
[9]
Baudet GM Asynchronous iterative methods for multiprocessors Journal of the ACM (JACM) 1978 25 62 226-244
[10]
Berkhin P Bookmark-coloring algorithm for personalized PageRank computing Internet Mathematics 2006 3 1 41-62
[11]
Berkhout J and Heidergott BF The jump start power method: A new approach for computing the ergodic projector of a finite markov chain J. Sci. Comput. 2019 78 3 1691-1723
[12]
Bertsekas DP and Tsitsiklis JN Parallel and distributed computation: numerical methods 1989 NJ Prentice hall Englewood Cliffs
[13]
Bini, D.A., Latouche, G., Meini, B.: Numerical methods for structured Markov chains. Oxford University Press on Demand, Oxford, England (2005)
[14]
Boldi, P., Vigna, S.: The WebGraph framework I: Compression techniques. In: Proc. of the Thirteenth International World Wide Web Conference (WWW 2004), pp. 595–601. ACM Press, Manhattan, USA (2004)
[15]
Brin S and Page L The anatomy of a large-scale hypertextual web search engine Computer networks and ISDN systems 1998 30 1–7 107-117
[16]
Condon, A., Karp, R.M.: Algorithms for graph partitioning on the planted partition model. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (Eds.) Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques, pp. 221–232. Springer Berlin Heidelberg, Berlin, Heidelberg (1999)
[17]
Dai, L., Freris, N.M.: Fully distributed PageRank computation with exponential convergence. arXiv preprint arXiv:1705.09927 (2017)
[18]
Dwork C, Lynch N, and Stockmeyer L Consensus in the presence of partial synchrony Journal of the ACM (JACM) 1988 35 2 288-323
[19]
Fogaras D, Rácz B, Csalogány K, and Sarlós T Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments Internet Mathematics 2005 2 3 333-358
[20]
Gleich DF PageRank beyond the Web SIAM Rev. 2015 57 3 321-363
[21]
Grassmann WK, Taksar MI, and Heyman DP Regenerative analysis and steady state distributions for Markov chains Oper. Res. 1985 33 5 1107-1116
[22]
Hernández-Lerma, O., Lasserre, J.B.: Further topics on discrete-time Markov control processes, vol. 42. Springer, Berlin/Heidelberg, Germany (2012)
[23]
Holland, P.W., Laskey, K.B., Leinhardt, S.: Stochastic blockmodels: First steps. Social Networks 5(2), 109–137 (1983). URL www.sciencedirect.com/science/article/pii/0378873383900217
[24]
Hong, D.: Optimized on-line computation of PageRank algorithm. arXiv preprint arXiv:1202.6158 (2012)
[25]
Hong, D., Huynh, T.D., Mathieu, F.: D-iteration: Diffusion approach for solving PageRank. arXiv preprint arXiv:1501.06350 (2015)
[26]
Ishii, H., Suzuki, A.: Distributed randomized algorithms for PageRank computation: Recent advances. In: Uncertainty in Complex Networked Systems, 419–447. Springer (2018)
[27]
Langville, A.N., Meyer, C.D.: Google’s PageRank and beyond: The science of search engine rankings. Princeton University Press, Princeton, NJ (2011)
[28]
Latouche, G., Ramaswami, V.: Introduction to matrix analytic methods in stochastic modeling, vol. 5. SIAM (1999)
[29]
Lefevere R, Mariani M, and Zambotti L Large deviations for renewal processes Stochastic Processes and their Applications 2011 121 10 2243-2271
[30]
Litvak, N., Robert, P.: Analysis of an on-line algorithm for solving large Markov chains. In: Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools, p. 19. ICST (Institute for Computer Sciences, Social-Informatics) (2008)
[31]
Litvak N and Robert P A scaling analysis of a cat and mouse Markov chain Ann. Appl. Probab. 2012 22 2 792-826
[32]
Liu J, Mou S, and Morse AS Asynchronous distributed algorithms for solving linear algebraic equations IEEE Trans. Autom. Control 2017 63 2 372-385
[33]
Lofgren, P.A., Banerjee, S., Goel, A., Seshadhri, C.: FAST-PPR: Scaling personalized PageRank estimation for large graphs. In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 1436–1445. ACM (2014)
[34]
Lubachevsky B and Mitra D A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radius Journal of the ACM (JACM) 1986 33 1 130-150
[35]
McKenzie, L.W.: Turnpike theory. Econometrica: Journal of the Econometric Society pp. 841–865 (1976)
[36]
McSherry, F.: A uniform approach to accelerated PageRank computation. In: Proceedings of the 14th international conference on World Wide Web, pp. 575–582. ACM (2005)
[37]
Nassar, H., Kloster, K., Gleich, D.F.: Strong localization in personalized PageRank vectors. In: International Workshop on Algorithms and Models for the Web-Graph, pp. 190–202. Springer (2015)
[38]
O’Cinneide CA Entrywise perturbation theory and error analysis for Markov chains Numer. Math. 1993 65 1 109-120
[39]
Park S, Lee W, Choe B, and Lee SG A survey on personalized PageRank computation algorithms IEEE Access 2019 7 163049-163062
[40]
Philippe, B., Saad, Y., Stewart, W.J.: Numerical methods in Markov chain modeling. Operations Research 40(6), 1156–1179 (1992). URL http://www.jstor.org/stable/171728
[41]
Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, NJ (2014)
[42]
Rosenthal JS Convergence rates for Markov chains SIAM Rev. 1995 37 3 387-405
[43]
Saad, Y., Schultz, M.H.: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Stat. Comput. 7(3), 856–869 (1986)
[44]
Seneta, E.: Non-negative matrices and Markov chains, revised printing edn. Springer Science & Business Media (2006)
[45]
Southwell, R.V.: Relaxation methods in engineering science (1940)
[46]
Southwell, R.V.: Relaxation methods in theoretical physics, vol. 1, clarendon (1946)
[47]
Spielman DA and Teng SH A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning SIAM J. Comput. 2013 42 1 1-26
[48]
Stewart, W.J.: Numerical solution of Markov chains, vol. 8. CRC Press, Boca Raton, FL (1991)
[49]
Suzuki, A., Ishii, H.: Distributed randomized algorithms for PageRank based on a novel interpretation. In: 2018 Annual American Control Conference (ACC), pp. 472–477. IEEE (2018)
[50]
Van Der Hofstad, R.: Random graphs and complex networks, vol. 1. Cambridge University Press, Cambridge, England (2016)
[51]
Vial D and Subramanian V A structural result for Personalized PageRank and its algorithmic consequences Proceedings of the ACM on Measurement and Analysis of Computing Systems 2019 3 2 1-88
[52]
Wills, R.S.: When Rank Trumps Precision: Using the Power Method to Compute Google’s PageRank. PhD Thesis, North Carolina State University, Raleigh (2007)
[53]
Wills RS and Ipsen IC Ordinal ranking for Google’s PageRank SIAM J. Matrix Anal. Appl. 2009 30 4 1677-1696
Index Terms
- Red Light Green Light Method for Solving Large Markov Chains
Index terms have been assigned to the content through auto-classification.
Recommendations
Schwarz methods for quasi stationary distributions of Markov chains
We study computational schemes for quasi stationary distributions of Markov chains, having matrices which are quasi stochastic, i.e., all of their row sums are less than or equal to one. We develop Schwarz methods for the corresponding distributions. In ...
Perturbed Markov Chains with Damping Component
AbstractThe paper is devoted to studies of regularly and singularly perturbed Markov chains with damping component. In such models, a matrix of transition probabilities is regularised by adding a special damping matrix multiplied by a small damping (...
On the Convergence Time of Some Non-Reversible Markov Chain Monte Carlo Methods
AbstractIt is commonly admitted that non-reversible Markov chain Monte Carlo (MCMC) algorithms usually yield more accurate MCMC estimators than their reversible counterparts. In this note, we show that in addition to their variance reduction effect, some ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2022. Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Plenum Press
United States
Publication History
Published: 01 October 2022
Accepted: 01 August 2022
Revision received: 26 May 2022
Received: 23 November 2021
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
- NWO
- Qwant
- European Cooperation in Science and Technology
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Dec 2024