Randomised reproducing graphs (2011)
Electronic Journal of Probability, vol. 16, pp. 1549-1562.
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.
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.
M. Kaluszka and A. Okolewski (2004), On Fatou-type lemma for monotone moments of weakly convergent random variables, Statistics and Probability Letters 66:45–50
X. Shi, Y.Wu and Y. Liu (2010), A note on asymptotic approximations of inverse moments of nonnegative random variables, Statistics and Probability Letters 80:1260-1264