Global disorder transition in the community structure of large-q Potts systems

Abstract

We examine a global disorder transition when identifying community structure in an arbitrary complex network. Earlier, we illustrated [Phil. Mag. 92, 406 (2012)] that "community detection" (CD) generally exhibits disordered (or unsolvable) and ordered (solvable) phases of both high and low computational complexity along with corresponding transitions from regular to chaotic dynamics in derived systems. Using an exact generalized dimensional reduction inequality, multivariate Tutte polynomials, and other considerations, we illustrate how increasing the number of communities q emulates increasing the heat bath temperature T for a general weighted Potts model, leading to global disorder in the community structure of arbitrary large graphs. Dimensional reduction bounds lead to results similar to those suggested by mean-field type approaches. Large systems tend toward global insolvability in the limit of large q above a crossover temperature $T_{\times }\approx L|J_e|/[N\ln q]$ where |J_e| is a typical interaction strength, L is the number of edges, and N is the number of nodes. For practical system sizes, a solvable phase is generally accessible at low T. The global nature of the disorder transition does not preclude solutions by local CD algorithms (even those that employ global cost function parameters) as long as community evaluations are locally determined.

arXiv comment6 pages, 2 figures; accepted version with minor editing, corrected indices in one equation, results unchanged, revised references

References in corpus (42)

• Fast unfolding of communities in large networks
• Finding and evaluating community structure in networks
• Community detection in graphs
• Finding community structure in very large networks
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Resolution limit in community detection
• 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
• Network Physiology reveals relations between network topology and physiological function
• 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
• Analysis of the structure of complex networks at different resolution levels
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• 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
• Graph spectra and the detectability of community structure in networks
• Multiresolution community detection for megascale networks by information-based replica correlations
• A sequential algorithm for fast clique percolation
• Community Detection as an Inference Problem
• Local resolution-limit-free Potts model for community detection
• Limited resolution in complex network community detection with Potts model approach
• Generalized Elitzur's Theorem and Dimensional Reduction
• Spectral methods for the detection of network community structure: a comparative analysis
• (Un)detectable cluster structure in sparse networks
• Uncovering the community structure associated with the diffusion dynamics of networks
• Mean-field driven first-order phase transitions in systems with long-range interactions
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Limitation of multi-resolution methods in community detection
• Community Detection in Complex Networks by Dynamical Simplex Evolution
• A Replica Inference Approach to Unsupervised Multi-Scale Image Segmentation
• 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
• Disorder driven phase transitions of the large q-state Potts model in 3d
• The Tutte-Potts connection in the presence of an external magnetic field
• Finding mesoscopic communities in sparse networks
• Zeros of the Potts Model Partition Function in the Large-$q$ Limit

Cited by in corpus (9)

• Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
• Phase Transitions in Community Detection: A Solvable Toy Model
• The stability to instability transition in the structure of large scale networks
• Multiple phases in modularity-based community detection
• Counting the number of metastable states in the modularity landscape: Algorithmic detectability limit of greedy algorithms in community detection
• Metastability in the Potts model: exact results in the large q limit
• Detectability thresholds of general modular graphs
• Inference of hidden structures in complex physical systems by multi-scale clustering
• Local multiresolution order in community detection