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

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

2012-04-16

arxiv.org/abs/1204.3649v2

Physics

Condensed Matter

Statistical Mechanics

6 pages, 2 figures, minor editing, revised references

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Global disorder transition in the community structure of large q Potts systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Global disorder transition in the community structure of large q Potts systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Global disorder transition in the community structure of large q Potts systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-288585