2018/09/19 by Ben-Hamou, Anna
#05C81 #60J10 #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1809.07243
In this paper, we are interested in the impact of communities on the mixing behavior of the non-backtracking random walk. We consider sequences of sparse random graphs of size N generated according to a variant of the classical configuration model which incorporates a two-community structure. The strength of the bottleneck is measured by a parameter α which roughly corresponds to the fraction of edges that go from one community to the other. We show that if α≫ (1)/(log N), then the non-backtracking random walk exhibits cutoff at the same time as in the one-community case, but with a larger cutoff window, and that the distance profile inside this window converges to the Gaussian tail function. On the other hand, if α≪ (1)/(log N) or α\asymp (1)/(log N), then the mixing time is of order 1/α and there is no cutoff.