Exponential random graph models for networks with community structure

Although the community structure organization is an important characteristic of real-world networks, most of the traditional network models fail to reproduce the feature. Therefore, the models are useless as benchmark graphs for testing community detection algorithms. They are also inadequate to predict various properties of real networks. With this paper we intend to fill the gap. We develop an exponential random graph approach to networks with community structure. To this end we mainly built upon the idea of blockmodels. We consider both the classical blockmodel and its degree-corrected counterpart and study many of their properties analytically. We show that in the degree-corrected blockmodel, node degrees display an interesting scaling property, which is reminiscent of what is observed in real-world fractal networks. A short description of Monte Carlo simulations of the models is also given in the hope of being useful to others working in the field.

Figure 1

A Monte Carlo realization of the classical blockmodel with $N=2048$ nodes divided into $K=8$ groups of equal size $N_r=256$. The color symbols indicate the group membership, the node size is proportional to the degree, and the edge width is proportional to the edge betweenness. To get the figure the following values of the ensemble parameters have been used: ${\forall }_r{q}_{rr}=3/255$ and ${\forall }_{r\ne s}{q}_{rs}=0.006/256$; see Eqs. (11) and (12). The network was visualized using Cytoscape software [27].

Figure 2

A Monte Carlo realization of the degree-corrected blockmodel with scale-free communities. The network consists of $N=2048$ nodes divided into $K=8$ groups of equal size. The color indicates the partition of the nodes into groups, and the size of the nodes is proportional to the degree. The edge width is proportional to the edge betweenness. To perform numerical simulations, the following values of the ensemble parameters have been used: (i) The expected internal degrees have been independently drawn from the power law distribution with the characteristic exponent $\gamma =3$; (ii) the minimal value of the expected degree was assumed to be 2; (iii) the expected numbers of interblock connections were taken to be ${\forall }_{r\ne s}\langle E_{rs}\rangle =1$. The network was visualized using Cytoscape software [27].

Figure 3

Scaling relations between the internal, $\langle k_i^{\mathrm{int}}\rangle$, and external, $\langle k_i^{\mathrm{out}}\rangle$, node degrees in scale-free networks with community structure. In the main panel, linear relations of internal (open symbols) and external (solid symbols) degrees vs. the preimposed internal degrees, $\langle k_{i,r}^r\rangle$, are shown. In the inset, linear scaling between $\langle k_i^{\mathrm{int}}\rangle$ and $\langle k_i^{\mathrm{out}}\rangle$ is displayed. The scattered points represent the simulated data averaged over 100 snapshots of scale-free networks (with $\gamma =3$) of size $N=2048$ nodes divided into $K=8$ groups of equal size. The smallest preimposed internal node degree was equal to 2, and the expected numbers of interblock connections were taken to be ${\forall }_{r\ne s}\langle E_{rs}\rangle =5$. Solid lines either represent the identity $\langle k_i^{\mathrm{int}}\rangle =\langle k_{i,r}^r\rangle$ or Eq. (48).

Figure 4

Histograms of node degrees for a single community, $N\left(k_i^{\mathrm{int}}\right)$ (open symbols), and for the whole network, $N\left(k_i\right)$ (solid symbols), where $k_i=k_i^{\mathrm{int}}+k_i^{\mathrm{ext}}$. The data were gathered during the same Monte Carlo simulations as those shown in Fig. 3. Solid lines represent power law with slope $\gamma =3$.