کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8904725 1633755 2018 102 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Information-theoretic thresholds from the cavity method
ترجمه فارسی عنوان
آستانه اطلاعات-نظری از روش حفره
کلمات کلیدی
روش حفره، انتشار عقیده، مدل بلوک تصادفی، گراف رنگ تصادفی، آستانه های نظری اطلاعات،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات (عمومی)
چکیده انگلیسی
Vindicating a sophisticated but non-rigorous physics approach called the cavity method, we establish a formula for the mutual information in statistical inference problems induced by random graphs and we show that the mutual information holds the key to understanding certain important phase transitions in random graph models. We work out several concrete applications of these general results. For instance, we pinpoint the exact condensation phase transition in the Potts antiferromagnet on the random graph, thereby improving prior approximate results (Contucci et al., 2013) [34]. Further, we prove the conjecture from Krzakala et al. (2007) [55] about the condensation phase transition in the random graph coloring problem for any number q≥3 of colors. Moreover, we prove the conjecture on the information-theoretic threshold in the disassortative stochastic block model (Decelle et al., 2011) [35]. Additionally, our general result implies the conjectured formula for the mutual information in Low-Density Generator Matrix codes (Montanari, 2005) [73].
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Advances in Mathematics - Volume 333, 31 July 2018, Pages 694-795
نویسندگان
, , , ,