A THRESHOLD FOR CUTOFF IN TWO-COMMUNITY RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Ben-Hamou, Anna
• 署名单位: Universite Paris Cite; Sorbonne Universite
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/19-AAP1544
• 发表日期: 2020
• 页码: 1824-1846
• 关键词: random-walks; hitting times

摘要

In this paper, we are interested in the impact of communities on the mixing behavior of the nonbacktracking 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 alpha which roughly corresponds to the fraction of edges that go from one community to the other. We show that if alpha >> 1/ log N, then the nonbacktracking 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 alpha << 1/log N or alpha asymptotic to 1/log N, then the mixing time is of order 1/alpha and there is no cutoff.