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 intercommunity 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.
Consider two arbitrarily connected communities with internal adjacency matrices @math and @math and network sizes @math and @math , respectively. The external connections between these two communities are characterized by an @math adjacency matrix @math , where each entry in @math is a Bernoulli( @math ) random variable. Let @math . The overall @math adjacency matrix of the community structure can be represented as . The widely used stochastic block model @cite_31 is a special case of ) when the two community structures are generated by connected Erdos-Renyi random graphs parameterized by the within-community connection probability @math ( @math ). Our network model is more general since we only assume random connection probability @math on the external edges and we allow the within-community adjacency matrices @math to be arbitrary. In this paper we consider the noisy setting in which the adjacency matrix @math is corrupted by a random adjacency matrix @math such that the observed adjacency matrix is @math . The adjacency matrix @math is generated by a Erdos-Renyi random graph with edge connection probability @math . Note that this model only allows random insertions and not deletions of edges.
@cite_31
2964292545
We consider the problem of clustering a graph @math into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables @math , where @math is the incidence matrix of a graph @math , @math is the vector of unknown vertex variables (with a uniform prior), and @math is a noise vector with Bernoulli @math i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of @math is possible if and only the graph @math is connected, with a sharp threshold at the edge probability @math for Erdős-Renyi random graphs. The first goal of this paper is to determine how the edge probability @math needs to scale to allow exact recovery in the presence of noise. Defining the degree rate of the graph by @math , it is shown that exact recovery is possible if and only if @math . In other words, @math is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph @math , defining the degree rate as @math , where @math is the minimum degree of the graph, it is shown that the proposed method achieves the rate @math , where @math is the spectral gap of the graph @math .