A unified framework for spectral clustering in sparse graphs
This work addresses community detection in sparse graphs, a key challenge in network analysis, but it appears incremental as it builds on existing spectral methods like the non-backtracking and Bethe-Hessian matrices.
The authors tackled the problem of spectral community detection in sparse networks with heterogeneous degree distributions by proposing a parametrized regularized Laplacian matrix, which efficiently retrieves communities without suffering from degree heterogeneity and inherently accounts for classification hardness, achieving high-quality reconstruction.
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.