Social balance as a satisfiability problem of computer science

Area of Science:

• Complex Systems
• Statistical Physics
• Computational Social Science

Background:

• Social balance theory addresses frustration reduction in social networks.
• Previous models (Antal et al.) used all-to-all coupling and triad dynamics.

Purpose of the Study:

• Generalize social balance models to k-cycle dynamics and diluted networks.
• Map social balance to the satisfiability problem.
• Investigate parameter effects on reaching optimal solutions.

Main Methods:

• Generalized triad dynamics to k-cycle dynamics.
• Introduced diluted network topology with connection probability w<1.
• Mapped the model to a satisfiability problem.
• Developed a p-random local algorithm.

Main Results:

• Derived phase structures, stationary solutions, and time to reach frozen states.
• Phase structure depends on whether k is even or odd.
• Social balance phase maps to satisfiability phase.
• Optimal solutions always exist but may not be reachable in finite time.

Conclusions:

• The generalization reveals key differences in phase structure for even/odd k.
• The mapping to satisfiability provides new insights and computational approaches.
• Parameter p in the p-random local algorithm biases towards optimal solutions and reduces simulation time.