Stability-to-instability transition in the structure of large-scale networks

摘要

We examine phase transitions between the “easy,” “hard,” and “unsolvable” phases when attempting to identifynstructure in large complex networks (“community detection”) in the presence of disorder induced by networkn“noise” (spurious links that obscure structure), heat bath temperature T , and system size N. The partition of angraph into q optimally disjoint subgraphs or “communities” inherently requires Potts-type variables. In earliernwork [Philos. Mag. 92, 406 (2012)], when examining power law and other networks (and general associated Pottsnmodels), we illustrated that transitions in the computational complexity of the community detection problemntypically correspond to spin-glass-type transitions (and transitions to chaotic dynamics in mechanical analogs) atnboth high and low temperatures and/or noise. The computationally “hard” phase exhibits spin-glass type behaviornincluding memory effects. The region over which the hard phase extends in the noise and temperature phasendiagram decreases as N increases while holding the average number of nodes per community fixed. This suggestsnthat in the thermodynamic limit a direct sharp transition may occur between the easy and unsolvable phases.nWhen present, transitions at low temperature or low noise correspond to entropy driven (or “order by disorder”)nannealing effects, wherein stability may initially increase as temperature or noise is increased before becomingnunsolvable at sufficiently high temperature or noise. Additional transitions between contending viable solutionsn(such as those at different natural scales) are also possible. Identifying community structure via a dynamicalnapproach where “chaotic-type” transitions were found earlier. The correspondence between the spin-glass-typencomplexity transitions and transitions into chaos in dynamical analogs might extend to other hard computationalnproblems. In this work, we examine large networks (with a power law distribution in cluster size) that have anlarge number of communities (q u0002 1). We infer that large systems at a constant ratio of q to the number ofnnodes N asymptotically tend towards insolvability in the limit of large N for any positive T . The asymptoticnbehavior of temperatures below which structure identification might be possible, T× = O[1/ ln q], decreasesnslowly, so for practical system sizes, there remains an accessible, and generally easy, global solvable phase at lowntemperature. We further employ multivariate Tutte polynomials to show that increasing q emulates increasing Tnfor a general Potts model, leading to a similar stability region at low T . Given the relation between Tutte andnJones polynomials, our results further suggest a link between the above complexity transitions and transitionsnassociated with random knots.