Hitting times in the stochastic block model

2024/02/14 by Andrea Ottolini, Ottolini, Andrea
Physics and Astronomy · #05C80 #60J10 #Combinatorics (math.CO) #FOS: Mathematics #Opinion Dynamics and Social Influence #Probability (math.PR) #Theoretical and Computational Physics #stochastic dynamics and bifurcation

paper · pdf · doi:10.48550/arxiv.2402.09624

openalex publication_date 2024/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a large connected graph G=(V,E), and two vertices w,≠ v, let T_w,v be the first hitting time to v starting from w for the simple random walk on G. We prove a general theorem that guarantees, under some assumptions on G, to approximate \mathbb E[T_w,v] up to o(1) terms. As a corollary, we derive explicit formulas for the stochastic block model with two communities and connectivity parameters p and q, and show that the average hitting times, for fixed v and as w varies, concentrates around four possible values. The proof is purely probabilistic and uses a coupling argument.

Related

• Spectral properties of the stochastic block model and their application to hitting times of random walks
• A Central Limit Theorem for the average target hitting time for a random walk on a random graph
• Hitting Time Distributions of Random Walks on Finite Graphs
• A Central Limit Theorem for the mean starting hitting time for a random walk on a random graph
• Estimating Hitting Times Locally At Scale