Detectability thresholds and optimal algorithms for community structure in dynamic networks

Abstract

We study the fundamental limits on learning latent community structure in dynamic networks. Specifically, we study dynamic stochastic block models where nodes change their community membership over time, but where edges are generated independently at each time step. In this setting (which is a special case of several existing models), we are able to derive the detectability threshold exactly, as a function of the rate of change and the strength of the communities. Below this threshold, we claim that no algorithm can identify the communities better than chance. We then give two algorithms that are optimal in the sense that they succeed all the way down to this limit. The first uses belief propagation (BP), which gives asymptotically optimal accuracy, and the second is a fast spectral clustering algorithm, based on linearizing the BP equations. We verify our analytic and algorithmic results via numerical simulation, and close with a brief discussion of extensions and open questions.

9 pages, 3 figures

References in corpus (15)

• Stochastic blockmodels and community structure in networks
• Diffusion dynamics on multiplex networks
• Robust Detection of Dynamic Community Structure in Networks
• Phase transition in the detection of modules in sparse networks
• Structure and inference in annotated networks
• A Bayesian Approach to Network Modularity
• Dynamic stochastic blockmodels for time-evolving social networks
• Learning Latent Block Structure in Weighted Networks
• Community Detection as an Inference Problem
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Analytical computation of the epidemic threshold on temporal networks
• Congestion induced by the structure of multiplex networks
• Phase transitions in semisupervised clustering of sparse networks
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models
• Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs

Cited by in corpus (46)

• Social physics
• Community Discovery in Dynamic Networks: a Survey
• The ground truth about metadata and community detection in networks
• On community structure in complex networks: challenges and opportunities
• Random graph models for dynamic networks
• Modeling sequences and temporal networks with dynamic community structures
• Bayesian stochastic blockmodeling
• Joint Embedding of Graphs
• Community detection in networks without observing edges
• A Framework for the Construction of Generative Models for Mesoscale Structure in Multilayer Networks
• Super-resolution community detection for layer-aggregated multilayer networks
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Reciprocity, community detection, and link prediction in dynamic networks
• Estimating Causal Peer Influence in Homophilous Social Networks by Inferring Latent Locations
• Flow stability for dynamic community detection
• Community Detection and Improved Detectability in Multiplex Networks
• Spectral Clustering for Multiple Sparse Networks: I
• Algorithmic detectability threshold of the stochastic block model
• Generative model for reciprocity and community detection in networks
• Machine Learning assisted Chimera and Solitary states in Networks
• Dynamic Hidden-Variable Network Models
• General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
• Spectral estimation of the percolation transition in clustered networks
• Using Motif Transitions for Temporal Graph Generation
• Inference for growing trees
• Community detectability and structural balance dynamics in signed networks
• Inference of Edge Correlations in Multilayer Networks
• Resolution Limits for Detecting Community Changes in Multilayer Networks
• Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
• Detectability thresholds of general modular graphs
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• Message-Passing on Hypergraphs: Detectability, Phase Transitions and Higher-Order Information
• Detectability of Macroscopic Structures in Directed Asymmetric Stochastic Block Model
• Percolation is Odd
• Network interpolation
• Optimal timescale for community detection in growing networks
• Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
• Navigating differential structures in complex networks
• The Atlas for the Aspiring Network Scientist
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Compressing the chronology of a temporal network with graph commutators
• Community Detection with Node Attributes and its Generalization
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Sketch-based community detection in evolving networks
• Exploring and comparing temporal clustering methods
• A Class of Temporal Hierarchical Exponential Random Graph Models for Longitudinal Network Data