Some Models of Reproducing Graphs: I Pure Reproduction

ABSTRACT

Many real world networks change over time. This may arise due to individuals joining or leaving the network or due to links forming or being broken. These events may arise because of interactions between the vertices which occasion payoffs which subsequently determine the fate of the nodes, due to ageing or crowding, or perhaps due to isolation. Such phenomena result in a dynamical system which may lead to complex behaviours, to self-replication, to chaotic or regular patterns, to emergent phenomena from local interactions. They give insight to the nature of the real-world phenomena which the network, and its dynamics, may approximate. To a large extent the models considered here are motivated by biological and social phenomena, where the vertices may be genes, proteins, genomes or organisms, and the links interactions of various kinds. In this, the first paper of a series, we consider the dynamics of pure reproduction models where networks grow relentlessly in a deterministic way.

Many real world networks change over time. This may arise due to individuals joining or leaving the network or due to links forming or being broken. These events may arise because of interactions between the vertices which occasion payoffs which subsequently determine the fate of the nodes, due to ageing or crowding, or perhaps due to isolation. Such phenomena result in a dynamical system which may lead to complex behaviours, to self-replication, to chaotic or regular patterns, to emergent phenomena from local interactions. They give insight to the nature of the real-world phenomena which the network, and its dynamics, may approximate. To a large extent the models considered here are motivated by biological and social phenomena, where the vertices may be genes, proteins, genomes or organisms, and the links interactions of various kinds. In this, the first paper of a series, we consider the dynamics of pure reproduction models where networks grow relentlessly in a deterministic way.

Cite this paper

nullR. Southwell and C. Cannings, "Some Models of Reproducing Graphs: I Pure Reproduction,"*Applied Mathematics*, Vol. 1 No. 3, 2010, pp. 137-145. doi: 10.4236/am.2010.13018.

nullR. Southwell and C. Cannings, "Some Models of Reproducing Graphs: I Pure Reproduction,"

References

[1] 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 (Series B), Vol. 213, 1925, pp. 21-87.

[2] H. A. Simon, “On a Class of Skew Distribution Functions,” Biometrika, Vol. 42, No. 3-4, 1955, pp. 425-440.

[3] A. L. Barab′asi and R. Albert, “Emergence of Scaling in Random Networks,” Science, Vol. 286, No. 5439, 1999, pp. 509-512.

[4] B. Bollob′asi, O. Riordan and G. Spenser, “The Degree Sequence of a Scale-Free Random Graph,” Random Structures and Algorithms, Vol. 18, No. 3, 2001, pp. 279- 290.

[5] J. Jordan, “The Degree Sequences and Spectra of Scale-Free Random Graphs,” Random Structures and Algorithms, Vol. 29, No. 2, 2006, pp. 226-242.

[6] C. Cannings and A. W. Thomas, “Handbook of Statistical Genetics,” John Wiley and Sons Ltd, New York, 2007.

[7] J. S. Taylor and J. Raes, “Duplication and Divergence: The Evolution of New Genes and Old Ideas,” Annual Review of Genetics, Vol. 38, No. 1, 2004, pp. 615-643.

[8] A. Widdig, P. Nurnberg, M. Krawczak, W. J. Streich and F. B. Bercovitch, “Paternal Relatedness and Age Proximity Regulate Social Relationships among Adult Female Rhesus Macaques,” Proceedings of the National Academy of Science USA, Vol. 98, No. 24, 2001, pp. 13769- 13773.

[9] G. Hausfater, “Dominance and Reproduction in Baboons (Papio Cynocephalus),” Contributions to Primatology, Vol. 7, 1975, pp. 1-150.

[10] L. Frank, K. Holekamp and L. Smale, “Serengeti II: Dynamics, Management, and Conservation of an Ecosystem,” University of Chicago Press, Chicago, 1995.

[11] W. Imrich and S. Klavar, “Product Graphs: Structure and Recognition,” John Wiley and Sons Ltd, New York, 2000.

[12] S. Wolfram, “A New Kind of Science,” Wolfram Media, Inc., Champaign, 2002.

[13] P. Erd¨os, A. W. Goodman and L. Posa, “The Representation of a Graph by Set Intersections,” Canadian Journal of Mathematics, Vol. 18, No. 1, 1966, pp. 106-112.

[1] 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 (Series B), Vol. 213, 1925, pp. 21-87.

[2] H. A. Simon, “On a Class of Skew Distribution Functions,” Biometrika, Vol. 42, No. 3-4, 1955, pp. 425-440.

[3] A. L. Barab′asi and R. Albert, “Emergence of Scaling in Random Networks,” Science, Vol. 286, No. 5439, 1999, pp. 509-512.

[4] B. Bollob′asi, O. Riordan and G. Spenser, “The Degree Sequence of a Scale-Free Random Graph,” Random Structures and Algorithms, Vol. 18, No. 3, 2001, pp. 279- 290.

[5] J. Jordan, “The Degree Sequences and Spectra of Scale-Free Random Graphs,” Random Structures and Algorithms, Vol. 29, No. 2, 2006, pp. 226-242.

[6] C. Cannings and A. W. Thomas, “Handbook of Statistical Genetics,” John Wiley and Sons Ltd, New York, 2007.

[7] J. S. Taylor and J. Raes, “Duplication and Divergence: The Evolution of New Genes and Old Ideas,” Annual Review of Genetics, Vol. 38, No. 1, 2004, pp. 615-643.

[8] A. Widdig, P. Nurnberg, M. Krawczak, W. J. Streich and F. B. Bercovitch, “Paternal Relatedness and Age Proximity Regulate Social Relationships among Adult Female Rhesus Macaques,” Proceedings of the National Academy of Science USA, Vol. 98, No. 24, 2001, pp. 13769- 13773.

[9] G. Hausfater, “Dominance and Reproduction in Baboons (Papio Cynocephalus),” Contributions to Primatology, Vol. 7, 1975, pp. 1-150.

[10] L. Frank, K. Holekamp and L. Smale, “Serengeti II: Dynamics, Management, and Conservation of an Ecosystem,” University of Chicago Press, Chicago, 1995.

[11] W. Imrich and S. Klavar, “Product Graphs: Structure and Recognition,” John Wiley and Sons Ltd, New York, 2000.

[12] S. Wolfram, “A New Kind of Science,” Wolfram Media, Inc., Champaign, 2002.

[13] P. Erd¨os, A. W. Goodman and L. Posa, “The Representation of a Graph by Set Intersections,” Canadian Journal of Mathematics, Vol. 18, No. 1, 1966, pp. 106-112.