Detectability thresholds and optimal algorithms for community structure in dynamic networks
arXiv:1506.06179 · doi:10.1103/PhysRevX.6.031005
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.
arXiv comment9 pages, 3 figures
References in corpus (31)
- Mixing patterns in networks
- Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
- Stochastic blockmodels and community structure in networks
- Dynamical interplay between awareness and epidemic spreading in multiplex networks
- Diffusion dynamics on multiplex networks
- Mathematical Formulation of Multi-Layer Networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Mapping change in large 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
- Avalanche Collapse of Interdependent Network
- Temporal Link Prediction using Matrix and Tensor Factorizations
- Growing multiplex networks
- A Bayesian Approach to Network Modularity
- Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
- 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
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- Congestion induced by the structure of multiplex networks
- A state-space mixed membership blockmodel for dynamic network tomography
- The Nishimori line and Bayesian Statistics
- Multilayer stochastic block models reveal the multilayer structure of complex networks
- Phase transitions in semisupervised clustering of sparse networks
- Robust reconstruction on trees is determined by the second eigenvalue
- 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 (47)
- 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
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- 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
- Spectral Clustering for Multiple Sparse Networks: I
- Community Detection and Improved Detectability in Multiplex Networks
- 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
- Using Motif Transitions for Temporal Graph Generation
- Spectral estimation of the percolation transition in clustered networks
- 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