Author's School

Graduate School of Arts & Sciences

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.

DOI

https://doi.org/10.7936/K7GQ6VVN

Comments

Permanent URL: http://dx.doi.org/10.7936/K7GQ6VVN

Share

COinS