Correlations in Random Graphs and Mean-Field Spin Glasses

Abstract

Random graph models, e.g. the Erdös-Rényi model, are central objects in computer science. Ran- dom graph theory sheds light on the typical behavior of graphs such as connectivity, degree distri- bution, and expansion. On the other hand, by considering random graphs as networks that describe social, biological, and technical structures [DT19], combinatorial problems on random graphs have applications in machine learning, network de-anonymization, and computational biology. To obtain a more realistic model for some real-world scenarios, sometimes it is beneficial to consider correlated samples from the random graph model, where correlation can be thought of as a soft representation of the underlying structure. For example, contacts of users in two social networks are expected to be related. In this thesis, we consider the graph matching problem on correlated random graphs. In the first part of the thesis, we give an efficient algorithm that recovers a matching between two correlated random graphs without using any ”seed”. We then provide an application of random graph matching to a problem in computational biology. In particular, we propose an algorithm that recovers cell structures, where graphs are nearest neighbor graphs based on gene expression distance from single-cell RNA-seq dataset, without using prior information. For both problems, the algorithm found ways to capture structure from underlying correlation instead of requiring prior information on the underlying structure. Connections between spin glasses and random graphs have been investigated in recent years [MM09, Sen17, MM11]. In the second part of the thesis, we study a generalization of the SK model, the mean-field Ghatak-Sherrington Model. We establish the limiting distribution of the (self) overlap array and the free energy at sufficiently high temperature, by investigating the structure that arises from the correlation between coordinates of the spin configuration.