Statistical Mechanics of Community Detection

Abstract

Starting from a general \textit{ansatz}, we show how community detection can be interpreted as finding the ground state of an infinite range spin glass. Our approach applies to weighted and directed networks alike. It contains the \textit{at hoc} introduced quality function from \cite{ReichardtPRL} and the modularity $Q$ as defined by Newman and Girvan \cite{Girvan03} as special cases. The community structure of the network is interpreted as the spin configuration that minimizes the energy of the spin glass with the spin states being the community indices. We elucidate the properties of the ground state configuration to give a concise definition of communities as cohesive subgroups in networks that is adaptive to the specific class of network under study. Further we show, how hierarchies and overlap in the community structure can be detected. Computationally effective local update rules for optimization procedures to find the ground state are given. We show how the \textit{ansatz} may be used to discover the community around a given node without detecting all communities in the full network and we give benchmarks for the performance of this extension. Finally, we give expectation values for the modularity of random graphs, which can be used in the assessment of statistical significance of community structure.

References in corpus (2)

• Uncovering the overlapping community structure of complex networks in nature and society
• Eprints and the Open Archives Initiative

Cited by in corpus (31)

• Finding community structure in networks using the eigenvectors of matrices
• Critical phenomena in complex networks
• Community structure in directed networks
• An information-theoretic framework for resolving community structure in complex networks
• Modularity and community detection in bipartite networks
• Line Graphs, Link Partitions and Overlapping Communities
• Community detection in networks with positive and negative links
• Analysis of the structure of complex networks at different resolution levels
• Detecting network communities by propagating labels under constraints
• Robustness of community structure in networks
• A Bayesian Approach to Network Modularity
• Analysis of community structure in networks of correlated data
• Modularity clustering is force-directed layout
• Community Detection as an Inference Problem
• Evaluating Local Community Methods in Networks
• Limited resolution in complex network community detection with Potts model approach
• Maximizing Modularity is hard
• Role models for complex networks
• When are networks truly modular?
• Spectral tripartitioning of networks
• Partitioning and modularity of graphs with arbitrary degree distribution
• Note on the equivalence of the label propagation method of community detection and a Potts model approach
• Accuracy and Precision of Methods for Community Identification in Weighted Networks
• Deterministic Modularity Optimization
• Inversion method for content-based networks
• Detecting modules in dense weighted networks with the Potts method
• A Graph Analysis of the Linked Data Cloud
• Spectral methods and cluster structure in correlation-based networks
• Quality functions in community detection
• Multi-level algorithms for modularity clustering
• Small-world of communities: communication and correlation of the meta-network