  Consider a network consisting of two subnetworks (communities) connected by
some external edges. Given the network topology, the community detection
problem can be cast as a graph partitioning problem that aims to identify the
external edges as the graph cut that separates these two subnetworks. In this
paper, we consider a general model where two arbitrarily connected subnetworks
are connected by random external edges. Using random matrix theory and
concentration inequalities, we show that when one performs community detection
via spectral clustering there exists an abrupt phase transition as a function
of the random external edge connection probability. Specifically, the community
detection performance transitions from almost perfect detectability to low
detectability near some critical value of the random external edge connection
probability. We derive upper and lower bounds on the critical value and show
that the bounds are equal to each other when two subnetwork sizes are
identical. Using simulated and experimental data we show how these bounds can
be empirically estimated to validate the detection reliability of any
discovered communities.
