Mixing cutoff for simple random walks on the Chung-Lu digraph

DOI10.1002/RSA.21277MaRDI QIDQ7027464zbMATH OpenFDO

Authors Alessandra Bianchi, Giacomo Passuello

Publication date 14 February 2025

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/RSA.21277

zbMATH Keywords

Chung-Lu digraphcutoffmixing timerandom directed graphssimple random walks

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites work

• A threshold for cutoff in two-community random graphs
• Connected components in random graphs with given expected degree sequences
• Connectivity of a general class of inhomogeneous random digraphs
• Cutoff at the ``entropic time for sparse Markov chains
• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Cutoff phenomena for random walks on random regular graphs
• Generalized PageRank on directed configuration networks
• Linking the mixing times of random walks on static and dynamic random graphs
• 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.
• Meeting, coalescence and consensus time on random directed graphs
• Mixing time of PageRank surfers on sparse random digraphs
• Mixing time trichotomy in regenerating dynamic digraphs
• On tail probabilities for martingales
• PageRank in Scale-Free Random Graphs
• Probability theory. A comprehensive course
• Random graphs and complex networks. Volume 1
• Random walk on sparse random digraphs
• Random walks on dynamic configuration models: a trichotomy
• Random walks on the random graph
• Rankings in directed configuration models with heavy tailed in-degrees
• Stationary distribution and cover time of random walks on random digraphs
• Stationary distribution and cover time of sparse directed configuration models
• The cutoff phenomenon in finite Markov chains.
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The Size of the Largest Strongly Connected Component of a Random Digraph with a Given Degree Sequence

Cited in

(1)

• Mixing trichotomy for random walks on directed stochastic block models

This page was built for publication: Mixing cutoff for simple random walks on the Chung-Lu digraph

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