Fundamental Limits of Spectral Clustering in Stochastic Block Models
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914789565923328 |
|---|---|
| author | Zhang, Anderson Ye |
| author_facet | Zhang, Anderson Ye |
| contents | Spectral clustering has been widely used for community detection in network sciences. While its empirical successes are well-documented, a clear theoretical understanding, particularly for sparse networks where degrees are much smaller than $\log n$, remains unclear. In this paper, we address this significant gap by demonstrating that spectral clustering offers exponentially small error rates when applied to sparse networks under Stochastic Block Models. Our analysis provides sharp characterizations of its performance, backed by matching upper and lower bounds possessing an identical exponent with the same leading constant. The key to our results is a novel truncated $\ell_2$ perturbation analysis for eigenvectors, coupled with a new analysis idea of eigenvectors truncation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_09289 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fundamental Limits of Spectral Clustering in Stochastic Block Models Zhang, Anderson Ye Statistics Theory Social and Information Networks Spectral Theory Spectral clustering has been widely used for community detection in network sciences. While its empirical successes are well-documented, a clear theoretical understanding, particularly for sparse networks where degrees are much smaller than $\log n$, remains unclear. In this paper, we address this significant gap by demonstrating that spectral clustering offers exponentially small error rates when applied to sparse networks under Stochastic Block Models. Our analysis provides sharp characterizations of its performance, backed by matching upper and lower bounds possessing an identical exponent with the same leading constant. The key to our results is a novel truncated $\ell_2$ perturbation analysis for eigenvectors, coupled with a new analysis idea of eigenvectors truncation. |
| title | Fundamental Limits of Spectral Clustering in Stochastic Block Models |
| topic | Statistics Theory Social and Information Networks Spectral Theory |
| url | https://arxiv.org/abs/2301.09289 |