title: Ground-state energy of the q-state Potts model: The minimum modularity.
abstract: 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)PLEEE81539-375510.1103/PhysRevE.76.015102]; 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(≥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 〈sqrt[k]〉/〈k〉 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 〈k〉^{-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.
authors.affiliation: School of Physics, Korea Institute for Advanced Study, Seoul 130-722, Republic of Korea.
authors.forename: J S
authors.initials: JS
authors.lastname: Lee
authors.affiliation: Institute for Theoretical Physics, University of Cologne, 50937 Köln, Germany and Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea.
authors.forename: S
authors.initials: S
authors.lastname: Hwang
authors.affiliation: School of Physics, Konkuk University, Seoul 143-701, Korea.
authors.forename: J
authors.initials: J
authors.lastname: Yeo
authors.affiliation: School of Physics, Korea Institute for Advanced Study, Seoul 130-722, Republic of Korea.
authors.forename: D
authors.initials: D
authors.lastname: Kim
authors.affiliation: Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea.
authors.forename: B
authors.initials: B
authors.lastname: Kahng