Graph Spectra and the Detectability of Community Structure in Networks

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.

Figure 1

(a) The solid curves represent the right-hand side of Eq. (10) while the dashed horizontal line represents the left-hand side. The points at which the two cross, indicated by the dots, are the solutions $z_i$ of the equation, which necessarily fall between the eigenvalues ${\lambda }_i$ of the matrix $\mathbf{X}$ (vertical dashed lines). (b) The spectrum of the modularity matrix is the same of that of the random matrix $\mathbf{X}$ (semicircle), except for the highest eigenvalue $z_1$, which is separate from the rest of the spectrum above the transition point given in Eq. (14).

Figure 2

The fraction of vertices correctly classified by the spectral modularity algorithm in networks generated using the block model studied here, as a function of $c_{\mathrm{in}}-c_{\mathrm{out}}$, for four different values of the average degree as indicated. Points are numerical measurements for networks of 100 000 vertices, averaged over 25 networks each; solid curves represent the analytic prediction. The phase transition at which the algorithm fails is clearly visible in each curve.