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.

arXiv comment14 pages, 4 figures

References in corpus (27)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Modularity and community structure in networks
• Fast algorithm for detecting community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Functional cartography of complex metabolic networks
• Classes of behavior of small-world networks
• Comparing community structure identification
• Defining and identifying communities in networks
• Statistical Mechanics of Community Detection
• Universal Behavior of Load Distribution in Scale-free Networks
• Modularity from Fluctuations in Random Graphs and Complex Networks
• Detecting fuzzy community structures in complex networks with a Potts model
• Finding Communities in Linear Time: A Physics Approach
• Detecting Network Communities: a new systematic and efficient algorithm
• Subnetwork hierarchies of biochemical pathways
• Curvature of Co-Links Uncovers Hidden Thematic Layers in the World Wide Web
• A Method to Find Community Structures Based on Information Centrality
• Modularity and Extreme Edges of the Internet
• Community analysis in social networks
• Identifying "communities" within energy landscapes
• Partitioning and modularity of graphs with arbitrary degree distribution
• Evolution of scale-free random graphs: Potts model formulation
• Spin Glass Phase Transition on Scale-Free Networks
• Intrinsic degree-correlations in static model of scale-free networks