2020/06/03 by Lorenzo Dall'Amico, Lorenzo Dall’Amico, Dall'Amico, Lorenzo +4
Computer Science · Mathematics · Physics and Astronomy · #Applied mathematics #Combinatorics #Complex Network Analysis Techniques #Computer science #FOS: Computer and information sciences #Hessian equation #Hessian matrix #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical analysis #Mathematics #Opinion Dynamics and Social Influence #Physics #Social and Information Networks (cs.SI) #Statistical physics #Topological and Geometric Data Analysis #cs.LG #cs.SI #stat.ML
paper · pdf · doi:10.48550/arxiv.2006.04510
openalex publication_date 2020/06/03 · openalex created_date 2020/06/12 · arxiv created 2020/10/26 · arxiv updated 2020/10/27 · openalex updated_date 2026/07/28
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.