Further Properties of Reproducing Graphs

ABSTRACT

Many real world networks grow because their elements get replicated. Previously Southwell and Cannings introduced a class of models within which networks change because the vertices within them reproduce. This happens deterministically so each vertex simultaneously produces an offspring every update. These offspring could represent individuals, companies, proteins or websites. The connections given to these offspring depend upon their parent’s connectivity much as a child is likely to interact with their parent’s friends or a new website may copy the links of pre-existing one. In this paper we further investigate one particular model, ‘model 3’, where offspring connect to their parent and parent’s neighbours. This model has some particularly interesting features, including a degree distribution with an interesting fractal-like form, and was introduced independently under the name Iterated Local Transitivity by Bonato et al. In particular we show connections between this degree distribution and the theory of integer partitions and show that this can be used to explain some of the features of the degree distribution; we give exact formulae for the number of complete subgraphs and the global clustering coefficient and we show how to calculate the minimal cycle basis.

Many real world networks grow because their elements get replicated. Previously Southwell and Cannings introduced a class of models within which networks change because the vertices within them reproduce. This happens deterministically so each vertex simultaneously produces an offspring every update. These offspring could represent individuals, companies, proteins or websites. The connections given to these offspring depend upon their parent’s connectivity much as a child is likely to interact with their parent’s friends or a new website may copy the links of pre-existing one. In this paper we further investigate one particular model, ‘model 3’, where offspring connect to their parent and parent’s neighbours. This model has some particularly interesting features, including a degree distribution with an interesting fractal-like form, and was introduced independently under the name Iterated Local Transitivity by Bonato et al. In particular we show connections between this degree distribution and the theory of integer partitions and show that this can be used to explain some of the features of the degree distribution; we give exact formulae for the number of complete subgraphs and the global clustering coefficient and we show how to calculate the minimal cycle basis.

Cite this paper

nullJ. Jordan and R. Southwell, "Further Properties of Reproducing Graphs,"*Applied Mathematics*, Vol. 1 No. 5, 2010, pp. 344-350. doi: 10.4236/am.2010.15045.

nullJ. Jordan and R. Southwell, "Further Properties of Reproducing Graphs,"

References

[1] P. Erd?s and A. Rényi, “On Random Graphs. I,” Publicationes Mathematicae, Vol. 6, 1959.

[2] G. U. Yule, “A Mathematical Theory of Evolution, Based on the Conclusions of Dr. J. C. Willis, F.R.S.,” Philosophical Transactions of the Royal Society of London, London, Vol. B213, 1925, pp. 21-87.

[3] R. Albert, A. Barabasi and H. Jeong, “Mean-Field Theory for Scale-Free Random Networks,” Physica A, Vol. 272, 1999, pp. 173-187.

[4] M. Penrose, “Random Geometric Graphs,” Oxford University Press, Oxford, 2003.

[5] D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, Vol. 393, No. 6684, 1998, pp. 409-410.

[6] R. Southwell and C. Cannings, “Games on Graphs that Grow Determinis-Tically,” In: Proceedings of International Conference on Game Theory for Networks Game-Nets‘09, Istanbul, 2009, pp. 347-356.

[7] R. Southwell and C. Cannings, “Some Models of Re- producing Graphs. 1 Pure Reproduction,” Under Review.

[8] R. Southwell and C. Cannings, “Some Models of Reproducing Graphs. 2 Age Capped Vertices,” Under Review.

[9] F. Chung, L. Lu, T. Dewey and D. Gales, “Duplication Models for Biological Networks,” Journal of Computational Biology, Vol. 10, 2003, pp. 677-687.

[10] N. Cohen, J. Jordan and M. Voliotis, “Preferential Duplication Graphs,” Journal of Applied Probability, Vol. 47, No. 2, 2010, pp. 572-585.

[11] A. Bonato, N. Hadi, P. Horn, P. Pralat and C. Wang, “Models of on-Line Social Networks,” Internet Mathematics, 2010.

[12] N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences,” 2009. http:www.research.att.com/njas/sequences/

[13] N. J. A. Sloane and J. A. Sellers, “On Non-Squashing Partitions,” Discrete Mathematics, Vol. 294, No. 3, 2005, pp. 259-274.

[14] J. B. Olsson, “Sign Conjugacy Classes in Symmetric Groups,” Journal of Algebra, Vol. 322, No. 8, 2009, pp. 2793-2800.

[1] P. Erd?s and A. Rényi, “On Random Graphs. I,” Publicationes Mathematicae, Vol. 6, 1959.

[2] G. U. Yule, “A Mathematical Theory of Evolution, Based on the Conclusions of Dr. J. C. Willis, F.R.S.,” Philosophical Transactions of the Royal Society of London, London, Vol. B213, 1925, pp. 21-87.

[3] R. Albert, A. Barabasi and H. Jeong, “Mean-Field Theory for Scale-Free Random Networks,” Physica A, Vol. 272, 1999, pp. 173-187.

[4] M. Penrose, “Random Geometric Graphs,” Oxford University Press, Oxford, 2003.

[5] D. J. Watts and S. H. Strogatz, “Collective Dynamics of ‘Small-World’ Networks,” Nature, Vol. 393, No. 6684, 1998, pp. 409-410.

[6] R. Southwell and C. Cannings, “Games on Graphs that Grow Determinis-Tically,” In: Proceedings of International Conference on Game Theory for Networks Game-Nets‘09, Istanbul, 2009, pp. 347-356.

[7] R. Southwell and C. Cannings, “Some Models of Re- producing Graphs. 1 Pure Reproduction,” Under Review.

[8] R. Southwell and C. Cannings, “Some Models of Reproducing Graphs. 2 Age Capped Vertices,” Under Review.

[9] F. Chung, L. Lu, T. Dewey and D. Gales, “Duplication Models for Biological Networks,” Journal of Computational Biology, Vol. 10, 2003, pp. 677-687.

[10] N. Cohen, J. Jordan and M. Voliotis, “Preferential Duplication Graphs,” Journal of Applied Probability, Vol. 47, No. 2, 2010, pp. 572-585.

[11] A. Bonato, N. Hadi, P. Horn, P. Pralat and C. Wang, “Models of on-Line Social Networks,” Internet Mathematics, 2010.

[12] N. J. A. Sloane, “The On-Line Encyclopedia of Integer Sequences,” 2009. http:www.research.att.com/njas/sequences/

[13] N. J. A. Sloane and J. A. Sellers, “On Non-Squashing Partitions,” Discrete Mathematics, Vol. 294, No. 3, 2005, pp. 259-274.

[14] J. B. Olsson, “Sign Conjugacy Classes in Symmetric Groups,” Journal of Algebra, Vol. 322, No. 8, 2009, pp. 2793-2800.