Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
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.
Code (1)
Tasks
Community DetectionStochastic Block ModelSimilar Papers 제목 키워드 기반
Community detection in the sparse hypergraph stochastic block model
We consider the community detection problem in sparse random hypergraphs. Angelini et al. (2015) conjectured the existence of a sharp threshold on model parameters for community detection in sparse hypergraphs generated …
Community DetectionStochastic Block ModelSparse random hypergraphs: Non-backtracking spectra and community detection
We consider the community detection problem in a sparse $q$-uniform hypergraph $G$, assuming that $G$ is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the n…
Community DetectionDimensionality ReductionStochastic Block ModelEvaluating Community Detection Algorithms for Progressively Evolving Graphs
Many algorithms have been proposed in the last ten years for the discovery of dynamic communities. However, these methods are seldom compared between themselves. In this article, we propose a generator of dynamic graphs …
Community DetectionDescriptiveDynamic Community DetectionData-driven Clustering in Ad-hoc Networks based on Community Detection
High demands for industrial networks lead to increasingly large sensor networks. However, the complexity of networks and demands for accurate data require better stability and communication quality. Conventional clusteri…
ClusteringCommunity DetectionIncNSA: Detecting communities incrementally from time-evolving networks based on node similarity
Many real-world systems can be abstracted as networks. As those systems always change dynamically in nature, the corresponding networks also evolve over time in general, and detecting communities from such time-evolving …
Community DetectionDynamic Community DetectionGraph Clustering