Spectral Clustering and Block Models: A Review And A New Algorithm
This work addresses the problem of graph clustering for researchers and practitioners, offering an incremental improvement with a new algorithm that enhances consistency and performance.
The paper reviews spectral clustering methods for unlabeled graphs, analyzing their consistency in data from block models, and introduces a new algorithm that achieves optimal performance both theoretically through asymptotic analysis and empirically.
We focus on spectral clustering of unlabeled graphs and review some results on clustering methods which achieve weak or strong consistent identification in data generated by such models. We also present a new algorithm which appears to perform optimally both theoretically using asymptotic theory and empirically.