Spectral properties of the stochastic block model and their application to hitting times of random walks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910917003837440 |
|---|---|
| author | Löwe, Matthias Terveer, Sara |
| author_facet | Löwe, Matthias Terveer, Sara |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07896 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spectral properties of the stochastic block model and their application to hitting times of random walks Löwe, Matthias Terveer, Sara Probability [2020] 05C81, 05C80, 60F05 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. |
| title | Spectral properties of the stochastic block model and their application to hitting times of random walks |
| topic | Probability [2020] 05C81, 05C80, 60F05 |
| url | https://arxiv.org/abs/2401.07896 |