TY - JOUR
T1 - Merge-split Markov chain Monte Carlo for community detection
AU - Peixoto, Tiago P.
N1 - Publisher Copyright:
© 2020 American Physical Society.
PY - 2020/7
Y1 - 2020/7
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85089554696&partnerID=8YFLogxK
U2 - 10.1103/PhysRevE.102.012305
DO - 10.1103/PhysRevE.102.012305
M3 - Article
C2 - 32794904
AN - SCOPUS:85089554696
SN - 2470-0045
VL - 102
JO - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
JF - Physical Review E - Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics
IS - 1
M1 - 012305
ER -