Phase Transitions for the Cavity Approach to the Clique Problem on Random Graphs

被引：0
作者：
Alexandre Gaudillière
Benedetto Scoppola
Elisabetta Scoppola
Massimiliano Viale
机构：
[1] Université de Provence,LATP, CNRS
[2] University of Rome “Tor Vergata”,Dipartimento di Matematica
[3] University of Rome “Roma Tre”,Dipartimento di Matematica
[4] University of Rome “La Sapienza”,Dipartimento di Fisica
来源：
Journal of Statistical Physics | 2011年 / 145卷
关键词：
Phase transitions; Disordered systems; Random graphs; Cliques; Probabilistic cellular automaton;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We give a rigorous proof of two phase transitions for a disordered statistical mechanics system used to define an algorithm to find large cliques inside Erdös random graphs. Such a system is a conservative probabilistic cellular automaton inspired by the cavity method originally introduced in spin glass theory.
引用
收藏
页码：1127 / 1155
页数：28
相关论文
共 16 条
  • [1] Bradde S.(2010)Aligning graphs and finding substructures by a cavity approach Europhys. Lett. 89 37009-217
  • [2] Braunstein A.(2003)Metastability for stochastic dynamics with a parallel heat bath updating rule J. Stat. Phys. 110 183-812
  • [3] Mahmoudi H.(2011)Sampling the Fermi statistics and other conditional product measures Ann. Inst. Henri Poincaré Probab. Stat. 47 790-915
  • [4] Tria F.(2007)Some spin glass ideas applies to the clique problem J. Stat. Phys. 126 895-170
  • [5] Weigt M.(1990)Statistical mechanics of probabilistic cellular automata J. Stat. Phys. 59 117-undefined
  • [6] Zecchina R.(undefined)undefined undefined undefined undefined-undefined
  • [7] Cirillo E.N.M.(undefined)undefined undefined undefined undefined-undefined
  • [8] Nardi F.R.(undefined)undefined undefined undefined undefined-undefined
  • [9] Gaudilliere A.(undefined)undefined undefined undefined undefined-undefined
  • [10] Reygner J.(undefined)undefined undefined undefined undefined-undefined
12