Generic criticality of community structure in random graphs

We examine a community structure in random graphs of size $n$ and link probability $p/n$ determined with the Newman greedy optimization of modularity. Calculations show that for $p<1$ communities are nearly identical with clusters. For $p=1$ the average sizes of a community $s_{\mathrm{av}}$ and of the giant community $s_g$ show a power-law increase $s_{\mathrm{av}}\sim n^{{\alpha }^{\prime }}$ and $s_g\sim n^{\alpha }$. From numerical results we estimate ${\alpha }^{\prime }\approx 0.26\left(1\right)$ and $\alpha \approx 0.50\left(1\right)$ and using the probability distribution of sizes of communities we suggest that ${\alpha }^{\prime }=\alpha /2$ should hold. For $p>1$ the community structure remains critical: (i) $s_{\mathrm{av}}$ and $s_g$ have a power-law increase with ${\alpha }^{\prime }\approx \alpha <1$ and (ii) the probability distribution of sizes of communities is very broad and nearly flat for all sizes up to $s_g$. For large $p$ the modularity $Q$ decays as $Q\sim p^{-0.55}$, which is intermediate between some previous estimations. To check the validity of the results, we also determine the community structure using another method, namely, a nongreedy optimization of modularity. Tests with some benchmark networks show that the method outperforms the greedy version. For random graphs, however, the characteristics of the community structure determined using both greedy and nongreedy optimizations are, within small statistical fluctuations, the same.

Figure 1

Two clusters (separate subgraphs) and three communities (in circles). Clusters might include one or more communities and different clusters incorporate different communities.

Figure 2

Rescaled size of the giant community $s_g/n$ as a function of the link probability $p$ calculated for several sizes of a graph $n$. For each $p$ and $n$ we average over ${10}^3\text{–}{10}^5$ graphs.

Figure 3

The $n$ dependence of the size of the giant community (on a log-log scale). For $p\ge 1$, the size of the giant community shows a power-law increase $s_g\sim n^{\alpha }$ and from the fit to numerical data we obtain $\alpha (p=1)=0.51\left(1\right),\alpha (p=3)=0.85\left(1\right),\alpha (p=5)=0.90\left(1\right)$, and $\alpha (p=10)=0.95\left(1\right)$. The numerical data show a nearly linear increase for more than four decades of $n$.

Figure 4

Inverse of the average community size $s_{\mathrm{av}}$ as a function of $p$. For random graphs the average cluster size equals $1/(1-p)$ [14] and our numerical data in the limit $n\to \infty$ are in a very good agreement with this formula. This means that for $p<1$ communities basically coincide with clusters.

Figure 5

The $n$ dependence of the average size of a community $s_{\mathrm{av}}$ (on a log-log scale). For $p\ge 1,s_{\mathrm{av}}$ shows a power-law increase $s_{\mathrm{av}}\sim n^{{\alpha }^{\prime }}$ and from the fit to numerical data we obtain ${\alpha }^{\prime }(p=1)=0.26\left(1\right),{\alpha }^{\prime }(p=3)=0.87\left(1\right)$, and ${\alpha }^{\prime }(p=5)=0.91\left(1\right)$.

Figure 6

Distributions of size of clusters $P_{\mathrm{cl}}\left(s\right)$ and communities $P_{\mathrm{co}}\left(s\right)$ calculated for $p=1$ and $0.7$ and for $n={10}^5$ (on a log-log scale). For $p=1$ both $P_{\mathrm{cl}}\left(s\right)$ and $P_{\mathrm{co}}\left(s\right)$ seem to have the expected power-law decay $s^{-3/2}$ (thick black straight line) [14].

Figure 7

Distributions of the size of clusters $P_{\mathrm{cl}}\left(s\right)$ and communities $P_{\mathrm{co}}\left(s\right)$ calculated for $p=3$. The disconnected vertical parts of the $P_{\mathrm{cl}}\left(s\right)$ on the right side correspond to spanning clusters.

Figure 8

Distribution $P_{\mathrm{co}}\left(s\right)$ rescaled with the characteristic giant community size $n^{0.85}$ calculated for $p=3$ and several values of $n$.

Figure 9

Modularity $Q$ as a function of $p$. The inset presents the data for a larger range of $p$ and suggests that for large $p$ the modularity decays as $p^{-0.55}$.

Figure 10

Zachary's karate club network. The average number of runs $\tau$ that are needed to find the community structure with the largest modularity $Q=0.41979$ is shown as a function of $\varepsilon$.

Figure 11

Fraction of correctly identified nodes as a function of $z_{\mathrm{out}}$ for the network having 1024 links and 128 nodes forming four groups, obtained using the greedy and nongreedy optimization. Each result is an average over 100 graphs and the nongreedy optimization was executed ${10}^3$ times for each graph. The inset shows the behavior of the modularity $Q$ as a function of $z_{\mathrm{out}}$.

Figure 12

Modularity $Q$ as a function of $\varepsilon$ for the 128-node network with 1024 links. Circles indicate the values obtained by the greedy version $\left(\varepsilon =0\right)$.

Figure 13

Modularity $Q$ as a function of $\varepsilon$ for $n=1000$ random graph. Each result is an average over 100 graphs and nongreedy optimization was executed ${10}^3$ times for each graph. Circles indicate the values obtained by the greedy version $\left(\varepsilon =0\right)$.

Figure 14

Average size of the giant community as a function of $\varepsilon$ for $n=1000$ random graphs. Each result is an average over 100 graphs and the nongreedy optimization was executed ${10}^3$ times for each graph. Circles indicate the values obtained by the greedy version $\left(\varepsilon =0\right)$.