Structure and Function of Complex Modular Networks
Date Issued
2006-11-20
Author(s)
Supervisors
Referees
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.
Subjects
graph clustering
;
cluster quality function
Institution
Type
Dissertation
Secondary publication
No
Language
English
File(s)![Thumbnail Image]()
Loading...
Name
00010797.pdf
Size
8.4 MB
Format
Adobe PDF
Checksum
(MD5):227411f65dc04a116bccde222af669e2