Mixing time of PageRank surfers on sparse random digraphs

Pietro Caputo, Matteo Quattropani

Published 2019-05-13Version 1

Given a digraph $G$, a parameter $\alpha\in(0,1)$ and a distribution $\lambda$ over the vertices of $G$, the generalised PageRank surf on $G$ with parameters $\alpha$ and $\lambda$ is the Markov chain on the vertices of $G$ such that at each step with probability $\alpha$ the state is updated with an independent sample from $\lambda$, while with probability $1-\alpha$ the state is moved to a uniformly random vertex in the out-neighbourhood of the current state. The stationary distribution is the so-called PageRank vector. We analyse convergence to stationarity of this Markov chain when $G$ is a large sparse random digraph with given degree sequences, in the limit of vanishing parameter $\alpha$. We identify three scenarios: when $\alpha$ is much smaller than the inverse of the mixing time of $G$ the relaxation to equilibrium is dominated by the simple random walk and displays a cutoff behaviour; when $\alpha$ is much larger than the inverse of the mixing time of $G$ on the contrary one has pure exponential decay with rate $\alpha$; when $\alpha$ is comparable to the inverse of the mixing time of $G$ there is a mixed behaviour interpolating between cutoff and exponential decay. This trichotomy is shown to hold uniformly in the starting point and for a large class of distributions $\lambda$, including widespread as well as strongly localized measures. Our results are crucially based on recent progress in the analysis of mixing times for the simple random walk on sparse random digraphs by Bordenave-Caputo-Salez.