Boolean decision problems with competing interactions on scale-free networks: Critical thermodynamics

New posting to arXiv: this paper considered the thermodynamics of Boolean variables on scale-free networks – with the fascinating result that there is a phase transition if the graph is scale-free.

The abstract is:

We study the critical behavior of Boolean variables on scale-free networks with competing interactions (Ising spin glasses). Our analytical results for the disorder/network-decay-exponent phase diagram are verified using large-scale Monte Carlo simulations. When the probability of positive (ferromagnetic) and negative (antiferromagnetic) interactions is the same, the system undergoes a finite-temperature spin-glass transition if the exponent that describes the decay of the interaction degree in the scale-free graph is strictly larger than 3. However, when the exponent is equal to or less than 3, a spin-glass phase is stable for all temperatures. The robustness of both the ferromagnetic and spin-glass phases suggest that Boolean decision problems on scale-free networks are quite stable to local perturbations.

The paper can be downloaded from arXiv at: http://arxiv.org/abs/1202.1153