Abstract
Random graph models have become extremely popular due to their relevance as models of complex networks. While the famous Erdös-Rényi model and the configuration model have been around for decades helping us gain enormous insight of the relevance of network structure for complex phenomena, these two models lack a fundamental element of real networks, the presence of short loops. Amazingly, there is no easy extension of traditional models to produce random loopy graphs that mimic real loopy networks. Only in the past decade have manageable loopy random graphs been properly developed. In this thesis we will present maximum entropy loopy models with a tuneable amount of short loops. Amazingly, even the simplest cases will present a rich phenomenology with nontrivial transitions. For the spectral calculations of these ensembles we introduce an extension of the traditional replica method that require certain replica limits where dimensions take imaginary values, contrary to the traditional n → 0 case.In the first part of the thesis we present a maximum entropy ensemble of random loopy graphs with a fixed degree sequence and a tuneable number of short loops. For the particular case of 2-regular graphs we present an exact solution of the model. It shows the range of tuneability of all loops of different lengths up to any nite value K. A transition from a connected to a disconnected phase is characterized, showing the nontrivial necessary scaling of the parameters with the system size. We extend the case of a triangle bias to a model with an arbitrary degree distribution. Through a simple yet powerful approximation of the generating function of the model we find a general theory applying to all degree distributions with well defined first and second moments. This ensemble undergoes a transition from a weak clustering regime where triangles do not interact, in the sense that they do not share edges, into a regime where triangles begin to cluster. We refer to this transition as the clustering transition. Eventually, triangles "break off" in the form of isolated cliques to maximize the triangle density. We refer to this last transition as the shattering transition. We present accurate analytical estimates for the triangle density in the weak clustering regime. For the case of bounded degree distributions the scaling of the shattering transition with system size is also presented. We present the counter-intuitive result that every loop density will eventually fall in the shattered regime, no matter how small, if the graph is large enough. Overall we provide a complete picture of the behaviour of this ensemble validated by MCMC numerical sampling methods.
In the second part of the thesis we present the spectrally constrained maximum entropy ensemble. In this case we aim to bias the eigenvalue density at each point of the spectrum. For this we introduce a functional Lagrange parameter [symbol](μ) that biases the spectral density at point μ. We develop an analytic theory based on the method of imaginary replicas in order to calculate the generating function of this model. Following insight from the first part, we develop the theory up to subleading terms in the system size, N, of O(1=N). We present a set of distributional equations that depend on the choice of model [symbol](μ). We are able to recover the prediction for the loop density of the first part for the weak clustering regime, since the triangle bias is a particular case of this ensemble. With this theory we are also able to provide an analytic expression for the average eigenvalue density in the loopy regime. For the case of regular graphs an exact analytic solution is presented. For the case of an arbitrary degree distribution p(k) the equations must be solved with numerical methods. A good agreement is found in all cases. The functional imaginary replica theory opens the door to other nontrivial ensembles beyond the triangle bias. These are explored easily for regular graphs thanks to the exact solution.
| Date of Award | 1 Jan 2021 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Ton Coolen (Supervisor) |