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

23 pages, 18 figures

References in corpus (21)

• Fast unfolding of communities in large networks
• Community detection in graphs
• Maps of random walks on complex networks reveal community structure
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• The performance of modularity maximization in practical contexts
• Finding overlapping communities in networks by label propagation
• Phase transition in the detection of modules in sparse networks
• Community Detection as an Inference Problem
• Limited resolution in complex network community detection with Potts model approach
• Statistical significance of communities in networks
• Orbital order in classical models of transition-metal compounds
• (Un)detectable cluster structure in sparse networks
• Theory of the superglass phase
• Statistical Mechanics of Steiner trees
• Community Detection in Complex Networks by Dynamical Simplex Evolution
• Clustering Phase Transitions and Hysteresis: Pitfalls in Constructing Network Ensembles
• Community Detection with and without Prior Information
• Ground-State Entropy of the Random Vertex-Cover Problem
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems

Cited by in corpus (33)

• Spectral methods for network community detection and graph partitioning
• A network approach to topic models
• Hierarchical Block Structures and High-resolution Model Selection in Large Networks
• Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
• Identification of core-periphery structure in networks
• Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
• Community detection and graph partitioning
• Enhanced detectability of community structure in multilayer networks through layer aggregation
• Glassy Phase of Optimal Quantum Control
• Finding One Community in a Sparse Graph
• Descriptive vs. inferential community detection in networks: pitfalls, myths, and half-truths
• Spectra of random graphs with community structure and arbitrary degrees
• Community detection in networks with unequal groups
• Chaos in spin glasses revealed through thermal boundary conditions
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Limits and performances of algorithms based on simulated annealing in solving sparse hard inference problems
• Universality of modulation length (and time) exponents
• Phase Transitions in Community Detection: A Solvable Toy Model
• Parallel Tempering for the planted clique problem
• Information theoretic approach to ground-state phase transitions for two and three-dimensional frustrated spin systems
• Global disorder transition in the community structure of large-q Potts systems
• The stability to instability transition in the structure of large scale networks
• Multiple phases in modularity-based community detection
• Detectability of the spectral method for sparse graph partitioning
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Automatic Segmentation of Fluorescence Lifetime Microscopy Images of Cells Using Multi-Resolution Community Detection
• Detectability thresholds of general modular graphs
• Local multiresolution order in community detection
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Minimum entropy stochastic block models neglect edge distribution heterogeneity
• The Binomial Spin Glass
• Phase transition for parameter learning of Hidden Markov Models