  We derive rigorous bounds for well-defined community structure in complex
networks for a stochastic block model (SBM) benchmark. In particular, we
analyze the effect of inter-community "noise" (inter-community edges) on any
"community detection" algorithm's ability to correctly group nodes assigned to
a planted partition, a problem which has been proven to be NP complete in a
standard rendition. Our result does not rely on the use of any one particular
algorithm nor on the analysis of the limitations of inference. Rather, we turn
the problem on its head and work backwards to examine when, in the first place,
well defined structure may exist in SBMs.The method that we introduce here
could potentially be applied to other computational problems. The objective of
community detection algorithms is to partition a given network into optimally
disjoint subgraphs (or communities). Similar to k-SAT and other combinatorial
optimization problems, "community detection" exhibits different phases.
Networks that lie in the "unsolvable phase" lack well-defined structure and
thus have no partition that is meaningful. Solvable systems splinter into two
disparate phases: those in the "hard" phase and those in the "easy" phase. As
befits its name, within the easy phase, a partition is easy to achieve by known
algorithms. When a network lies in the hard phase, it still has an underlying
structure yet finding a meaningful partition which can be checked in polynomial
time requires an exhaustive computational effort that rapidly increases with
the size of the graph. When taken together, (i) the rigorous results that we
report here on when graphs have an underlying structure and (ii) recent results
concerning the limits of rather general algorithms, suggest bounds on the hard
phase.
