Hierarchical Block Structures and High-resolution Model Selection in Large Networks

Abstract

Discovering and characterizing the large-scale topological features in empirical networks are crucial steps in understanding how complex systems function. However, most existing methods used to obtain the modular structure of networks suffer from serious problems, such as being oblivious to the statistical evidence supporting the discovered patterns, which results in the inability to separate actual structure from noise. In addition to this, one also observes a resolution limit on the size of communities, where smaller but well-defined clusters are not detectable when the network becomes large. This phenomenon occurs not only for the very popular approach of modularity optimization, which lacks built-in statistical validation, but also for more principled methods based on statistical inference and model selection, which do incorporate statistical validation in a formally correct way. Here we construct a nested generative model that, through a complete description of the entire network hierarchy at multiple scales, is capable of avoiding this limitation, and enables the detection of modular structure at levels far beyond those possible with current approaches. Even with this increased resolution, the method is based on the principle of parsimony, and is capable of separating signal from noise, and thus will not lead to the identification of spurious modules even on sparse networks. Furthermore, it fully generalizes other approaches in that it is not restricted to purely assortative mixing patterns, directed or undirected graphs, and ad hoc hierarchical structures such as binary trees. Despite its general character, the approach is tractable, and can be combined with advanced techniques of community detection to yield an efficient algorithm that scales well for very large networks.

18 pages, 9 figures + Supplemental Material

References in corpus (26)

• Fast unfolding of communities in large networks
• Uncovering the overlapping community structure of complex networks in nature and society
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Hierarchical structure and the prediction of missing links in networks
• Stochastic blockmodels and community structure in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Mixture models and exploratory analysis in networks
• Extracting the hierarchical organization of complex systems
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Phase transition in the detection of modules in sparse networks
• Graph spectra and the detectability of community structure in networks
• A Bayesian Approach to Network Modularity
• The entropy of network ensembles
• Parsimonious module inference in large networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Uncovering latent structure in valued graphs: A variational approach
• Community Detection as an Inference Problem
• Maximum likelihood: extracting unbiased information from complex networks
• Role models for complex networks
• Multifractal Network Generator
• Eigenvalue Spectra of Modular Networks
• (Un)detectable cluster structure in sparse networks

Cited by in corpus (85)

• Identification of core-periphery structure in networks
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Efficiently inferring community structure in bipartite networks
• Inferring the mesoscale structure of layered, edge-valued and time-varying networks
• Evaluating Overfit and Underfit in Models of Network Community Structure
• Network reconstruction and community detection from dynamics
• Modeling sequences and temporal networks with dynamic community structures
• Estimating the number of communities in a network
• Selective Exposure shapes the Facebook News Diet
• 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
• Efficient method for estimating the number of communities in a network
• Reconstructing networks with unknown and heterogeneous errors
• Statistical inference of assortative community structures
• Estimating the resolution limit of the map equation in community detection
• A Deep Generative Model for Graph Layout
• Consistencies and inconsistencies between model selection and link prediction in networks
• Consistency of community structure in complex 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
• Collective dynamics of stock market efficiency
• Exploring the solution landscape enables more reliable network community detection
• Merge-split Markov chain Monte Carlo for community detection
• Link prediction with hyperbolic geometry
• Delineating Parameter Unidentifiabilities in Complex Models
• Community Detection in Bipartite Networks with Stochastic Blockmodels
• Network structure, metadata and the prediction of missing nodes and annotations
• Revealing In-Block Nestedness: detection and benchmarking
• Revealing consensus and dissensus between network partitions
• Stochastic block model and exploratory analysis in signed networks
• Disentangling homophily, community structure and triadic closure in networks
• Cross-validation estimate of the number of clusters in a network
• Tensorial and bipartite block models for link prediction in layered networks and temporal networks
• Multiplex decomposition of non-Markovian dynamics and the hidden layer reconstruction problem
• Hierarchical community structure in networks
• Hierarchical benchmark graphs for testing community detection algorithms
• Demarcating Geographic Regions using Community Detection in Commuting Networks with Significant Self-Loops
• Hierarchical mutual information for the comparison of hierarchical community structures in complex networks
• Deep Graphs - a general framework to represent and analyze heterogeneous complex systems across scales
• Identifying multi-scale communities in networks by asymptotic surprise
• Mapping flows on sparse networks with missing links
• Detection and localization of change points in temporal networks with the aid of stochastic block models
• Algorithmic detectability threshold of the stochastic block model
• Recurrent patterns of user behavior in different electoral campaigns: A Twitter analysis of the Spanish general elections of 2015 and 2016
• Clustering for epidemics on networks: a geometric approach
• Optimal redundancy against disjoint vulnerabilities in networks
• Ordered community detection in directed networks
• Weighted Community Detection and Data Clustering Using Message Passing
• Multiple phases in modularity-based community detection
• Relationship between ideology and language in the Catalan independence context
• Atomic subgraphs and the statistical mechanics of networks
• Analytical Formulation of the Block-Constrained Configuration Model
• Network reconstruction via the minimum description length principle
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Identifying hubs in directed networks
• Finite size analysis of the detectability limit of the stochastic block model
• Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
• Latent Poisson models for networks with heterogeneous density
• Limits and trade-offs of topological network robustness
• Decoding communities in networks
• Self-falsifiable Hierarchical Detection of Overlapping Communities On Social Networks
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• The Fitness-Corrected Block Model, or how to create maximum-entropy data-driven spatial social networks
• Identifying bias in cluster quality metrics
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Towards a generalization of information theory for hierarchical partitions
• Compression-based inference of network motif sets
• Stochastic resetting in a networked multiparticle system with correlated transitions
• Core-periphery Detection Based on Masked Bayesian Non-negative Matrix Factorization
• The Infinity Mirror Test for Graph Models
• Consistency between ordering and clustering methods for graphs
• Emergence of metastability in frustrated oscillatory networks: the key role of hierarchical modularity
• A Statistical Model of Bipartite Networks: Application to Cosponsorship in the United States Senate
• Learning common structures in a collection of networks. An application to food webs
• Hierarchical clustering of bipartite data sets based on the statistical significance of coincidences
• Finding community structure using the ordered random graph model
• On role extraction for digraphs via neighbourhood pattern similarity
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Anatomy of Elite and Mass Polarization in Social Networks
• A multilevel network approach to revealing patterns of online political selective exposure
• Negative Ties Highlight Hidden Extremes in Social Media Polarization
• Can x2vec Save Lives? Integrating Graph and Language Embeddings for Automatic Mental Health Classification