文章基本信息

标题：Charting the Replica Symmetric Phase
本地全文：下载
作者：Amin Coja-Oghlan ; Charilaos Efthymiou ; Nor Jaafari 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：40:1-40:17
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.40
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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