Bayesian stochastic blockmodeling
arXiv:1705.10225 · doi:10.1002/9781119483298.ch11
Abstract
This chapter provides a self-contained introduction to the use of Bayesian inference to extract large-scale modular structures from network data, based on the stochastic blockmodel (SBM), as well as its degree-corrected and overlapping generalizations. We focus on nonparametric formulations that allow their inference in a manner that prevents overfitting, and enables model selection. We discuss aspects of the choice of priors, in particular how to avoid underfitting via increased Bayesian hierarchies, and we contrast the task of sampling network partitions from the posterior distribution with finding the single point estimate that maximizes it, while describing efficient algorithms to perform either one. We also show how inferring the SBM can be used to predict missing and spurious links, and shed light on the fundamental limitations of the detectability of modular structures in networks.
arXiv comment44 pages, 16 figures. Minor typos fixed. 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
References in corpus (65)
- Community structure in social and biological networks
- Community detection in graphs
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Functional cartography of complex metabolic networks
- 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
- Link communities reveal multiscale complexity in networks
- Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
- 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
- The phase transition in inhomogeneous random graphs
- The ground truth about metadata and community detection in networks
- Class of correlated random networks with hidden variables
- Statistical physics of inference: Thresholds and algorithms
- Phase transition in the detection of modules in sparse networks
- An efficient and principled method for detecting communities in networks
- Structure and inference in annotated networks
- A Bayesian Approach to Network Modularity
- A General Formalism for Inhomogeneous Random Graphs
- Dynamic stochastic blockmodels for time-evolving social networks
- Hierarchical Block Structures and High-resolution Model Selection in Large Networks
- Parsimonious module inference in large networks
- Multiresolution community detection for megascale networks by information-based replica correlations
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Community detection in networks: Structural communities versus ground truth
- Learning Latent Block Structure in Weighted Networks
- Assessing the relevance of node features for network structure
- Community Detection as an Inference Problem
- Community detection, link prediction, and layer interdependence in multilayer networks
- Nonparametric Bayesian inference of the microcanonical stochastic block model
- Inferring the mesoscale structure of layered, edge-valued and time-varying networks
- Random graph models for dynamic networks
- Clique Graphs and Overlapping Communities
- Modeling sequences and temporal networks with dynamic community structures
- Estimating the number of communities in a network
- Network histograms and universality of blockmodel approximation
- Entropy of stochastic blockmodel ensembles
- Detectability thresholds and optimal algorithms for community structure in dynamic networks
- Clustering Network Layers With the Strata Multilayer Stochastic Block Model
- Nonparametric weighted stochastic block models
- Model selection and hypothesis testing for large-scale network models with overlapping groups
- Model Selection for Degree-corrected Block Models
- Multilayer stochastic block models reveal the multilayer structure of complex networks
- A network inference method for large-scale unsupervised identification of novel drug-drug interactions
- Efficient method for estimating the number of communities in a network
- Generalized communities in networks
- Non-parametric Bayesian modeling of complex networks
- Community detection in multi-relational data with restricted multi-layer stochastic blockmodel
- (Un)detectable cluster structure in sparse networks
- Consistencies and inconsistencies between model selection and link prediction in networks
- Structural inference for uncertain networks
- The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
- Accurate and scalable social recommendation using mixed-membership stochastic block models
- Predicting human preferences using the block structure of complex social networks
- The interplay of microscopic and mesoscopic structure in complex networks
- Network structure, metadata and the prediction of missing nodes and annotations
- Ensemble nonequivalence in random graphs with modular structure
- Exact ICL maximization in a non-stationary temporal extension of the stochastic block model for dynamic networks
- Predicting future conflict between team-members with parameter-free models of social networks
Cited by in corpus (20)
- Evaluating Overfit and Underfit in Models of Network Community Structure
- A Clarified Typology of Core-Periphery Structure in Networks
- From the origin of life to pandemics: Emergent phenomena in complex systems
- Local dominance unveils clusters in networks
- Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
- Multilayer Network Science: from Cells to Societies
- Representative community divisions of networks
- Extreme rainfall propagation within Boreal Summer Intraseasonal Oscillation modulated by Pacific sea surface temperature
- Random Spatial Network Models with Core-Periphery Structure
- Detecting mesoscale structures by surprise
- Network mutual information measures for graph similarity
- Community detection for directed networks revisited using bimodularity
- Community Detection in networks by Dynamical Optimal Transport Formulation
- EC-SBM Synthetic Network Generator
- Community detection in bipartite signed networks is highly dependent on parameter choice
- Edge based stochastic block model statistical inference
- Symmetry-driven embedding of networks in hyperbolic space
- Loan maturity aggregation in interbank lending networks obscures mesoscale structure and economic functions
- Anatomy of Elite and Mass Polarization in Social Networks
- Evolution of global development cooperation: An analysis of aid flows with hierarchical stochastic block models