Abstract
Markov chains refer to stochastic processes whose states change according to transition probabilities determined only by the states of the previous time step. They have been crucial for modeling large-scale systems with random behavior in various fields such as control, communications, biology, optimization, and economics. In this entry, we focus on their recent application to the area of search engines, namely, the PageRank algorithm employed at Google, which provides a measure of importance for each page in the web. We present several researches carried out with control theoretic tools such as aggregation, distributed randomized algorithms, and PageRank optimization. Due to the large size of the web, computational issues are the underlying motivation of these studies.
†Roberto Tempo passed away before publication of this work was completed.
Similar content being viewed by others
Bibliography
Aldhaheri R, Khalil H (1991) Aggregation of the policy iteration method for nearly completely decomposable Markov chains. IEEE Trans Autom Control 36: 178–187
Bertsekas D, Tsitsiklis J (1989) Parallel and distributed computation: numerical methods. Prentice-Hall, Englewood Cliffs
Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw ISDN Syst 30:107–117
Csáji B, Jungers R, Blondel V (2014) PageRank optimization by edge selection. Discrete Appl Math 169:73–87
de Kerchove C, Ninove L, Van Dooren P (2008) Influence of the outlinks of a page on its PageRank. Linear Algebra Appl 429:1254–1276
Fercoq O, Akian M, Bouhtou M, Gaubert S (2013) Ergodic control and polyhedral approaches to PageRank optimization. IEEE Trans Autom Control 58: 134–148
Horn R, Johnson C (1985) Matrix analysis. Cambridge University Press, Cambridge
Ishii H, Suzuki A (2018) Distributed randomized algorithms for PageRank computation: recent advances. In: Basar T (ed) Uncertainty in complex networked systems. Birkhäuser, Basel, pp 419–447
Ishii H, Tempo R (2010) Distributed randomized algorithms for the PageRank computation. IEEE Trans Autom Control 55:1987–2002
Ishii H, Tempo R, Bai EW (2012) A web aggregation approach for distributed randomized PageRank algorithms. IEEE Trans Autom Control 57:2703–2717
Ishii H, Tempo R (2014) The PageRank problem, multi-agent consensus and web aggregation: a systems and control viewpoint. IEEE Control Syst Mag 34(3):34–53
Kumar P, Varaiya P (1986) Stochastic systems: estimation, identification, and adaptive control. Prentice Hall, Englewood Cliffs
Lagoa C, Zaccarian L, Dabbene F (2017) A distributed algorithm with consistency for PageRank-like linear algebraic systems. In: Proceedings of 20th IFAC World Congress, pp 5339–5344
Langville A, Meyer C (2006) Google’s PageRank and beyond: the science of search engine rankings. Princeton University Press, Princeton
Meyer C (1989) Stochastic complementation, uncoupling Markov chains, and the theory of nearly reducible systems. SIAM Rev 31:240–272
Norris J (1997) Markov chains. Cambridge University Press, Cambridge
Phillips R, Kokotovic P (1981) A singular perturbation approach to modeling and control of Markov chains. IEEE Trans Autom Control 26:1087–1094
Puterman M (1994) Markov decision processes: discrete stochastic dynamic programming. Wiley, New York
You K, Tempo R, Qiu L (2017) Distributed algorithms for computation of centrality measures in complex networks. IEEE Trans Autom Control 62:2080–2094
Zhao W, Chen H, Fang H (2013) Convergence of distributed randomized PageRank algorithms. IEEE Trans Autom Control 58:3255–3259
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2020 Springer-Verlag London Ltd., part of Springer Nature
About this entry
Cite this entry
Ishii, H., Tempo, R. (2020). Markov Chains and Ranking Problems in Web Search. In: Baillieul, J., Samad, T. (eds) Encyclopedia of Systems and Control. Springer, London. https://doi.org/10.1007/978-1-4471-5102-9_135-2
Download citation
DOI: https://doi.org/10.1007/978-1-4471-5102-9_135-2
Published:
Publisher Name: Springer, London
Print ISBN: 978-1-4471-5102-9
Online ISBN: 978-1-4471-5102-9
eBook Packages: Springer Reference EngineeringReference Module Computer Science and Engineering
Publish with us
Chapter history
-
Latest
Markov Chains and Ranking Problems in Web Search- Published:
- 29 November 2019
DOI: https://doi.org/10.1007/978-1-4471-5102-9_135-2
-
Original
Markov Chains and Ranking Problems in Web Search- Published:
- 12 February 2014
DOI: https://doi.org/10.1007/978-1-4471-5102-9_135-1