Random Graphs: Dynamic and Multi-type Extensions

Sammanfattning: Random graphs is a well-studied field of probability theory, and have proven very useful in a range of applications. However, most random graphs are \textit{static} in the sense that the network structure does not change over time; they also tend to consist of \textit{single-type} objects. This puts restrictions on possible applications. In this thesis we extend two standard models to a \textit{dynamic} and \textit{multi-type} setting, respectively.In the first paper we study a dynamic version of the famous Erd\H{o}s-Rényi graph. The graph changes dynamically over time, but still has the static Erd\H{o}s-Rényi graph as its stationary distribution. In studying the dynamic graph we present two results. The first one concerns the time to stationarity, and the second one the time to reach a certain number of edges.In the second paper we introduce and study an extension of the preferential attachment model. The standard preferential attachment model is already dynamic, but its vertices are only allowed to be of one type. We introduce a multi-type analogue of the preferential attachment model and study its asymptotic degree distributions as well as its asymptotic composition.