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 (23)
- Scikit-learn: Machine Learning in Python
- Emergence of scaling in random networks
- Fast unfolding of communities in large networks
- The structure and function of complex networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- From Louvain to Leiden: guaranteeing well-connected communities
- Cooperative Game Theory Approaches for Network Partitioning
- Benchmark graphs for testing community detection algorithms
- Stochastic blockmodels and community structure in networks
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Fast community detection by SCORE
- Ferromagnetic ordering in graphs with arbitrary degree distribution
- Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
- Stochastic Block Models and Reconstruction
- Understanding Regularized Spectral Clustering via Graph Conductance
- Estimating the number of communities in networks by spectral methods
- 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