Ground-state energy of the $q$-state Potts model: The minimum modularity

A wide range of interacting systems can be described by complex networks. A common feature of such networks is that they consist of several communities or modules, the degree of which may quantified as the modularity. However, even a random uncorrelated network, which has no obvious modular structure, has a finite modularity due to the quenched disorder. For this reason, the modularity of a given network is meaningful only when it is compared with that of a randomized network with the same degree distribution. In this context, it is important to calculate the modularity of a random uncorrelated network with an arbitrary degree distribution. The modularity of a random network has been calculated [Reichardt and Bornholdt, Phys. Rev. E 76, 015102 (2007)]; however, this was limited to the case whereby the network was assumed to have only two communities, and it is evident that the modularity should be calculated in general with $q(\ge 2)$ communities. Here we calculate the modularity for $q$ communities by evaluating the ground-state energy of the $q$-state Potts Hamiltonian, based on replica symmetric solutions assuming that the mean degree is large. We found that the modularity is proportional to $\langle \sqrt{k}\rangle /\langle k\rangle$ regardless of $q$ and that only the coefficient depends on $q$. In particular, when the degree distribution follows a power law, the modularity is proportional to ${\langle k\rangle }^{-1/2}$. Our analytical results are confirmed by comparison with numerical simulations. Therefore, our results can be used as reference values for real-world networks.

Figure 1

Examples of a random uncorrelated and a modular network. Each color represents a different community, as identified by the $q$-state Potts model. (a) A static model with a modularity of 0.51. (b) A modular network with a modularity of 0.72.

Figure 2

Potts spin vector. $q$-state Potts spin can be mapped into vertices of a $r(=q-1)$-dimensional simplex.

Figure 3

$C_0\left(q\right)$ as defined in Eq. (44) for various $q$.

Figure 4

Plot of ${\left[Q_{\text{MOD},\eta }^{*}\right]}_c$ against $\eta$ for $q=3$, $N=10000$, $\langle k\rangle =64$, and $\gamma =3.5$. The red open circles represent the data calculated using the simulated annealing method. The cross symbols indicate the solutions of Eq. (39) obtained by solving the self-consistent equations (36), (D2), (D7), and (D9) numerically. For small $\eta$, $D$ is expected to be small, and thus ${\left[Q_{\text{MOD},\eta }^{*}\right]}_c$ is very close to $1-\eta$ (the blue dashed curve), which can be seen in Eq. (39).

Figure 5

(a) Plot of ${\left[Q_{\mathrm{MOD}}^{*}\right]}_c$ rescaled by $\mathcal{G}\left(\gamma \right)$ as a function of $\langle k\rangle$ for $\gamma =3$, 3.5, 4, 4.5, and ER ($\gamma \to \infty$), with $\eta =1.0$ and $q=3$. The red dashed curve shows the result of Eq. (49). The gradient of the curve in the double logarithmic scale is $-0.5$. (b) Plot of ${\left[Q_{\mathrm{MOD}}^{*}\right]}_c$ rescaled by $C\left(q\right)$ as a function of $\langle k\rangle$ for eight values of $q$ up to $q=9$ with $\eta =1.0$ and $\gamma =3.5$. The red dashed curve shows the theoretical curve from Eq. (49).