Reconstruction and Estimation in the Planted Partition Model
Elchanan Mossel Supported by NSF grant DMS-1106999 and DOD ONR grant N000141110140 Department of Statistics, UC Berkeley Department of Computer Science, UC Berkeley Joe Neeman∗ Department of Statistics, UC Berkeley Allan Sly Department of Statistics, UC Berkeley
Abstract
The planted partition model (also known as the stochastic blockmodel) is a classical cluster-exhibiting random graph model that has been extensively studied in statistics, physics, and computer science. In its simplest form, the planted partition model is a model for random graphs on $n$ nodes with two equal-sized clusters, with an between-class edge probability of $q$ and a within-class edge probability of $p$ . Although most of the literature on this model has focused on the case of increasing degrees (ie. $pn,qn\to\infty$ as $n\to\infty$ ), the sparse case $p,q=O(1/n)$ is interesting both from a mathematical and an applied point of view.
中文速览
稀疏随机图中的聚类问题长期存在一个来自统计物理学的精确猜想：当图的平均度为常数、参数满足 $(a-b)^2 < 2(a+b)$ 时，任何算法都无法从图中识别出两个隐藏社区，反之则可以。本文从数学上严格证明了这一猜想的"不可能"半边，即在阈值以下，不仅无法找到与真实划分相关的二分，甚至连模型参数 $a$、$b$ 本身都无法被一致估计——planted partition 模型与同等密度的普通 Erdős–Rényi 随机图在统计上完全无法区分（互相毗连，mutually contiguous）。与此同时，作者还给出了阈值以上的正面结果：通过统计图中短环（short cycles）的数量，可以构造出 $a$ 和 $b$ 的一致估计量，算法复杂度为多项式时间。这项工作在聚类问题、Bethe 格上的自旋玻璃模型与树上的信息重建问题（reconstruction problem）之间建立了严格的数学联系，为理解稀疏网络中社区发现的根本极限提供了坚实理论基础。
原文 arXiv:1202.1499;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1202.1499v4