Paper detail

Randomised reproducing graphs

We introduce a model for a growing random graph based on simultaneous reproduction of the vertices. The model can be thought of as a generalisation of the reproducing graphs of Southwell and Cannings and Bonato et al to allow for a random element, and there are three parameters, $α$, $β$ and $γ$, which are the probabilities of edges appearing between different types of vertices. We show that as the probabilities associated with the model vary there are a number of phase transitions, in particular concerning the degree sequence. If $(1+α)(1+γ)<1$ then the degree distribution converges to a stationary distribution, which in most cases has an approximately power law tail with an index which depends on $α$ and $γ$. If $(1+α)(1+γ)>1$ then the degree of a typical vertex grows to infinity, and the proportion of vertices having any fixed degree $d$ tends to zero. We also give some results on the number of edges and on the spectral gap.