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.
Our model is more general than the stochastic block model since it does not assume any edge connection models within the communities. The details are discussed in Sec. . A similar model is studied in @cite_26 for interconnected networks. However, in @cite_26 the subnetworks are of equal size and the external edges are known (i.e., non-random). The main contribution of @cite_26 was a study of the eigenstructure of the overall graph Laplacian matrix with different interconnected edge strengths as contrasted to community detection. The simulation results in @cite_4 show that phase transition on community detectability exists under this general model, yet the critical phase transition threshold is still poorly understood. Phase transition results on p-resistance distances of random geometric graphs are obtained in @cite_2 . The authors of @cite_2 show that there exist two critical thresholds for the p-resistance. The first (lower) threshold depends on the global graph topology while the second (higher) threshold only depends on local graph connectivity.
@cite_26 @cite_4 @cite_2
2024224210 2078528040
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. 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.