Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives

Abstract

Phase transitions in spin-glass type systems and, more recently, in related computational problems have gained broad interest in disparate arenas. In the current work, we focus on the “community detection” problem when cast in terms of a general Potts spin-glass type problem. As such, our results apply to rather broad Potts spin-glass type systems. Community detection describes the general problem of partitioning a complex system involving many elements into optimally decoupled “communities” of such elements. We report on phase transitions between solvable and unsolvable regimes. A solvable region may further split into “easy” and “hard” phases. Spin-glass type phase transitions appear at both low and high temperatures (or noise). Low-temperature transitions correspond to an “order by disorder” type effect wherein fluctuations render the system ordered or solvable. Separate transitions appear at higher temperatures into a disordered (or an unsolvable) phase. Different sorts of randomness lead to disparate behaviors. We illustrate the spin glass character of both transitions and report on memory effects. We further relate Potts type spin systems to mechanical analogs and suggest how chaotic-type behavior in general thermodynamic systems can indeed naturally arise in hard computational problems and spin glasses. The correspondence between the two types of transitions (spin glass and dynamic) is likely to extend across a larger spectrum of spin-glass type systems and hard computational problems. We briefly discuss potential implications of these transitions in complex many-body physical systems.

Keywords:

• phase transitions
• statistical physics
• computer simulation
• community detection
• spin-glass type transition

Acknowledgments

This work was supported by NSF grant DMR-1106293 (ZN). We also wish to thank S. Chakrabarty, R. Darst, P. Johnson, B. Leonard, A. Middleton, M.E.J. Newman, D. Reichman, V. Tran, and L. Zdeborova for discussions and ongoing work.

Notes

Notes

1. Setting, in Equation (1), A _ij  = δ_|i−j|,1 with sites i and j of a square lattice and |i − j| the distance between the sites (with the lattice constant set to unity) yields a q-state Potts model on a square lattice. For an unweighted graph, for which a _ij  = b _ij  = 1, Equation (1) becomes the standard Potts model on a square lattice: , with .

2. Similar expressions and analysis appear for an inertial system (wherein the force is given by ). The damping accentuates the difference between converging and diverging trajectories as seen on the experimental time-scale as discussed in the text.