Bayesian stochastic blockmodeling

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.

44 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 (27)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• 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
• Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities
• 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
• Dynamic stochastic blockmodels for time-evolving social networks
• Parsimonious module inference in large networks
• Community detection in networks: Structural communities versus ground truth
• Learning Latent Block Structure in Weighted Networks
• Community Detection as an Inference Problem
• Community detection, link prediction, and layer interdependence in multilayer networks
• Clique Graphs and Overlapping Communities
• Nonparametric weighted stochastic block models
• Model selection and hypothesis testing for large-scale network models with overlapping groups
• 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
• (Un)detectable cluster structure in sparse networks
• Consistencies and inconsistencies between model selection and link prediction in networks
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• Predicting human preferences using the block structure of complex social 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