Parsimonious module inference in large networks

Abstract

We investigate the detectability of modules in large networks when the number of modules is not known in advance. We employ the minimum description length (MDL) principle which seeks to minimize the total amount of information required to describe the network, and avoid overfitting. According to this criterion, we obtain general bounds on the detectability of any prescribed block structure, given the number of nodes and edges in the sampled network. We also obtain that the maximum number of detectable blocks scales as $\sqrt{N}$, where $N$ is the number of nodes in the network, for a fixed average degree $<k>$. We also show that the simplicity of the MDL approach yields an efficient multilevel Monte Carlo inference algorithm with a complexity of $O(\tau N\log N)$, if the number of blocks is unknown, and $O(\tau N)$ if it is known, where $\tau$ is the mixing time of the Markov chain. We illustrate the application of the method on a large network of actors and films with over $10^6$ edges, and a dissortative, bipartite block structure.

5 pages, 4 figures + Supplemental Material

References in corpus (29)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Community detection algorithms: a comparative analysis
• Statistical Mechanics of Community Detection
• Stochastic blockmodels and community structure in networks
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Mixture models and exploratory analysis in networks
• Limits of modularity maximization in community detection
• Analysis of the structure of complex networks at different resolution levels
• Phase transition in the detection of modules in sparse networks
• An efficient and principled method for detecting communities in networks
• Graph spectra and the detectability of community structure in networks
• A Bayesian Approach to Network Modularity
• The entropy of network ensembles
• Consistency of community detection in networks under degree-corrected stochastic block models
• Stochastic blockmodels with growing number of classes
• Community Detection as an Inference Problem
• Maximum likelihood: extracting unbiased information from complex networks
• Clique Graphs and Overlapping Communities
• Entropy of stochastic blockmodel ensembles
• Role models for complex networks
• Spatial Guilds in the Serengeti Food Web Revealed by a Bayesian Group Model
• The interplay of microscopic and mesoscopic structure in complex networks
• Comparative Study for Inference of Hidden Classes in Stochastic Block Models

Cited by in corpus (89)

• Social physics
• A network approach to topic models
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Learning Latent Block Structure in Weighted Networks
• A Review of Stochastic Block Models and Extensions for Graph Clustering
• Identifying modular flows on multilayer networks reveals highly overlapping organization in social systems
• Identification of core-periphery structure in networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• 20 years of network community detection
• Efficiently inferring community structure in bipartite networks
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Spectral entropies as information-theoretic tools for complex network comparison
• Evaluating Overfit and Underfit in Models of Network Community Structure
• The many facets of community detection in complex networks
• Modeling sequences and temporal networks with dynamic community structures
• Bayesian stochastic blockmodeling
• Nonparametric weighted stochastic block models
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Multilayer stochastic block models reveal the multilayer structure of complex networks
• Clustering implies geometry in networks
• A Clarified Typology of Core-Periphery Structure in Networks
• Reconstructing networks with unknown and heterogeneous errors
• Statistical inference of assortative community structures
• Estimating the resolution limit of the map equation in community detection
• Streaming Graph Challenge: Stochastic Block Partition
• Consistencies and inconsistencies between model selection and link prediction in networks
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Efficient community detection of network flows for varying Markov times and bipartite networks
• Adapting the Stochastic Block Model to Edge-Weighted Networks
• Multiscale dynamical embeddings of complex networks
• Estimating the number of communities in networks by spectral methods
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Network structure, metadata and the prediction of missing nodes and annotations
• Revealing consensus and dissensus between network partitions
• Finding network communities using modularity density
• Optimal hypothesis testing for stochastic block models with growing degrees
• Cross-validation estimate of the number of clusters in a network
• Different approaches to community detection
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Hierarchical community structure in networks
• The organization of the interbank network and how ECB unconventional measures affected the e-MID overnight market
• Centrality metrics and localization in core-periphery networks
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Separating Polarization from Noise: Comparison and Normalization of Structural Polarization Measures
• The Infinite Degree Corrected Stochastic Block Model
• Deep Graphs - a general framework to represent and analyze heterogeneous complex systems across scales
• Detection and localization of change points in temporal networks with the aid of stochastic block models
• Micro, Meso, Macro: the effect of triangles on communities in networks
• Ordered community detection in directed networks
• Weighted Community Detection and Data Clustering Using Message Passing
• Detectability of the spectral method for sparse graph partitioning
• Robustness modularity in complex networks
• Atomic subgraphs and the statistical mechanics of networks
• Latent Poisson models for networks with heterogeneous density
• State aggregations in Markov chains and block models of networks
• Critical field-exponents for secure message-passing in modular networks
• Mapping Flows on Bipartite Networks
• A Tractable Fully Bayesian Method for the Stochastic Block Model
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Entropy of labeled versus unlabeled networks
• Link community detection through global optimization and the inverse resolution limit of partition density
• Regular Decomposition: an information and graph theoretic approach to stochastic block models
• Finite size analysis of the detectability limit of the stochastic block model
• Limits and trade-offs of topological network robustness
• Decoding communities in networks
• A shadowing problem in the detection of overlapping communities: lifting the resolution limit through a cascading procedure
• Spectral partitioning in equitable graphs
• Decoupling approximation robustly reconstructs directed dynamical networks
• Community Detection with the Map Equation and Infomap: Theory and Applications
• Link Prediction Accuracy on Real-World Networks Under Non-Uniform Missing Edge Patterns
• Importance of initial conditions in the polarization of complex networks
• The likelihood-ratio test for multi-edge network models
• A network community detection method with integration of data from multiple layers and node attributes
• Minimum entropy stochastic block models neglect edge distribution heterogeneity
• Stochastic fluctuations and the detectability limit of network communities
• Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences
• Quantifying metadata relevance to network block structure using description length
• Corrected Bayesian information criterion for stochastic block models
• Partition and Code: learning how to compress graphs
• On role extraction for digraphs via neighbourhood pattern similarity
• Network compression with configuration models and the minimum description length
• Thermodynamics of the Minimum Description Length on Community Detection
• A Formal Critique of the Value of the Colombian Páramo
• Absence of a resolution limit in in-block nestedness
• Discrimination universally determines reconstruction of multiplex networks
• Goodness-of-fit Test for Latent Block Models
• Error-Correcting Decoders for Communities in Networks
• Hyperbolic Multiplex Network Embedding with Maps of Random Walk