Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian

Lorenzo Dall'Amico (1) , Romain Couillet (1, 2) , Nicolas Tremblay (1)

1 GIPSA-GAIA - GIPSA Pôle Géométrie, Apprentissage, Information et Algorithmes
2 L2S - Laboratoire des signaux et systèmes

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

Mots clés: community detection; sparsity; dynamical graphs; spectral clustering; unsupervised learning

Domaines: Intelligence artificielle [cs.AI]

Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay. Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian. NeurIPS 2020 - 34th Conference on Neural Information Processing Systems, Dec 2020, Vancouver (virtual), Canada. ⟨hal-03172642⟩