Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
arXiv:2006.04510
Abstract
This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an extension of the Bethe-Hessian matrix is proposed, which benefits from the positive correlation in the class labels and in their temporal evolution and is designed to be applicable to any dynamical graph with a community structure. Under the dynamical degree-corrected stochastic block model, in the case of two classes of equal size, we demonstrate and support with extensive simulations that our proposed algorithm is capable of making non-trivial community reconstruction as soon as theoretically possible, thereby reaching the optimal detectability threshold and provably outperforming competing spectral methods.
References in corpus (15)
- Emergence of scaling in random networks
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Stochastic blockmodels and community structure in networks
- High-resolution measurements of face-to-face contact patterns in a primary school
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Mitigation of infectious disease at school: targeted class closure vs school closure
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Compressive Spectral Clustering
- A unified framework for spectral clustering in sparse graphs
- Revealing latent factors of temporal networks for mesoscale intervention in epidemic spread
- Compressive spectral embedding: sidestepping the SVD
- Spectral Inference Methods on Sparse Graphs: Theory and Applications