Nonparametric Bayesian inference of the microcanonical stochastic block model

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.

24 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 (18)

• Modularity and community structure in networks
• 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
• Stochastic blockmodels and community structure in networks
• Community detection in networks: A user guide
• An information-theoretic framework for resolving community structure in complex networks
• Missing and spurious interactions and the reconstruction of complex networks
• Phase transition in the detection of modules in sparse networks
• A Bayesian Approach to Network Modularity
• The entropy of network ensembles
• Parsimonious module inference in large networks
• Community detection in networks: Structural communities versus ground truth
• Estimating the number of communities in a network
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• Bayesian Model Selection of Stochastic Block Models
• Active Learning for Hidden Attributes in Networks

Cited by in corpus (67)

• 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
• 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 $k$-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
• Network reconstruction via the minimum description length principle
• Atomic subgraphs and the statistical mechanics of networks
• Analytical Formulation of the Block-Constrained Configuration Model
• 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
• Entropy of microcanonical finite-graph ensembles
• Spectral partitioning in equitable graphs
• 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
• Large deviations of connected components in the stochastic block model
• Detect opinion-based groups and reveal polarisation in survey data
• Single-trajectory map equation
• Loan maturity aggregation in interbank lending networks obscures mesoscale structure and economic functions
• Quantifying metadata relevance to network block structure using description length
• The Feature-First Block Model
• Partition and Code: learning how to compress graphs
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Mixture Models and Networks -- Overview of Stochastic Blockmodelling
• Network compression with configuration models and the minimum description length
• Probabilistic Multilayer Networks
• Nondiagonal Mixture of Dirichlet Network Distributions for Analyzing a Stock Ownership Network
• Drug-disease networks and drug repurposing
• Fragility of spectral clustering for networks with an overlapping structure