Social balance as a satisfiability problem of computer science
Radicchi, F, Vilone, D, Yoon, S, Meyer-Ortmanns, HPhys. Rev. E 75, 026106 (2007)
Times cited: 12
Abstract
Reduction of frustration was the driving force in an approach to social
balance as it was recently considered by Antal [T. Antal, P. L.
Krapivsky, and S. Redner, Phys. Rev. E 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 to a random network with
connection probability w < 1. 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
frustration always exists, but the question actually is as to whether
this solution can be found by means of a local stochastic algorithm
within a finite time. The answer depends on the choice of parameters.
After establishing the mapping between the two classes of models, we
generalize the social-balance problem to a diluted network topology for
which the satisfiability problem is usually studied. On the other hand,
in connection with the satisfiability problem we generalize the random
local algorithm to a p-random local algorithm, including a parameter p
that corresponds to the propensity parameter in the social balance
problem. The qualitative effect of the inclusion of this parameter is a
bias towards the optimal solution and a reduction of the needed
simulation time.