Modularity from fluctuations in random graphs and complex networks

The mechanisms by which modularity emerges in complex networks are not well understood but recent reports have suggested that modularity may arise from evolutionary selection. We show that finding the modularity of a network is analogous to finding the ground-state energy of a spin system. Moreover, we demonstrate that, due to fluctuations, stochastic network models give rise to modular networks. Specifically, we show both numerically and analytically that random graphs and scale-free networks have modularity. We argue that this fact must be taken into consideration to define statistically significant modularity in complex networks.

Figure 1

Modularity in Erdös-Rényi random graphs. (a) Comparison of numerical results of the modularity as a function of the linking probability, and the predictions of Eqs. (16, 19). The numerical results are obtained by maximizing the modularity, Eq. (1), using simulated annealing [19]. (b) Modularity as a function of $pS$ for large networks, as predicted by Eq. (16). Both in (a) and (b), numerical problems in the solution of Eq. (9) prevent us from obtaining values of the modularity for larger values of $p$.

Figure 2

Modularity in scale-free networks. Numerical results of the modularity as a function of the network size $S$ for different values of $m$. These results are obtained by maximizing the modularity, Eq. (1), with simulated annealing. The lines are the predictions of Eq. (21), with $a=0.165\pm 0.009$ in all the cases.