Ground state energy of $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 \emph{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 [Phys. Rev. E \textbf{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 $⟨\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.

14 pages, 4 figures

References in corpus (8)

• Modularity and community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Comparing community structure identification
• Statistical Mechanics of Community Detection
• Subnetwork hierarchies of biochemical pathways
• Identifying "communities" within energy landscapes
• Partitioning and modularity of graphs with arbitrary degree distribution
• Evolution of scale-free random graphs: Potts model formulation