Randomised Reproducing Graphs
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, $\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
References
- K. E. Athreya and P. E. Ney. Branching Processes Dover Publications, Mineola, New York, 1972.
- 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
- F. Chung, L. Lu, T. Dewey and D. Gales. Duplication models for biological networks. Journal of Computational Biology, 10:677-687, 2003.
- F. R. K. Chung. Spectral Graph Theory. Number 92 in CBMS Regional Conference Series. AMS, Providence, Rhode Island, 1997. Math. Review MR1421568.
- N. Cohen, J. Jordan and M. Voliotis. Preferential duplication graphs. Journal of Applied Probability, 47:582-585, 2010. Math. Review MR2668507.
- G. CsÂ·rdi and T. Nepusz. The igraph software package for complex network research. InterJournal Complex Systems.
- 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.
- S. Meyn and R. Tweedie. Markov Chains and Stochastic Stability. Springer-Verlag, London, 1993. Math. Review MR1287609.
- W. Smith and W. Wilkinson. On branching processes in random environments. Annals of Mathematical Statistics, 40:814-827, 1969. Math. Review MR0246380.
- 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.
- R. Southwell and C. Cannings. Some models of reproducing graphs. 1 Pure reproduction. Applied Mathematics, 1:137-145, 2010.
- R. Southwell and C. Cannings. Some models of reproducing graphs. 2 Age capped vertices. Applied Mathematics, 1:251-259, 2010.
This work is licensed under a Creative Commons Attribution 3.0 License.