The stability to instability transition in the structure of large scale networks
arXiv:1204.4167 · doi:10.1103/PhysRevE.86.066106
Abstract
We examine phase transitions between the easy, hard, and the unsolvable phases when attempting to identify structure in large complex networks (community detection) in the presence of disorder induced by network noise (spurious links that obscure structure), heat bath temperature , and system size . When present, transitions at low temperature or low noise correspond to entropy driven (or "order by disorder") annealing effects wherein stability may initially increase as temperature or noise is increased before becoming unsolvable at sufficiently high temperature or noise. Additional transitions between contending viable solutions (such as those at different natural scales) are also possible. When analyzing community structure via a dynamical approach, "chaotic-type" transitions were previously identified [Phil. Mag. {\bf 92} 406 (2012)]. The correspondence between the spin-glass-type complexity transitions and transitions into chaos in dynamical analogs might extend to other hard computational problems. In this work, we examine large networks that have a large number of communities. We infer that large systems at a constant ratio of to the number of nodes asymptotically tend toward insolvability in the limit of large for any positive . The asymptotic behavior of temperatures below which structure identification might be possible, , decreases slowly, so for practical system sizes, there remains an accessible, and generally easy, global solvable phase at low temperature. We further employ multivariate Tutte polynomials to show that increasing emulates increasing for a general Potts model, leading to a similar stability region at low . Given the relation between Tutte and Jones polynomials, our results further suggest a link between the above complexity transitions and transitions associated with random knots.
arXiv comment26 pages, 24 figures
References in corpus (50)
- Fast unfolding of communities in large networks
- Finding and evaluating community structure in networks
- Community detection in graphs
- Maps of random walks on complex networks reveal community structure
- Near linear time algorithm to detect community structures in large-scale networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Comparing community structure identification
- Defining and identifying communities in networks
- Critical phenomena in complex networks
- Community detection algorithms: a comparative analysis
- Statistical Mechanics of Community Detection
- Detecting the overlapping and hierarchical community structure of complex networks
- The performance of modularity maximization in practical contexts
- Epidemics and percolation in small-world networks
- Synchronization reveals topological scales in complex networks
- Detecting fuzzy community structures in complex networks with a Potts model
- Limits of modularity maximization in community detection
- Community detection in networks with positive and negative links
- Phase transition in the detection of modules in sparse networks
- Narrow scope for resolution-limit-free community detection
- Detecting network communities by propagating labels under constraints
- Multiresolution community detection for megascale networks by information-based replica correlations
- Community Detection as an Inference Problem
- The number of guards needed by a museum: A phase transition in vertex covering of random graphs
- Critical load and congestion instabilities in scale-free networks
- Local resolution-limit-free Potts model for community detection
- Phase Transition in the Number Partitioning Problem
- Percolation and Epidemic Thresholds in Clustered Networks
- Generalized Elitzur's Theorem and Dimensional Reduction
- Statistical significance of communities in networks
- Spectral methods for the detection of network community structure: a comparative analysis
- Robustness of the avalanche dynamics in data packet transport on scale-free networks
- Phase transition in a directed traffic flow network
- Uncovering the community structure associated with the diffusion dynamics of networks
- Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
- Effective and exact holographies from symmetries and dualities
- Community Detection in Complex Networks by Dynamical Simplex Evolution
- A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
- Disorder induced rounding of the phase transition in the large q-state Potts model
- Zero-free regions for multivariate Tutte polynomials (alias Potts-model partition functions) of graphs and matroids
- The Random-bond Potts model in the large-q limit
- Combinatorial approach to Modularity
- Disorder driven phase transitions of the large q-state Potts model in 3d
- Phase Transition in Multiprocessor Scheduling
- Global disorder transition in the community structure of large-q Potts systems
- Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
- Locating phase transitions in computationally hard problems
- Zeros of the Potts Model Partition Function in the Large- Limit
- Phase transition and computational complexity in a stochastic prime number generator
Cited by in corpus (8)
- Glassy Phase of Optimal Quantum Control
- Algorithmic detectability threshold of the stochastic block model
- Information theoretic approach to ground-state phase transitions for two and three-dimensional frustrated spin systems
- Toward a Theory of Phase Transitions in Quantum Control Landscapes
- Local multiresolution order in community detection
- Inference of hidden structures in complex physical systems by multi-scale clustering
- Order-to-chaos transition in the hardness of random Boolean satisfiability problems
- Topological Phase Transitions in a Constrained Two-Qubit Quantum Control Landscape