Further properties of reproducing graphs (2010)

Abstract: Many real world networks grow because structures within 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 rep- resent individuals, companies, proteins or websites. The connections given to these offspring depends upon their parents 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 parents 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.

Paper (PDF, 331KB)