Structure and Function of Complex Modular Networks

Abstract

A method for community detection (graph clustering) is developed by mapping the problem onto finding the ground state of an infinite range spin glass. A precise definition of community as maximally cohesive subgraph is derived from the properties of the ground state. Overlapping and hierarchical cluster structures are detected via changes of a single parameter. The ground state of the infinite range spin glass can be found by using computationally efficient methods operating on the sparse links of the network, only. As a test for statistical significance, expectation values of ground state energies (cluster quality function) are derived for networks of arbitrary degree distributions using the replica and cavity method and compared to numerical experiments. The results improve estimates for the cut size of the graph partitioning problem.Two applications are presented: the analysis of an energy landscape of the folding Hamiltonian of a short peptide and a market segmentation study of a large online market (eBay). Both applications show that the suggested network clustering methodology gives high quality results, which could not be obtained otherwise.