Volume 99, Number 3, August 2012
|Number of page(s)||6|
|Section||Interdisciplinary Physics and Related Areas of Science and Technology|
|Published online||08 August 2012|
Global disorder transition in the community structure of large-q Potts systems
Department of Physics, Washington University in St. Louis - Campus Box 1105, 1 Brookings Drive, St. Louis, MO 63130, USA
Received: 2 May 2012
Accepted: 8 July 2012
We examine a global disorder transition when identifying community structure in an arbitrary complex network. Earlier, we illustrated (Hu D. et al., Philos. Mag., 92 (2012) 406) 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 where |Je| 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.
PACS: 89.75.Fb – Structures and organization in complex systems / 64.60.Cn – Order-disorder transformations / 64.60.De – Statistical mechanics of model systems (Ising model, Potts model, field-theory models, Monte Carlo techniques, etc.)
© EPLA, 2012
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.