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

2019/01/25 by Lorenzo Dall'Amico, Romain Couillet, Dall'Amico, Lorenzo +3
Computer Science · Mathematics · Physics and Astronomy · #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Physics and Society (physics.soc-ph) #Social and Information Networks (cs.SI) #cs.LG #cs.SI #physics.soc-ph #stat.ML

paper · pdf · doi:10.48550/arxiv.1901.09715

arxiv created 2019/10/09 · arxiv updated 2019/10/10

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²-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.

Related

• Community detection with the Bethe-Hessian
• Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
• Analysis of spectral clustering algorithms for community detection: the general bipartite setting
• Spectral community detection in heterogeneous large networks
• Perfect Spectral Clustering with Discrete Covariates