Lattice models of glasses and Potts models for community detection

In Part I, we construct a configurationally constrained lattice glass model following the example of Biroli and Mezard (Phys. Rev. Lett., 82, 025501 (2001)), which we denote t154. By examining the relaxation, atomic motion, Stokes-Einstein relationship violation, time-dependent displacement (van Hove function), wavevector-dependent relaxation, and multi-point correlations S4 and chi4, we can show that this new model satisfies all minimal requirements set by the observed phenomena of dynamical heterogeneity of supercooled liquids, though with a drastically different theoretical basis from existing lattice models of glasses based on kinetic facilitation. We then proceed to perform a more detailed comparison between lattice glass models, including t154 and a model by Ciamarra et. al. (Phys. Rev. E 68 066111 (2003)), with traditional facilitated models. We study two forms of dynamical sensitivity: sensitivity to boundary conditions, and a sensitivity to initial conditions. By comparison to atomistic computer simulation, we find evidence that the lattice glass models better describe glassy behavior. We conclude by discussing the implications of our findings for contrasting theories of the glass transition. In Part II, we change our focus and examine community detection in graphs from a theoretical standpoint. Many disparate community definitions have been proposed, however except for one, few have been analyzed in any great detail. In this work, we, for the first time, formally study a definition based on internal edge density. Using the concept that internal edge density is the fraction of intra-community edges relative to the maximal number of intra-community edges, we produce a rich framework to use as the basis of community detection. We discuss its use in local and global community detection algorithms, and how our methods can extend to overlapping and hierarchical communities, and weighted, directed, and multi-graphs. In order to validate our definition, we use the recently proposed affiliation graph model and both theoretically and computationally demonstrate the suitability of edge density to solve this problem. We see that internal edge density can perform successful detection on this benchmark under a variety of conditions. We then discuss the limitations of edge density, the types of community structure it will and will not be able to successfully detect, and emphasize the importance of detailed study of real-world community structure in order to produce evidence-based community detection algorithms.