论文标题
合并斯普利特马尔可夫链蒙特卡洛用于社区检测
Merge-split Markov chain Monte Carlo for community detection
论文作者
论文摘要
我们基于能够根据随机块模型（SBM）定义的，可以有效地从网络分区的后验分布中有效采样基于组的合并和分裂。我们演示了基于组之间单个节点的移动方案如何系统地从后验分布中正确地取样，即使在小型网络上也可以正确采样，以及我们的合并阶段方法的表现如何明显更好，并在典型情况下通过多个数量级的混合时间改善了马尔可夫链的混合时间。我们还展示了该方案如何直接扩展到SBM的嵌套版本，从而产生层次网络分区的渐近精确样本。
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.
