Random field Ising model and community structure in complex networks

Abstract

We propose a method to find out the community structure of a complex network. In this method the ground state problem of a ferromagnetic random field Ising model is considered on the network with the magnetic field $B_s=+\infty$, $B_t=-\infty$, and $B_{i\ne s,t}=0$ for a node pair $s$ and $t$. The ground state problem is equivalent to the so-called maximum flow problem, which can be solved exactly numerically with the help of a combinatorial optimization algorithm. The community structure is then identified from the ground state Ising spin domains for all pairs of $s$ and $t$. Our method provides a criterion for the existence of the community structure, and is applicable to unweighted and weighted networks equally well. We demonstrate the performance of the method by applying it to the Barabási-Albert network, Zachary karate club network, the scientific collaboration network, and the stock price correlation network.

7 pages, 4 figures

References in corpus (22)

• Emergence of scaling in random networks
• Statistical mechanics of complex networks
• The structure and function of complex networks
• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Finding community structure in very large networks
• Fast algorithm for detecting community structure in networks
• Hierarchical organization of modularity in metabolic networks
• The large-scale organization of metabolic networks
• Evolution of networks
• Defining and identifying communities in networks
• Hierarchical Structure in Financial Markets
• Dynamics of market correlations: Taxonomy and portfolio analysis
• Detecting fuzzy community structures in complex networks with a Potts model
• Finding Communities in Linear Time: A Physics Approach
• Subnetwork hierarchies of biochemical pathways
• A Method to Find Community Structures Based on Information Centrality
• Distance, dissimilarity index, and network community structure
• The three-dimensional random field Ising magnet: interfaces, scaling, and the nature of states
• Systematic analysis of group identification in stock markets
• A model for correlations in stock markets
• Disorder Driven Critical Behavior of Periodic Elastic Media in a Crystal Potential

Cited by in corpus (14)

• Community detection in graphs
• Robust network community detection using balanced propagation
• Community Detection Using A Neighborhood Strength Driven Label Propagation Algorithm
• Majority Model on a network with communities
• Coexistence of opposite opinions in a network with communities
• Accuracy and Precision of Methods for Community Identification in Weighted Networks
• Ubiquitousness of link-density and link-pattern communities in real-world networks
• Process Flow Diagram of an Ammonia Plant as a Complex Network
• Broad lifetime distributions for ordering dynamics in complex networks
• Community detection by label propagation with compression of flow
• Random field Ising model on networks with inhomogeneous connections
• Low-energy excitations in the three-dimensional random-field Ising model
• Rewiring driven evolution of quenched frustrated signed network
• Partitioning networks into clusters of synchronized nodes via the message-passing algorithm: an unbiased scalable approach