Merge-split Markov chain Monte Carlo for community detection

Abstract

We present a Markov chain Monte Carlo scheme based on merges and splits of groups that is capable of efficiently sampling from the posterior distribution of network partitions, defined according to the stochastic block model (SBM). We demonstrate how schemes based on the move of single nodes between groups systematically fail at correctly sampling from the posterior distribution even on small networks, and how our merge-split approach behaves significantly better, and improves the mixing time of the Markov chain by several orders of magnitude in typical cases. We also show how the scheme can be straightforwardly extended to nested versions of the SBM, yielding asymptotically exact samples of hierarchical network partitions.

arXiv comment13 pages, 6 figures. Code available at https://graph-tool.skewed.de/static/doc/demos/inference/inference.html

References in corpus (19)

• Community structure in social and biological networks
• Community detection in graphs
• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Modularity from Fluctuations in Random Graphs and 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
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Nonparametric Bayesian inference of the microcanonical stochastic block model
• Network reconstruction and community detection from dynamics
• Estimating the number of communities in a network
• Nonparametric weighted stochastic block models
• A network approach to analyzing highly recombinant malaria parasite genes
• Efficient method for estimating the number of communities in a network
• Reconstructing networks with unknown and heterogeneous errors
• Communities and bottlenecks: Trees and treelike networks have high modularity
• Latent Poisson models for networks with heterogeneous density

Cited by in corpus (12)

• Statistical inference of assortative community structures
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Revealing consensus and dissensus between network partitions
• Disentangling homophily, community structure and triadic closure in networks
• Representative community divisions of networks
• Multilayer Networks for Text Analysis with Multiple Data Types
• Brain tumour genetic network signatures of survival
• Ordered community detection in directed networks
• Compressing network populations with modal networks reveals structural diversity
• Network reconstruction via the minimum description length principle
• 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