Reducing Frustration in Social Systems: Regular and Random Networks

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 first 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 diference 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 et al. to a random network. Interestingly, this model can be mapped onto a k-XOR satisfiability problem that is studied in connection with optimization problems in computer
science. What is the phase of social balance in our original interpretation is the phase of satisfaction of all clauses without frustration in the satisfiability problem of computer science. We generalize the random local algorithm usually applied for solving the k-XOR satisfiability problem to a p-random local algorithm, including a parameter p, that corresponds to the propensity parameter
in the social balance problem. The qualitative efect is a bias towards the optimal solution and a reduction of the needed simulation time. As a third generalization, we study the model of social balance on two-dimensional triangular lattices. As a function of p we find a phase transition between diferent kind of absorbing states. The phases difer by the existence of an infinitely
connected (percolated) cluster. From a finite-size scaling analysis we numerically determine the critical exponents of the transition. The exponents satisfy the known hyperscaling relations. The transition of triad dynamics between diferent absorbing states belongs to a universality class with new critical exponents.