Till innehåll på sidan
Till KTH:s startsida Till KTH:s startsida

Sebastian Rosengren: Random graph and growth models

Tid: Fr 2020-09-25 kl 13.00

Plats: Kräftriket, house 5, room 15

Respondent: Sebastian Rosengren , Stockholms universitet

Opponent: Tatyana Turova, Lund University

Exportera till kalender

Attendence Notes: The number of people who can be present in the room is limited. Those who wish to be present therefore need to register by sending an email to rosengren@math.su.se . For those who cannot be present in the room, the defence will be broadcasted via Zoom. A link will be published here a few days before the defence.


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 extension 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 grow in a deterministic way. 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 Z^d 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.