Nonparametric Bayesian inference of the microcanonical stochastic block model
arXiv:1610.02703 · doi:10.1103/PhysRevE.95.012317
Abstract
A principled approach to characterize the hidden structure of networks is to formulate generative models, and then infer their parameters from data. When the desired structure is composed of modules or "communities", a suitable choice for this task is the stochastic block model (SBM), where nodes are divided into groups, and the placement of edges is conditioned on the group memberships. Here, we present a nonparametric Bayesian method to infer the modular structure of empirical networks, including the number of modules and their hierarchical organization. We focus on a microcanonical variant of the SBM, where the structure is imposed via hard constraints, i.e. the generated networks are not allowed to violate the patterns imposed by the model. We show how this simple model variation allows simultaneously for two important improvements over more traditional inference approaches: 1. Deeper Bayesian hierarchies, with noninformative priors replaced by sequences of priors and hyperpriors, that not only remove limitations that seriously degrade the inference on large networks, but also reveal structures at multiple scales; 2. A very efficient inference algorithm that scales well not only for networks with a large number of nodes and edges, but also with an unlimited number of modules. We show also how this approach can be used to sample modular hierarchies from the posterior distribution, as well as to perform model selection. We discuss and analyze the differences between sampling from the posterior and simply finding the single parameter estimate that maximizes it. Furthermore, we expose a direct equivalence between our microcanonical approach and alternative derivations based on the canonical SBM.
arXiv comment24 pages, 9 figures, 1 table. Code is freely available as part of graph-tool at https://graph-tool.skewed.de . See also the HOWTO at https://graph-tool.skewed.de/static/doc/demos/inference/inference.html . Minor typos fixed in most recent version
References in corpus (33)
- Community structure in social and biological networks
- Modularity and community structure in networks
- Community detection in graphs
- Power-law distributions in empirical data
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Resolution limit in community detection
- An efficient, multiple range random walk algorithm to calculate the density of states
- Stochastic blockmodels and community structure in networks
- Community detection in networks: A user guide
- Self-similar community structure in organisations
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex 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
- Phase transition in the detection of modules in sparse networks
- A Bayesian Approach to Network Modularity
- The entropy of network ensembles
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Parsimonious module inference in large networks
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Community detection in networks: Structural communities versus ground truth
- Estimating the number of communities in a network
- Entropy of stochastic blockmodel ensembles
- Model Selection for Degree-corrected Block Models
- A network approach to analyzing highly recombinant malaria parasite genes
- Model selection and hypothesis testing for large-scale network models with overlapping groups
- Breaking of ensemble equivalence in networks
- Trust transitivity in social networks
- Ensemble nonequivalence in random graphs with modular structure
- Bayesian Model Selection of Stochastic Block Models
- Active Learning for Hidden Attributes in Networks
Cited by in corpus (68)
- Social physics
- A network approach to topic models
- A Review of Stochastic Block Models and Extensions for Graph Clustering
- 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
- Selective Exposure shapes the Facebook News Diet
- Bayesian stochastic blockmodeling
- Nonparametric weighted stochastic block models
- A Clarified Typology of Core-Periphery Structure in Networks
- Efficient method for estimating the number of communities in a network
- Reconstructing networks with unknown and heterogeneous errors
- Finding multiple core-periphery pairs in networks
- Statistical inference of assortative community structures
- Diversity of information pathways drives scaling and sparsity in real-world networks
- Core-periphery structure requires something else in the network
- Consistencies and inconsistencies between model selection and link prediction in networks
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- Exploring the solution landscape enables more reliable network community detection
- Detecting anomalous citation groups in journal networks
- Merge-split Markov chain Monte Carlo for community detection
- Learning physical properties of anomalous random walks using graph neural networks
- Link prediction with hyperbolic geometry
- Community Detection in Bipartite Networks with Stochastic Blockmodels
- Message passing methods on complex networks
- Revealing consensus and dissensus between network partitions
- Multilayer Network Science: from Cells to Societies
- Disentangling homophily, community structure and triadic closure in networks
- Reconstructing networks
- Representative community divisions of networks
- Multilayer Networks for Text Analysis with Multiple Data Types
- Mapping flows on sparse networks with missing links
- Interplay between -core and community structure in complex networks
- Hierarchical core-periphery structure in networks
- Ordered community detection in directed networks
- Symptom extraction from the narratives of personal experiences with COVID-19 on Reddit
- Dynamic Hidden-Variable Network Models
- Analytical Formulation of the Block-Constrained Configuration Model
- Network reconstruction via the minimum description length principle
- Atomic subgraphs and the statistical mechanics of networks
- Latent Poisson models for networks with heterogeneous density
- Implicit models, latent compression, intrinsic biases, and cheap lunches in community detection
- Duality between predictability and reconstructability in complex systems
- Mesoscopic scales in hierarchical configuration models
- Spectral partitioning in equitable graphs
- Entropy of microcanonical finite-graph ensembles
- Mutual information and the encoding of contingency tables
- Bayesian Learning of Graph Substructures
- Large-scale multi-objective influence maximisation with network downscaling
- Compression-based inference of network motif sets
- Description length of canonical and microcanonical models
- Minimum entropy stochastic block models neglect edge distribution heterogeneity
- On the Structural Properties of Social Networks and their Measurement-calibrated Synthetic Counterparts
- Multilayer Modularity Belief Propagation To Assess Detectability Of Community Structure
- Single-trajectory map equation
- Large deviations of connected components in the stochastic block model
- Detect opinion-based groups and reveal polarisation in survey data
- Mixture Models and Networks -- Overview of Stochastic Blockmodelling
- Loan maturity aggregation in interbank lending networks obscures mesoscale structure and economic functions
- Network compression with configuration models and the minimum description length
- The Feature-First Block Model
- Partition and Code: learning how to compress graphs
- Quantifying metadata relevance to network block structure using description length
- Systematic assessment of the quality of fit of the stochastic block model for empirical networks
- Drug-disease networks and drug repurposing
- Probabilistic Multilayer Networks
- Fragility of spectral clustering for networks with an overlapping structure
- Nondiagonal Mixture of Dirichlet Network Distributions for Analyzing a Stock Ownership Network