摘要：Random graph models and associated inference problems such as the stochastic block model play an eminent role in computer science, discrete mathematics and statistics. Based on non-rigorous arguments physicists predicted the existence of a generic phase transition that separates a "replica symmetric phase" where statistical inference is impossible from a phase where the detection of the "ground truth" is information-theoretically possible. In this paper we prove a contiguity result that shows that detectability is indeed impossible within the replica-symmetric phase for a broad class of models. In particular, this implies the detectability conjecture for the disassortative stochastic block model from [Decelle et al.: Phys Rev E 2011]. Additionally, we investigate key features of the replica symmetric phase such as the nature of point-to-set correlations (`reconstruction').
关键词：Random factor graph; bounds for condensation phase transition; Potts antiferromagnet; diluted k-spin model; stochastic block model
