Author's Department/Program
Physics
Language
English (en)
Date of Award
5-24-2010
Degree Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Chair and Committee
Zohar Nussinov
Abstract
We present an exceptionally accurate spin-glass-type Potts model for the graph theoretic problem of community detection. With a simple algorithm, we find that our approach is exceptionally accurate, robust to the effects of noise, and competitive with the best currently available algorithms in terms of speed and the size of solvable systems. Being a "local" measure of community structure, our Potts model is free from a "resolution limit" that hinders community solutions for some popular community detection models. It further remains a local measure on weighted and directed graphs. We apply our community detection method to accurately and quantitatively evaluate the multi-scale: "multiresolution") structure of a graph. Our multiresolution algorithm calculates correlations among multiple copies: "replicas") of the same graph over a range of resolutions. Significant multiresolution structures are identified by strongly correlated replicas. The average normalized mutual information and variation of information give a quantitative estimate of the "best" resolutions and indicate the relative strength of the structures in the graph. We further investigate a "phase transition" effect in community detection, and we elaborate on its relation to analogous physical phase transitions. Finally, we apply our community detection methods to ascertain the most "natural" complex amorphous structures in two model glasses in an unbiased manner. We construct a model graph for the physical systems using the potential energy to generate weighted edge relationships for all pairs of atoms. We then solve for the communities within the model network and associate the best communities with the natural structures in the physical systems.
Recommended Citation
Ronhovde, Peter, "Physical Models in Community Detection with Applications to Identifying Structure in Complex Amorphous Systems" (2010). All Theses and Dissertations (ETDs). 852.
https://openscholarship.wustl.edu/etd/852
Comments
Permanent URL: http://dx.doi.org/10.7936/K7GQ6VVN