A unified framework for spectral clustering in sparse graphs
arXiv:2003.09198
Abstract
This article considers spectral community detection in the regime of sparse networks with heterogeneous degree distributions, for which we devise an algorithm to efficiently retrieve communities. Specifically, we demonstrate that a conveniently parametrized form of regularized Laplacian matrix can be used to perform spectral clustering in sparse networks, without suffering from its degree heterogeneity. Besides, we exhibit important connections between this proposed matrix and the now popular non-backtracking matrix, the Bethe-Hessian matrix, as well as the standard Laplacian matrix. Interestingly, as opposed to competitive methods, our proposed improved parametrization inherently accounts for the hardness of the classification problem. These findings are summarized under the form of an algorithm capable of both estimating the number of communities and achieving high-quality community reconstruction.
References in corpus (7)
- Fast unfolding of communities in large networks
- Modularity and community structure in networks
- Cooperative Game Theory Approaches for Network Partitioning
- Benchmark graphs for testing community detection algorithms
- Stochastic blockmodels and community structure in networks
- Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
- Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian