Jonathan JordanElectronic Journal of Probability, Vol. 16, pp1549-1562 (2011) Abstract: 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. Link to paper on the EJP website.
Post-publication note. It has been pointed out to me that Theorem 2.1 of reference [7], used in the proof of Lemma 7, has been shown to be incorrect by Koluszka and Ololewski (2004). In the proof of Lemma 7 in the p<0 case, this result should be replaced by Theorem 1 of Shi, Wu and Liu (2010), which covers the case needed for Lemma 7. |