2003/12/31 by Alfredo Braunstein, A. Braunstein, Riccardo Zecchina +1 · 2 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Applied mathematics #Bayesian Modeling and Causal Inference #Cluster analysis #Clustering coefficient #Computation #Computer science #Data Management and Algorithms #Decimation #Discrete mathematics #Entropy (arrow of time) #Error Correcting Code Techniques #Graph #Logarithm #Mathematical analysis #Mathematical optimization #Mathematics #Physics #Product (mathematics) #Random graph #Space (punctuation) #Statistics #cond-mat.dis-nn #cs.CC
paper · pdf · doi:10.1088/1742-5468/2004/06/p06007
published as J. Stat. Mech., P06007 (2004) · 13 pages, 3 figures
arxiv created 2004/06/08 · openalex publication_date 2004/06/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
It has been shown experimentally that a decimation algorithm based on survey propagation (SP) equations allows one to solve efficiently some combinatorial problems over random graphs. We show that these equations can be derived as sum–product equations for the computation of marginals in an extended space where the variables are allowed to take an additional value—*—when they are not forced by the combinatorial constraints. An appropriate 'local equilibrium condition' cost/energy function is introduced and its entropy is shown to coincide with the expected logarithm of the number of clusters of solutions as computed by SP. These results may help to clarify the geometrical notion of clusters assumed by SP for random K -SAT or random graph colouring (where it is conjectured to be exact) and help to explain which kind of clustering operation or approximation is enforced in general/small sized models in which it is known to be inexact.