Celina Arnlund: PageRank as a Markov Chain: The Relationship Between Spectral Gap and Mixing Time

Abstract: PageRank is a measure of importance that determines the relevance of a webpage by analyzing its incoming links. The algorithm for computing the PageRank, published in 1998, is a part of Google's search engine, and was developed by Larry Page and Sergey Brin. This paper provides a theoretical understanding of the algorithm from the perspective of Markov chains. By modeling the Web as a directed graph and introducing a Google matrix, the algorithm ensures the existence and the uniqueness of the stationary distribution called PageRank. Furthermore, the paper aims to examine the relationship between the damping factor, the spectral gap and the mixing time. The second largest eigenvalue of the Google matrix is examined in relation to the rate of convergence and mixing time respectively. Finally, the theory is applied to simple graph structures, the cycle and wheel graph, in order to exemplify the concepts.