Spectral properties of the stochastic block model and their application to hitting times of random walks

2024/01/15 by Löwe, Matthias, Terveer, Sara
#05C80 #60F05 #FOS: Mathematics #Probability (math.PR) #[2020] 05C81

paper · doi:10.48550/arxiv.2401.07896

Abstract

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.

Related

• Hitting times in the stochastic block model
• A Central Limit Theorem for the average target hitting time for a random walk on a random graph
• A Central Limit Theorem for the mean starting hitting time for a random walk on a random graph
• Hitting Time Distributions of Random Walks on Finite Graphs
• Spectral Properties and Weak Detection in Stochastic Block Models