Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
This addresses the problem of tracking evolving communities in sparse dynamic networks for applications like social network analysis, with incremental improvements to spectral methods.
The paper tackles community detection in sparse time-evolving graphs by proposing a fast spectral algorithm based on an extended Bethe-Hessian matrix that leverages temporal correlations. The algorithm achieves non-trivial community reconstruction at the optimal detectability threshold, provably outperforming competing spectral methods in simulations under a dynamical degree-corrected stochastic block model.
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.