Exactly solvable models of adaptive networks

Abstract

A satisfiability (SAT-UNSAT) transition takes place for many optimization problems when the number of constraints, graphically represented by links between variables nodes, is brought above some threshold. If the network of constraints is allowed to adapt by redistributing its links, the SAT-UNSAT transition may be delayed and preceded by an intermediate phase where the structure self-organizes to satisfy the constraints. We present an analytic approach, based on the recently introduced cavity method for large deviations, which exactly describes the two phase transitions delimiting this adaptive intermediate phase. We give explicit results for random bond models subject to the connectivity or rigidity percolation transitions, and compare them with numerical simulations.

4 pages, 4 figures

References in corpus (8)

• The structure and function of complex networks
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Coloring random graphs
• On adaptability and "intermediate phase" in randomly connected networks
• Floppy modes and the free energy: Rigidity and connectivity percolation on Bethe Lattices
• Self-organization with equilibration: a model for the intermediate phase in rigidity percolation
• Rigidity percolation in a field
• The cavity method for large deviations

Cited by in corpus (5)

• Rigidity percolation by next-nearest-neighbor braces on generic and regular isostatic lattices
• Statistical mechanics of error exponents for error-correcting codes
• Finite temperature mechanical instability in disordered lattices
• Hierarchical models of rigidity percolation
• Stability and anomalous entropic elasticity of sub isostatic random-bond networks