View article

Reduction of frustration was the driving force in an approach to social balance as it was recently considered by Antal et al. [T. Antal, P. L. Krapivsky, and S. Redner, Phys. Rev. E 72, 036121 (2005)]. We generalize their triad dynamics to -cycle dynamics for arbitrary integer . 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 is related to being even or odd. As a second generalization we dilute the all-to-all coupling as considered by Antal et al. to a random network with connection probability . Interestingly, this model can be mapped to a satisfiability problem of computer science. The phase of social balance in our original interpretation then becomes the phase of satisfaction of all logical clauses in the satisfiability problem. In common to the cases we study, the ideal solution without any …