论文标题
随机块模型中连接组件的大偏差
Large deviations of connected components in the stochastic block model
论文作者
论文摘要
我们研究了随机块模型，该模型通常用于建模社区结构和研究社区检测算法。我们分别考虑了两个块的最大连接组件和最大的双连接组件的情况。我们对它们大小的分布特别感兴趣，包括尾巴的概率小于$ 10^{-800} $。为此，我们使用复杂的马尔可夫链蒙特卡洛模拟来从随机块模型集合中采样图形。我们使用这些数据来研究大型原理所具有的大型泄漏率函数和猜想。此外，我们将分布与众所周知的Erdős-rényi合奏进行了比较，在那里我们注意到渗透阈值和渗透阈值的细微差异。
We study the stochastic block model which is often used to model community structures and study community-detection algorithms. We consider the case of two blocks in regard to its largest connected component and largest biconnected component, respectively. We are especially interested in the distributions of their sizes including the tails down to probabilities smaller than $10^{-800}$. For this purpose we use sophisticated Markov chain Monte Carlo simulations to sample graphs from the stochastic block model ensemble. We use this data to study the large-deviation rate function and conjecture that the large-deviation principle holds. Further we compare the distribution to the well known Erdős-Rényi ensemble, where we notice subtle differences at and above the percolation threshold.
