Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
This work addresses community detection for researchers in network analysis, offering an incremental improvement by refining an existing spectral method to handle degree heterogeneity more effectively.
The paper tackles the problem of community detection in sparse heterogeneous graphs by revisiting the Bethe-Hessian matrix, showing that spectral clustering with a specific parameter value becomes insensitive to degree heterogeneity and predicting clustering accuracy, with results validated through simulations on synthetic and real networks.
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 = ζ$, clustering is shown to be insensitive to the degree heterogeneity. We then study the behavior of the informative eigenvector of $H_ζ$ 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.