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.
@cite_22: We study networks that display community structure -- groups of nodes within which connections are unusually dense. Using methods from random matrix theory, we calculate the spectra of such networks in the limit of large size, and hence demonstrate the presence of a phase transition in matrix methods for community detection, such as the popular modularity maximization method. The transition separates a regime in which such methods successfully detect the community structure from one in which the structure is present but is not detected. By comparing these results with recent analyses of maximum-likelihood methods we are able to show that spectral modularity maximization is an optimal detection method in the sense that no other method will succeed in the regime where the modularity method fails.
@cite_33: Recent research has shown that virtually all algorithms aimed at the identification of communities in networks are affected by the same main limitation: the impossibility to detect communities, even when these are well defined, if the average value of the difference between internal and external node degrees does not exceed a strictly positive value, in the literature known as detectability threshold. Here, we counterintuitively show that the value of this threshold is inversely proportional to the intrinsic quality of communities: the detection of well-defined modules is thus more difficult than the identification of ill-defined communities.
@cite_8: 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.
@cite_21: We study the problem of detecting or discovering a planted clique embedded in a random graph. Using recent results from random matrix theory, we demonstrate the presence of a phase transition in eigen-analysis based methods for planted clique detection. The transition separates a regime in which eigen-analysis based methods will successfully detect the planted clique and the associated vertices from one in which the planted clique is present but is undetectable. We validate the prediction with numerical simulations.
@cite_3: Communities are fundamental entities for the characterization of the structure of real networks. The standard approachtotheidentificationofcommunitiesinnetworksisbasedontheoptimizationofaqualityfunctionknown as modularity. Although modularity has been at the center of an intense research activity and many methods for its maximization have been proposed, not much is yet known about the necessary conditions that communities need to satisfy in order to be detectable with modularity maximization methods. Here, we develop a simple theory to establish these conditions, and we successfully apply it to various classes of network models. Our main result is that heterogeneity in the degree distribution helps modularity to correctly recover the community structure of a network and that, in the realistic case of scale-free networks with degree exponent γ< 2.5, modularity is always able to detect the presence of communities.
@cite_23: Real-world networks are rarely isolated. A model of an interdependent network of networks shows that an abrupt phase transition occurs when interconnections between independent networks are added. This study also suggests ways to minimize the danger of abrupt structural changes to real networks.
@cite_10: We prove the existence of an asymptotic phase transition threshold on community detectability for the spectral modularity method [M. E. J. Newman, Phys. Rev. E 74, 036104 (2006) and Proc. National Academy of Sciences. 103, 8577 (2006)] under a stochastic block model. The phase transition on community detectability occurs as the inter-community edge connection probability @math grows. This phase transition separates a sub-critical regime of small @math , where modularity-based community detection successfully identifies the communities, from a super-critical regime of large @math where successful community detection is impossible. We show that, as the community sizes become large, the asymptotic phase transition threshold @math is equal to @math , where @math is the within-community edge connection probability. Thus the phase transition threshold is universal in the sense that it does not depend on the ratio of community sizes. The universal phase transition phenomenon is validated by simulations for moderately sized communities. Using the derived expression for the phase transition threshold we propose an empirical method for estimating this threshold from real-world data.
@cite_25: We present an asymptotically exact analysis of the problem of detecting communities in sparse random networks generated by stochastic block models. Using the cavity method of statistical physics and its relationship to belief propagation, we unveil a phase transition from a regime where we can infer the correct group assignments of the nodes to one where these groups are undetectable. Our approach yields an optimal inference algorithm for detecting modules, including both assortative and disassortative functional modules, assessing their significance, and learning the parameters of the underlying block model. Our algorithm is scalable and applicable to real-world networks, as long as they are well described by the block model.
@cite_12: Spectral algorithms are classic approaches to clustering and community detection in networks. However, for sparse networks the standard versions of these algorithms are suboptimal, in some cases completely failing to detect communities even when other algorithms such as belief propagation can do so. Here, we present a class of spectral algorithms based on a nonbacktracking walk on the directed edges of the graph. The spectrum of this operator is much better-behaved than that of the adjacency matrix or other commonly used matrices, maintaining a strong separation between the bulk eigenvalues and the eigenvalues relevant to community structure even in the sparse case. We show that our algorithm is optimal for graphs generated by the stochastic block model, detecting communities all of the way down to the theoretical limit. We also show the spectrum of the nonbacktracking operator for some real-world networks, illustrating its advantages over traditional spectral clustering.
Community detectability has been studied under the stochastic block model with restricted assumptions such as @math , @math and fixed average degree as the network size @math increases @cite_25 @cite_22 @cite_12 @cite_3 @cite_33 . The planted clique detection problem in @cite_21 is a special case of the stochastic block model when @math and @math . A less restricted stochastic block model is studied in @cite_10 where a universal phase transition in community detectability is established for which the critical value does not depend on the community sizes. A similar model to our network model is studied in @cite_23 for interconnected networks. However, in @cite_23 the subnetworks are of equal size and the external edges are known (i.e., non-random). Phase transitions in spectral community detection under noiseless network setting is studied in @cite_8 .