Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors

Tatsuro Kawamoto, Yoshiyuki Kabashima

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…