Mixing time of PageRank surfers on sparse random digraphs

DOI10.1002/RSA.21009MaRDI QIDQ6074663zbMATH OpenFDO

Authors Pietro Caputo, Matteo Quattropani

Publication date 12 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.04993

zbMATH Keywords

mixing timenonreversible Markov chainPageRankrandom digraphsrandom walks on networks

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Abstract: We consider the generalised PageRank walk on a digraph $G$, with refresh probability $alpha$ and resampling distribution $lambda$. We analyse convergence to stationarity when $G$ is a large sparse random digraph with given degree sequences, in the limit of vanishing $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 uniformly in the resampling distribution $lambda$.

Recommendations

• Comparing mixing times on sparse random graphs
• Comparing mixing times on sparse random graphs
• PageRank on inhomogeneous random digraphs
• Mixing time of near-critical random graphs
• Mixing time bounds for graphlet random walks
• The mixing time of the giant component of a random graph
• Mixing time of exponential random graphs
• Mixing time of vertex-weighted exponential random graphs
• PageRank in Scale-Free Random Graphs
• Linking the mixing times of random walks on static and dynamic random graphs

Cites work

• Choose the damping, choose the ranking?
• Cutoff at the ``entropic time for sparse Markov chains
• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff phenomena for random walks on random regular graphs
• Diameter and stationary distribution of random r-out digraphs
• Directed random graphs with given degree distributions
• Generalized PageRank on directed configuration networks
• Local weak convergence for PageRank
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Networks, crowds and markets. Reasoning about a highly connected world.
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• PageRank beyond the web
• Probability with Martingales
• Random walk on sparse random digraphs
• Random walks on dynamic configuration models: a trichotomy
• Random walks on the random graph
• The cutoff phenomenon in finite Markov chains.
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence

Cited in

(11)

• Mixing time trichotomy in regenerating dynamic digraphs
• Linking the mixing times of random walks on static and dynamic random graphs
• The buck-passing game
• On the meeting of random walks on random DFA
• Rankings in directed configuration models with heavy tailed in-degrees
• Mixing trichotomy for an Ehrenfest urn with impurities
• Meeting, coalescence and consensus time on random directed graphs
• Mixing trichotomy for random walks on directed stochastic block models
• Restart perturbations for reversible Markov chains: trichotomy and pre-cutoff equivalence
• Mixing cutoff for simple random walks on the Chung-Lu digraph
• Evolution of discordant edges in the voter model on random sparse digraphs

This page was built for publication: Mixing time of PageRank surfers on sparse random digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6074663)