  In this paper, we study the sensitivity of the spectral clustering based
community detection algorithm subject to a Erdos-Renyi type random noise model.
We prove phase transitions in community detectability as a function of the
external edge connection probability and the noisy edge presence probability
under a general network model where two arbitrarily connected communities are
interconnected by random external edges. Specifically, the community detection
performance transitions from almost perfect detectability to low detectability
as the inter-community edge connection probability exceeds some critical value.
We derive upper and lower bounds on the critical value and show that the bounds
are identical when the two communities have the same size. The phase transition
results are validated using network simulations. Using the derived expressions
for the phase transition threshold we propose a method for estimating this
threshold from observed data.
