Random Graph and Growth Models

Random graphs is a well-studied field of probability theory, and have proven very useful in a range of applications — modeling social networks, epidemics, and structures on the Internet to name a few. However, most random graphs are static in the sense that the network structure does not change over time. Furthermore, standard models also tend to consist of single-type objects. This puts restrictions on possible applications. The first part of this thesis concerns random graphs with a focus on dynamic and multi-type extensions of standard models. The second part of the thesis deals with random growth models. Random growth models are important objects in probability theory and, as the name suggests, models the random growth of some entity. Typical examples include infectious disease spread; how a liquid flows through a random medium; and tumor growth. The growth of these models, properly scaled by time, tends to be deterministic. The second theme of the thesis concerns the final shape of the growing entity for two standard random growth models. In Paper I, we study a dynamic version of the famous Erdős-Rényi graph. The graph changes dynamically over time but still has the static Erdős-Rényi graph as its stationary distribution. In studying the dynamic graph we present two results. The first result concerns the time to stationarity, and the second concerns the time it takes for the graph to reach a certain number of edges. We also study the time until a large component emerges, as well as how it emerges. In Paper II, we introduce and study an extension of the preferential attachment tree. The standard version is already dynamic, but its vertices are only allowed to be of one type. We introduce a multi-type analog of the preferential attachment tree and study its asymptotic degree distributions as well as its asymptotic composition. Paper III concerns the configuration model — a random graph neither dynamic nor multi-type — and we break with the first theme of the thesis since no extensions are made to the model. Instead, we argue that the size of the largest component in the model does not depend on the tail of the degree distribution, but rather on the distribution over small degrees. This is quantified in some detail. In Paper IV, we consider the frog model on Zd and a two-type extension of it. For the one-type model, we show that the asymptotic shape does not depend on the initial set and the particle configuration there. For the two-type model, we show that the possibility of both types to coexist also does not depend on the initial sets and the particle configurations there. Paper V is concerned with the predictability of the set of discovered sites generated by the first passage percolation model. First passage percolation has the property that the set of discovered sites, scaled properly by time, converges to some deterministic set as time grows. Typically, not much is known about this set, and to get an impression of it simulations are needed. Using simulated data we show that it is possible to use a neural network to adequately predict the shape, on this dataset, from some easily calculable properties of the passage times. The purpose of the paper is to give researchers a proof of concept of this method as wells as a new tool for quickly getting an impression of the shape.At the time of the doctoral defense paper 3 had the following status: manuscript