The PageRank Problem in Google: A Systems and Control Viewpoint

October 21, 2014, ESB 2001

Roberto Tempo

Politecnico di Torino, CNR-IEIIT


In this lecture, we study the PageRank problem and illustrate it using the Google search engine as a paradigmatic example. Specifically, we introduce PageRank discussing the so-called random surfer model and the teleportation matrix. Subsequently, we present new distributed randomized algorithms (of Las Vegas type) for its efficient computation. Subsequently, we show the main properties of these algorithms utilizing results of the theory of positive matrices and Markov Chains. Finally, we discuss how these ideas can be extended to different problems of interest to the systems and control community, including ranking of scientific journals, aggregation techniques and consensus of multi-agent systems.

Speaker's Bio

Roberto Tempo was born in Cuorgne', Italy, in 1956. In 1980 he graduated in Electrical Engineering from Politecnico di Torino, Italy. After a period spent at Politecnico di Torino, he joined the National Research Council of Italy (CNR) at the research institute IEIIT, Torino, where he is a Director of Research of Systems and Computer Engineering since 1991. He has held visiting and research positions at Chinese Academy of Sciences in Beijing, Kyoto University, The University of Tokyo, University of Illinois at Urbana-Champaign, German Aerospace Research Organization in Oberpfaffenhofen and Columbia University in New York.

Dr. Tempo's research activities are mainly focused on the analysis and design of complex systems with uncertainty, and various related applications within information technology which currently include the PageRank computation in the Google search engine, distributed localization of wireless sensor networks and asynchronous opinion dynamics in social networks. On these topics, he has published more than 180 research papers in international journals, books and conferences. He is also a co-author of the book “Randomized Algorithms for Analysis and Control of Uncertain Systems,” Springer-Verlag, London, published in two editions in 2005 and 2013.

He is a Fellow of the IEEE for “Contributions to Robust Identification and Control of Uncertain Systems” and a Fellow of the International Federation of Automatic Control (IFAC) for “Contributions to the Analysis and Control of Uncertain Systems, for Pioneering the Probabilistic Approach to Robustness.” He is a recipient of the "Outstanding Paper Prize Award" from the IFAC for a paper published in the journal Automatica, and of the “Distinguished Member Award” from the IEEE Control Systems Society. He is a Corresponding Member of the Academy of Sciences, Institute of Bologna, Italy, Class Physical Sciences, Section Technical Sciences.

In 2010 Dr. Tempo has served the IEEE Control Systems Society as President. He was General Co-Chair for the IEEE Conference on Decision and Control, which was held in Florence, Italy, in 2013 and Program Chair of the first joint IEEE Conference on Decision and Control and European Control Conference, Seville, Spain, 2005. He is currently an Editor and Deputy Editor-in-Chief of Automatica, a Senior Editor of the IEEE Transactions on Automatic Control, a member of the Advisory Committee of the IEEE Transactions on Control of Network Systems, and an Editor at Large of the Asian Journal of Control. He has been Editor for Technical Notes and Correspondence of the IEEE Transactions on Automatic Control in 2005-2009.