Randomised Reproducing Graphs

Jonathan H Jordan (University of Sheffield)


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, $\alpha$, $\beta$ and $\gamma$, 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+\alpha)(1+\gamma)<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 $\alpha$ and $\gamma$. If $(1+\alpha)(1+\gamma)>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.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1549-1562

Publication Date: August 22, 2011

DOI: 10.1214/EJP.v16-921


  1. K. E. Athreya and P. E. Ney. Branching Processes Dover Publications, Mineola, New York, 1972.
  2. A. Bonato, N. Hadi, P. Horn, P. Prałat and C. Wang. Models of on-line social networks. Internet Mathematics, 6:285-313, 2011. Math. Review MR2798106
  3. F. Chung, L. Lu, T. Dewey and D. Gales. Duplication models for biological networks. Journal of Computational Biology, 10:677-687, 2003.
  4. F. R. K. Chung. Spectral Graph Theory. Number 92 in CBMS Regional Conference Series. AMS, Providence, Rhode Island, 1997. Math. Review MR1421568.
  5. N. Cohen, J. Jordan and M. Voliotis. Preferential duplication graphs. Journal of Applied Probability, 47:582-585, 2010. Math. Review MR2668507.
  6. G. Cs·rdi and T. Nepusz. The igraph software package for complex network research. InterJournal Complex Systems.
  7. Nancy Lopes GarcÌa and JosÈ Luis Palacios. On inverse moments of nonnegative random variables. Statist. Probab. Lett., 53:235-239, 2001. Math. Review MR1841624.
  8. S. Meyn and R. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, London, 1993. Math. Review MR1287609.
  9. W. Smith and W. Wilkinson. On branching processes in random environments. Annals of Mathematical Statistics, 40:814-827, 1969. Math. Review MR0246380.
  10. R. Southwell and C. Cannings. Games on graphs that grow deterministically. In Proc. International Conference on Game Theory for Networks GameNets '09, pp347-356, 2009.
  11. R. Southwell and C. Cannings. Some models of reproducing graphs. 1 Pure reproduction. Applied Mathematics, 1:137-145, 2010.
  12. R. Southwell and C. Cannings. Some models of reproducing graphs. 2 Age capped vertices. Applied Mathematics, 1:251-259, 2010.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.