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

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

2010-08-16

arxiv.org/abs/1008.2699v3

Physics

Physics and Society

23 pages, 18 figures

Scientific paper

10.1080/14786435.2011.616547

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. 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.

Affiliated with

Also associated with

No associations

Rating

Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178052