Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
arXiv:1502.06775 · doi:10.1103/PhysRevE.91.062803
Abstract
Investigating the performance of different methods is a fundamental problem in graph partitioning. In this paper, we estimate the so-called detectability threshold for the spectral method with both unnormalized and normalized Laplacians in sparse graphs. The detectability threshold is the critical point at which the result of the spectral method is completely uncorrelated to the planted partition. We also analyze whether the localization of eigenvectors affects the partitioning performance in the detectable region. We use the replica method, which is often used in the field of spin-glass theory, and focus on the case of bisection. We show that the gap between the estimated threshold for the spectral method and the threshold obtained from Bayesian inference is considerable in sparse graphs, even without eigenvector localization. This gap closes in a dense limit.
26 pages, 13 figures
References in corpus (14)
- Finding community structure in networks using the eigenvectors of matrices
- Resolution limit in community detection
- Hierarchical structure and the prediction of missing links in networks
- Stochastic blockmodels and community structure in networks
- Consistency of spectral clustering
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Parsimonious module inference in large networks
- Community detection in networks: Structural communities versus ground truth
- On the localization transition in symmetric random matrices
- (Un)detectable cluster structure in sparse networks
- First eigenvalue/eigenvector in sparse random symmetric matrices: influences of degree fluctuation
- Comparative Study for Inference of Hidden Classes in Stochastic Block Models
- Global disorder transition in the community structure of large-q Potts systems