Mixing time of PageRank surfers on sparse random digraphs

DOI10.1002/rsa.21009zbMath1523.60127arXiv1905.04993MaRDI QIDQ6074663

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 timePageRankrandom digraphsrandom walks on networksnonreversible Markov chain

Mathematics Subject Classification ID

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) Directed graphs (digraphs), tournaments (05C20)

Related Items

On the meeting of random walks on random DFA, Rankings in directed configuration models with heavy tailed in-degrees, Linking the mixing times of random walks on static and dynamic random graphs, The Buck-Passing Game

Cites Work

• Unnamed Item
• Unnamed Item
• Diameter and stationary distribution of random \(r\)-out digraphs
• Choose the damping, choose the ranking?
• Cutoff phenomena for random walks on random regular graphs
• Cutoff at the ``entropic time for sparse Markov chains
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• Random walks on the random graph
• Cutoff for nonbacktracking random walks on sparse random graphs
• Local weak convergence for PageRank
• Random walks on dynamic configuration models: a trichotomy
• Random walk on sparse random digraphs
• PageRank Beyond the Web
• Probability with Martingales
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence
• The cutoff phenomenon in finite Markov chains.
• Directed random graphs with given degree distributions
• Generalized PageRank on directed configuration networks