Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
复制标题
DOI：
10.1103/physreve.75.026106
复制
发表时间：
2006-08
期刊：
影响因子：
--
通讯作者：
F. Radicchi;Daniele Vilone;Sooeyon Yoon;H. Meyer-Ortmanns
中科院分区：
文献类型：
--
作者：
F. Radicchi;Daniele Vilone;Sooeyon Yoon;H. Meyer-Ortmanns
正如Antal等人最近所认为的那样，减少挫折感是社会平衡的驱动力。Antal，P. L. Krapivsky和S. Redner，Phys.Rev.E72，036121（2005）. ].对于任意整数k，我们将它们的三元动力学推广到k -圈动力学.我们推导出的相结构，确定固定的解决方案，并计算所需的时间达到冻结状态。作为k的函数的相位结构中的主要差异与k是偶数还是奇数有关。作为第二个推广，我们将Antal等人所考虑的全对全耦合稀释为连接概率w < 1的随机网络。有趣的是，这个模型可以映射到一个k-XOR-SAT问题上，这个问题在计算机科学中与优化问题有关。在我们最初的解释中，社会平衡的阶段是在计算机科学的可萨蒂斯性问题中所有条款都得到满足而没有挫折的阶段。然而，尽管在我们研究的案例中总是存在没有挫折的理想解，但这并不意味着它曾经达到过，无论是在社会中还是在优化问题中，因为局部动态更新规则可能是这样的，即理想状态是在随着系统规模呈指数级增长的时间内达到的。我们推广的随机局部算法通常适用于解决k-XOR-SAT问题的p -随机局部算法，包括一个参数p，对应于社会平衡问题中的倾向参数。定性的效果是偏向最优解和减少所需的模拟时间。我们建立了稀释网络上社会平衡的k -循环动力学与用p -随机局部算法求解的k-XOR-SAT问题之间的映射。
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 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 et al. to a random network with connection probability w < 1. Interestingly, this model can be mapped onto a k -XOR-SAT 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. Nevertheless, although the ideal solution without frustration always exists in the cases we study, it does not mean that it is ever reached, neither in the society nor in the optimization problem, because the local dynamical updating rules may be such that the ideal state is reached in a time that grows exponentially with the system size. We generalize the random local algorithm usually applied for solving the k -XOR-SAT problem to a p -random local algorithm, including a parameter p , that corresponds to the propensity parameter in the social balance problem. The qualitative effect is a bias towards the optimal solution and a reduction of the needed simulation time. We establish the mapping between the k -cycle dynamics for social balance on diluted networks and the k -XOR-SAT problem solved by a p -random local algorithm.