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.

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

References in corpus (7)

• Finding community structure in networks using the eigenvectors of matrices
• Resolution limit in community detection
• Stochastic blockmodels and community structure in networks
• Missing and spurious interactions and the reconstruction of complex networks
• Nonparametric weighted stochastic block models
• Efficient method for estimating the number of communities in a network
• 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