%0 Book Section %1 statphys23_0133 %A Radicchi, F. %A Vilone, D. %A Meyer-ortmanns, H. %B Abstract Book of the XXIII IUPAP International Conference on Statistical Physics %C Genova, Italy %D 2007 %E Pietronero, Luciano %E Loreto, Vittorio %E Zapperi, Stefano %K algorithms dynamics nonequilibrium optimization problems spin statphys23 stochastic systems topic-11 %T Spin Dynamics as an Approach to Social Balance and an Optimization Problem of Computer Science %U http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=133 %X We consider $k$-cycle spin dynamics as a generalization of triad dynamics that was recently considered by Antal et al. T. Antal, P. L. Krapivsky, and S. Redner, Phys. Rev. E 72 , 036121 (2005) as an approach to social balance. We study the phase structure as a function of a propensity parameter and the dilution of the network. We observe phase transitions between active and absorbing states which are reached after a time that is characteristic for the corresponding phases. For diluted networks we identify a mapping from the approach to social balance to a satisfiability problem of computer science, the so-called $k$-XOR-SAT problem. In particular, we map the spin-dynamics to the algorithm which is usually used to solve the $k$-XOR-SAT-problem. Due to an additional parameter, contained in the spin dynamics, $k$-XOR-SAT-problems become solvable which are unsolvable otherwise. On a regular triangular topology the triad dynamics leads to a phase transition for which we identify a new universality class by measuring a set of critical exponents. In common to the approach of social balance and the solution of the satisfiability problem is the search for a solution by means of a local stochastic updating algorithm. In both cases the solution is known to exist, nevertheless the local algorithm or the spin dynamics are only able to find the solution when the driving parameter of the phase transition exceeds a certain critical value.

@incollection{statphys23_0133, abstract = {We consider $k$-cycle spin dynamics as a generalization of triad dynamics that was recently considered by Antal {\it et al.} [ T. Antal, P. L. Krapivsky, and S. Redner, Phys. Rev. E {\bf 72} , 036121 (2005) ] as an approach to social balance. We study the phase structure as a function of a propensity parameter and the dilution of the network. We observe phase transitions between active and absorbing states which are reached after a time that is characteristic for the corresponding phases. For diluted networks we identify a mapping from the approach to social balance to a satisfiability problem of computer science, the so-called $k$-XOR-SAT problem. In particular, we map the spin-dynamics to the algorithm which is usually used to solve the $k$-XOR-SAT-problem. Due to an additional parameter, contained in the spin dynamics, $k$-XOR-SAT-problems become solvable which are unsolvable otherwise. On a regular triangular topology the triad dynamics leads to a phase transition for which we identify a new universality class by measuring a set of critical exponents. In common to the approach of social balance and the solution of the satisfiability problem is the search for a solution by means of a local stochastic updating algorithm. In both cases the solution is known to exist, nevertheless the local algorithm or the spin dynamics are only able to find the solution when the driving parameter of the phase transition exceeds a certain critical value.}, added-at = {2007-06-20T10:16:09.000+0200}, address = {Genova, Italy}, author = {Radicchi, F. and Vilone, D. and Meyer-ortmanns, H.}, biburl = {https://www.bibsonomy.org/bibtex/20eb4d3a08e9a2cfac9a6dceaf7c58f78/statphys23}, booktitle = {Abstract Book of the XXIII IUPAP International Conference on Statistical Physics}, editor = {Pietronero, Luciano and Loreto, Vittorio and Zapperi, Stefano}, interhash = {09bf88e6fc6399a394eca06b6da0b84e}, intrahash = {0eb4d3a08e9a2cfac9a6dceaf7c58f78}, keywords = {algorithms dynamics nonequilibrium optimization problems spin statphys23 stochastic systems topic-11}, month = {9-13 July}, timestamp = {2007-06-20T10:16:12.000+0200}, title = {Spin Dynamics as an Approach to Social Balance and an Optimization Problem of Computer Science}, url = {http://st23.statphys23.org/webservices/abstract/preview_pop.php?ID_PAPER=133}, year = 2007 }