Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
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.
BibTeX
@inproceedings{NEURIPS2020_54391c87,
author = {Dall\textquotesingle Amico, Lorenzo and Couillet, Romain and Tremblay, Nicolas},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {7486--7497},
publisher = {Curran Associates, Inc.},
title = {Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/54391c872fe1c8b4f98095c5d6ec7ec7-Paper.pdf},
volume = {33},
year = {2020}
}