Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem

Abstract

Reduction of frustration was the driving force in an approach to social balance as it was recently considered by Antal \emph{et al.} [ T. Antal, P. L. Krapivsky, and S. Redner, Phys. Rev. E {\bf 72}, 036121 (2005). ]. We generalize their triad dynamics to $k$-cycle dynamics for arbitrary integer $k$. We derive the phase structure, determine the stationary solutions and calculate the time it takes to reach a frozen state. The main difference in the phase structure as a function of $k$ is related to $k$ being even or odd. As a second generalization we dilute the all-to-all coupling as considered by Antal \emph{et al.} to a random network with connection probability $w<1$. ...

20 pages, 14 figures. Submitted to Phys. Rev. E

References in corpus (9)

• Dynamics of Social Balance on Networks
• Stochastic gene expression as a many body problem
• Clustering of solutions in the random satisfiability problem
• The Entropy of the K-Satisfiability Problem
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• A variational description of the ground state structure in random satisfiability problems
• Simplest random K-satisfiability problem
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms

Cited by in corpus (15)

• Dynamical Models Explaining Social Balance and Evolution of Cooperation
• Phase transition in a network model of social balance with Glauber dynamics
• Coupled dynamics of node and link states in complex networks: A model for language competition
• Universality class of triad dynamics on a triangular lattice
• Fragmentation transition in a coevolving network with link-state dynamics
• Dynamics of link states in complex networks: The case of a majority rule
• Balanced-imbalanced transitions in indirect reciprocity dynamics on networks
• External bias in the model of isolation of communities
• Pseudo-Phase Transitions of Ising and Baxter-Wu Models in Two-Dimensional Finite-Size Lattices
• Topological transition in a coupled dynamic in random networks
• On the dynamics of Social Balance on general networks (with an application to XOR-SAT)
• Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
• Dynamics of Social Balance on Networks: The Emergence of Multipolar Societies
• The physics of custody
• Some recent attempts to simulate the Heider balance problem