Robust Detection of Dynamic Community Structure in Networks

Abstract

We describe techniques for the robust detection of community structure in some classes of time-dependent networks. Specifically, we consider the use of statistical null models for facilitating the principled identification of structural modules in semi-decomposable systems. Null models play an important role both in the optimization of quality functions such as modularity and in the subsequent assessment of the statistical validity of identified community structure. We examine the sensitivity of such methods to model parameters and show how comparisons to null models can help identify system scales. By considering a large number of optimizations, we quantify the variance of network diagnostics over optimizations (`optimization variance') and over randomizations of network structure (`randomization variance'). Because the modularity quality function typically has a large number of nearly-degenerate local optima for networks constructed using real data, we develop a method to construct representative partitions that uses a null model to correct for statistical noise in sets of partitions. To illustrate our results, we employ ensembles of time-dependent networks extracted from both nonlinear oscillators and empirical neuroscience data.

18 pages, 11 figures

References in corpus (38)

• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Community detection in graphs
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Synchronization in complex networks
• Resolution limit in community detection
• Specificity and stability in topology of protein networks
• Temporal Networks
• Community Structure in Time-Dependent, Multiscale, and Multiplex Networks
• Hierarchical structure and the prediction of missing links in networks
• Statistical Mechanics of Community Detection
• Structure and tie strengths in mobile communication networks
• Dynamic reconfiguration of human brain networks during learning
• Quantifying social group evolution
• Chimera States for Coupled Oscillators
• The performance of modularity maximization in practical contexts
• Synchronization reveals topological scales in complex networks
• Consensus clustering in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Generating surrogate data for time series with several simultaneously measured variables
• The Dynamics of Protest Recruitment through an Online Network
• Narrow scope for resolution-limit-free community detection
• Rotating Spiral Waves with Phase-Randomized Core in Non-locally Coupled Oscillators
• Comparing Community Structure to Characteristics in Online Collegiate Social Networks
• Synchronization processes in complex networks
• Statistical significance of communities in networks
• The Influence of Network Topology on Sound Propagation in Granular Materials
• Temporal Evolution of Financial Market Correlations
• Spectral tripartitioning of networks
• From brain to earth and climate systems: Small-world interaction networks or not?
• The weighted random graph model
• Dynamic communities in multichannel data: An application to the foreign exchange market during the 2007--2008 credit crisis
• Unraveling Spurious Properties of Interaction Networks with Tailored Random Networks
• Party Polarization in Congress: A Network Science Approach
• Constrained Randomisation of Weighted Networks
• Revisiting algorithms for generating surrogate time series
• Probing non-Gaussianities in the CMB on an incomplete sky using surrogates

Cited by in corpus (56)

• Multilayer Networks
• The structure and dynamics of multilayer networks
• Controllability of Brain Networks
• Mathematical Formulation of Multi-Layer Networks
• Random walks and diffusion on networks
• The Multilayer Nature of Ecological Networks
• Community Discovery in Dynamic Networks: a Survey
• MuxViz: A Tool for Multilayer Analysis and Visualization of Networks
• Detecting the community structure and activity patterns of temporal networks: a non-negative tensor factorization approach
• Dynamic network drivers of seizure generation, propagation and termination in human epilepsy
• Network Analysis of Particles and Grains
• Developmental increases in white matter network controllability support a growing diversity of brain dynamics
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Multilayer Brain Networks
• Cognitive chimera states in human brain networks
• Modeling sequences and temporal networks with dynamic community structures
• Think Locally, Act Locally: The Detection of Small, Medium-Sized, and Large Communities in Large Networks
• Brain Network Adaptability Across Task States
• Extraction of Force-Chain Network Architecture in Granular Materials Using Community Detection
• Choosing Wavelet Methods, Filters, and Lengths for Functional Brain Network Construction
• Multi-scale community organization of the human structural connectome and its relationship with resting-state functional connectivity
• Persistent homology of time-dependent functional networks constructed from coupled time series
• Element-centric clustering comparison unifies overlaps and hierarchy
• Detectability thresholds and optimal algorithms for community structure in dynamic networks
• Evolution of network architecture in a granular material under compression
• Nonparametric weighted stochastic block models
• Resolving structural variability in network models and the brain
• Reduced integration and improved segregation of functional brain networks in Alzheimer's disease
• Benchmark model to assess community structure in evolving networks
• Cross-Linked Structure of Network Evolution
• Individual Differences in Dynamic Functional Brain Connectivity Across the Human Lifespan
• Topological and geometric measurements of force chain structure
• Fast consensus clustering in complex networks
• Dynamics on Modular Networks with Heterogeneous Correlations
• Stability of spontaneous, correlated activity in mouse auditory cortex
• Post-processing partitions to identify domains of modularity optimization
• Detecting Dynamic Community Structure in Functional Brain Networks Across Individuals: A Multilayer Approach
• Versatility of nodal affiliation to communities
• Community detection in directed acyclic graphs
• Dynamic Reconfiguration of Brain Functional Network in Stroke
• Architecture and evolution of semantic networks in mathematics texts
• Gene communities in co-expression networks across different tissues
• Consistency landscape of network communities
• Surrogate-assisted network analysis of nonlinear time series
• A Fast and Efficient Incremental Approach toward Dynamic Community Detection
• Topological Data Analysis of Human Brain Networks Through Order Statistics
• Dissociable changes in functional network topology underlie early category learning and development of automaticity
• Node-Centric Graph Learning from Data for Brain State Identification
• Network analysis of 3D complex plasma clusters in a rotating electric field
• Forecasting landslides using community detection on geophysical satellite data
• Emergence and persistence of communities in coevolutionary networks
• Detection of Functional Communities in Networks of Randomly Coupled Oscillators Using the Dynamic-Mode Decomposition
• Time-dependent community structure in legislation cosponsorship networks in the Congress of the Republic of Peru
• Linking Through Time: Memory-Enhanced Community Discovery in Temporal Networks
• Modeling and Analysis of the Lead-Lag Network of Economic Indicators
• Refinement for community structures of bipartite networks