Modularity from Fluctuations in Random Graphs and Complex Networks

Abstract

The mechanisms by which modularity emerges in complex networks are not well understood but recent reports have suggested that modularity may arise from evolutionary selection. We show that finding the modularity of a network is analogous to finding the ground-state energy of a spin system. Moreover, we demonstrate that, due to fluctuations, stochastic network models give rise to modular networks. Specifically, we show both numerically and analytically that random graphs and scale-free networks have modularity. We argue that this fact must be taken into consideration to define statistically-significant modularity in complex networks.

4 pages

References in corpus (5)

• Finding and evaluating community structure in networks
• Fast algorithm for detecting community structure in networks
• Defining and identifying communities in networks
• Subnetwork hierarchies of biochemical pathways
• Community analysis in social networks

Cited by in corpus (174)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Functional cartography of complex metabolic networks
• Resolution limit in community detection
• Comparing community structure identification
• Critical phenomena in complex networks
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• Detecting the overlapping and hierarchical community structure of complex networks
• Community detection in networks: A user guide
• The worldwide air transportation network: Anomalous centrality, community structure, and cities' global roles
• Community detection in complex networks using Extremal Optimization
• Finding statistically significant communities in networks
• A smart local moving algorithm for large-scale modularity-based community detection
• Community structure in directed networks
• The complex network of global cargo ship movements
• The performance of modularity maximization in practical contexts
• Overlapping Community Detection in Networks: the State of the Art and Comparative Study
• Vertex similarity in networks
• Consensus clustering in complex networks
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Hierarchical modularity in human brain functional networks
• Line Graphs, Link Partitions and Overlapping Communities
• Clustering and Community Detection in Directed Networks: A Survey
• Extracting the hierarchical organization of complex systems
• Limits of modularity maximization in community detection
• The ground truth about metadata and community detection in networks
• Spectral methods for network community detection and graph partitioning
• Classes of complex networks defined by role-to-role connectivity profiles
• Module identification in bipartite and directed networks
• The Statistical Physics of Real-World Networks
• Community detection in networks: Modularity optimization and maximum likelihood are equivalent
• Uncovering space-independent communities in spatial networks
• Robustness of community structure in networks
• Community landscapes: an integrative approach to determine overlapping network module hierarchy, identify key nodes and predict network dynamics
• Modularity-Maximizing Network Communities via Mathematical Programming
• A network approach to topic models
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Community Detection as an Inference Problem
• A General Optimization Technique for High Quality Community Detection in Complex Networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Evaluating Local Community Methods in Networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Identifying network communities with a high resolution
• 20 years of network community detection
• LinkRank: Finding communities in directed networks
• Maximizing Modularity is hard
• On the Origins of Hierarchy in Complex Networks
• Local modularity measure for network clusterizations
• Communities, Knowledge Creation, and Information Diffusion
• Identifying "communities" within energy landscapes
• The many facets of community detection in complex networks
• Delineating geographical regions with networks of human interactions in an extensive set of countries
• Modeling sequences and temporal networks with dynamic community structures
• Fuzzy overlapping communities in networks
• Finding instabilities in the community structure of complex networks
• Statistical significance of communities in networks
• Bayesian stochastic blockmodeling
• When are networks truly modular?
• Social significance of community structure: Statistical view
• Enhancing community detection using a network weighting strategy
• Nonparametric weighted stochastic block models
• Computational Socioeconomics
• Currency and commodity metabolites: Their identification and relation to the modularity of metabolic networks
• Empirical Comparison of Algorithms for Network Community Detection
• Centrality Measures for Networks with Community Structure
• Systemic risk and spatiotemporal dynamics of the US housing market
• Immunization of networks with community structure
• Multiway spectral community detection in networks
• Partitioning and modularity of graphs with arbitrary degree distribution
• Community structure of complex software systems: Analysis and applications
• Finding multiple core-periphery pairs in networks
• Statistical inference of assortative community structures
• Hierarchical Synchrony of Phase Oscillators in Modular Networks
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Core-periphery structure requires something else in the network
• Consistency of community structure in complex networks
• Comparison and validation of community structures in complex networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Metabolic robustness and network modularity: A model study
• Large network community detection by fast label propagation
• Modular architecture facilitates noise-driven control of synchrony in neuronal networks
• Detecting degree symmetries in networks
• Merge-split Markov chain Monte Carlo for community detection
• The Web of Connections between Tourism Companies in Elba: Structure and Dynamics
• Network science: a review focused on tourism
• Detecting communities of triangles in complex networks using spectral optimization
• Robust Detection of Hierarchical Communities from Escherichia coli Gene Expression Data
• Network structure, metadata and the prediction of missing nodes and annotations
• Deterministic Modularity Optimization
• Revealing In-Block Nestedness: detection and benchmarking
• Detection of node group membership in networks with group overlap
• Limitation of multi-resolution methods in community detection
• Network community detection using modularity density measures
• Inversion method for content-based networks
• Measuring Significance of Community Structure in Complex Networks
• Disentangling homophily, community structure and triadic closure in networks
• Process Flow Diagram of an Ammonia Plant as a Complex Network
• Community Detection in Quantum Complex Networks
• Broad lifetime distributions for ordering dynamics in complex networks
• Climatic seasonality may affect ecological network structure: Food webs and mutualistic networks
• Different approaches to community detection
• Genetic Algorithm with a Local Search Strategy for Discovering Communities in Complex Networks
• The inherent community structure of hyperbolic networks
• eBay users form stable groups of common interest
• Representative community divisions of networks
• Improving the performance of algorithms to find communities in networks
• Combinatorial approach to Modularity
• Unveiling Relationships Between Crime and Property in England and Wales Via Density Scale-Adjusted Metrics and Network Tools
• Separating Polarization from Noise: Comparison and Normalization of Structural Polarization Measures
• The effects of degree correlations on network topologies and robustness
• Alternative approach to community detection in networks
• Community detection in networks via nonlinear modularity eigenvectors
• Effect of size heterogeneity on community identification in complex networks
• Identifying multi-scale communities in networks by asymptotic surprise
• Discovering Network Structure Beyond Communities
• Evolution of Coordination in Social Networks: A Numerical Study
• Spatial correlations in attribute communities
• Modularity and Projection of Bipartite Networks
• Communication and correlation among communities
• Analysis of heat kernel highlights the strongly modular and heat-preserving structure of proteins
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Variational Community Partition with Novel Network Structure Centrality Prior
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Ordered community detection in directed networks
• Substance graphs are optimal simple-graph representations of metabolism
• Total variation based community detection using a nonlinear optimization approach
• Multiple phases in modularity-based community detection
• Structural dynamics of plant-pollinator mutualistic networks
• A unified framework for spectral clustering in sparse graphs
• Robustness modularity in complex networks
• Detectability of the spectral method for sparse graph partitioning
• Statistical test for detecting community structure in real-valued edge-weighted graphs
• Maximally modular structure of growing hyperbolic networks
• Latent Poisson models for networks with heterogeneous density
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Detecting groups of similar components in complex networks
• Additive Approximation Algorithms for Modularity Maximization
• Random graphs and real networks with weak geometric coupling
• Criterions for locally dense subgraphs
• Statistical Mechanics of Semi-Supervised Clustering in Sparse Graphs
• Mutual information and the encoding of contingency tables
• Identifying robust features of community structure in complex networks
• Order-disorder transition in the zero-temperature Ising model on random graphs
• On the modularity of 3-regular random graphs and random graphs with given degree sequences
• Habitat variability does not generally promote metabolic network modularity in flies and mammals
• Large Scale Training of Graph Neural Networks for Optimal Markov-Chain Partitioning Using the Kemeny Constant
• Discovering Block Structure in Networks
• Community detection by resistance distance: automation and benchmark testing
• Minimum entropy stochastic block models neglect edge distribution heterogeneity
• Core-Periphery Segregation in Evolving Prisoner's Dilemma Networks
• The Importance of Being Negative: A serious treatment of non-trivial edges in brain functional connectome
• Metrics for Community Analysis: A Survey
• A new edge betweenness measure using a game theoretical approach: an application to hierarchical community detection
• Edge based stochastic block model statistical inference
• Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences
• Generic criticality of community structure in random graphs
• Anatomy of Elite and Mass Polarization in Social Networks
• Clustering evolving data using kernel-based methods
• Designing topological cluster synchronization patterns with the Dirac operator
• A new measure of modularity density for community detection
• Correlation-Based Community Detection
• Emergence of consensus as a modular-to-nested transition in communication dynamics
• Graph model selection by edge probability sequential inference
• Approximate Conditional Sampling for Pattern Detection in Weighted Networks
• CIIA:A New Algorithm for Community Detection
• Hierarchical modularity of nested bow-ties in metabolic networks
• Network-based models for social recommender systems
• Block-corrected Modularity for Community Detection
• Ground state energy of $q$-state Potts model: the minimum modularity
• Modularity of regular and treelike graphs
• Modularity of Erdős-Rényi random graphs