The stability to instability transition in the structure of large scale networks

Details The stability to instability transition in the structure of large scale networks The stability to instability transition in the structure of large scale networks

2012-04-18

arxiv.org/abs/1204.4167v1

Physics

Condensed Matter

Statistical Mechanics

26 pages, 24 figures

Scientific paper

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 $T$, and system size $N$. 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 $q$ to the number of nodes $N$ asymptotically tend toward insolvability in the limit of large $N$ for any positive $T$. The asymptotic behavior of temperatures below which structure identification might be possible, $T_\times =O[1/\log q]$, 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 $q$ emulates increasing $T$ for a general Potts model, leading to a similar stability region at low $T$. 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.

Affiliated with

Also associated with

No associations

Rating

The stability to instability transition in the structure of large scale networks 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 The stability to instability transition in the structure of large scale networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The stability to instability transition in the structure of large scale networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-412450