Physical Models in Community Detection with Applications to Identifying Structure in Complex Amorphous Systems

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.

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Physics

Year dc:date.available

2010

Author dc:creator

• Ronhovde, Peter

Contributors dc:contributor

• Zohar Nussinov

• Theoretical Physics
• Mathematics
• clustering
• community detection
• complex networks
• graph theory
• multiresolution
• Potts model

Language dc:language

English (en)

DOI

https://doi.org/10.7936/K7GQ6VVN

OAI identifier oai:identifier

oai:openscholarship.wustl.edu:etd-1851