






















We analyze hitting times of simple random walk on realizations of the stochastic block model. We show that under some natural assumptions the hitting time averaged over the target vertex asymptotically almost surely given by $N(1+o(1))$. On the other hand, the hitting time averaged over the starting vertex asymptotically almost surely depends on expected degrees in the block the target vertex is in. We also show a central limit theorem for the hitting time averaged over the starting vertex. Our main techniques are a spectral decomposition of these hitting times, a spectral analysis of the adjacency matrix and the graph Laplacian.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。