  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.
