2022/12/08 by Jonathan Hermon, Hermon, Jonathan, Anđela Šarković +3
Mathematics · Physics and Astronomy · #60F05 #60G50 #Complex Network Analysis Techniques #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2212.04469
openalex publication_date 2022/12/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has an internal degint≥ 3 and an outgoing degout number of half-edges. Given a stochastic matrix Q, we pick a random perfect matching of the half-edges subject to the constraint that each vertex v has degint(v) neighbours inside its community and the proportion of outgoing half-edges from community i matched to a half-edge from community j is Q(i,j). Assuming the number of communities is constant and they all have comparable sizes, we prove the following dichotomy: simple random walk on the resulting graph exhibits cutoff if and only if the product of the Cheeger constant of Q times log n (where n is the number of vertices) diverges. In [4], Ben-Hamou established a dichotomy for cutoff for a non-backtracking random walk on a similar random graph model with 2 communities. We prove the same characterisation of cutoff holds for simple random walk.