Merge-split Markov chain Monte Carlo for community detection

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

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.

Original languageEnglish
Article number012305
Number of pages1
JournalPhysical review. E
Volume102
Issue number1-1
DOIs
Publication statusPublished - 13 Jul 2020

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Condensed Matter Physics

Fingerprint

Dive into the research topics of 'Merge-split Markov chain Monte Carlo for community detection'. Together they form a unique fingerprint.

Cite this