Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs

Abstract

Spectral clustering is one of the most popular, yet still incompletely understood, methods for community detection on graphs. This article studies spectral clustering based on the Bethe-Hessian matrix $H_r=(r^2-1)I_n+D-rA$ for sparse heterogeneous graphs (following the degree-corrected stochastic block model) in a two-class setting. For a specific value $r=\zeta$, clustering is shown to be insensitive to the degree heterogeneity. We then study the behavior of the informative eigenvector of $H_{\zeta }$ and, as a result, predict the clustering accuracy. The article concludes with an overview of the generalization to more than two classes along with extensive simulations on synthetic and real networks corroborating our findings.

References in corpus (13)

• Emergence of scaling in random 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
• Cooperative Game Theory Approaches for Network Partitioning
• Stochastic blockmodels and community structure in networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Spectral redemption: clustering sparse networks
• Statistical physics of inference: Thresholds and algorithms
• Graph spectra and the detectability of community structure in networks
• Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
• Impact of regularization on Spectral Clustering

Cited by in corpus (2)

• Community detection in networks using graph embeddings
• Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs