Journal
EPL
Volume 99, Issue 3, Pages -Publisher
IOP Publishing Ltd
DOI: 10.1209/0295-5075/99/38006
Keywords
-
Categories
Funding
- NSF grant [DMR-1106293]
- Division Of Materials Research
- Direct For Mathematical & Physical Scien [1106293] Funding Source: National Science Foundation
Ask authors/readers for more resources
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 T-x approximate to L vertical bar J(e)vertical bar/[N ln q] where vertical bar J(e)vertical bar 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. Copyright (c) EPLA, 2012
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available