TITLE:
Further Properties of Reproducing Graphs
AUTHORS:
Jonathan Jordan, Richard Southwell
KEYWORDS:
Reproduction, Graph, Network, Deterministic Twocolumnfalse
JOURNAL NAME:
Applied Mathematics,
Vol.1 No.5,
November
30,
2010
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.