Some Models of Reproducing Graphs: II Age Capped Vertices

In the prequel to this paper we introduced eight reproducing graph models. The simple idea behind these models is that graphs grow because the vertices within reproduce. In this paper we make our models more realistic by adding the idea that vertices have a finite life span. The resulting models capture aspects of systems like social networks and biological networks where reproducing entities die after some amount of time. In the 1940’s Leslie introduced a population model where the reproduction and survival rates of individuals depends upon their ages. Our models may be viewed as extensions of Leslie’s model-adding the idea of network joining the reproducing individuals. By exploiting connections with Leslie’s model we are to describe how many aspects of graphs evolve under our systems. Many features such as degree distributions, number of edges and distance structure are described by the golden ratio or its higher order generalisations.

Some Models of Reproducing Graphs: I Pure Reproduction

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.

Further Properties of Reproducing Graphs

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.

Some Models of Reproducing Graphs: III Game Based Reproduction

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 vertices, due to ageing or crowding, or perhaps due to isolation. Such phenomena result in a dynamical system which may lead to complex behaviours, to selfreplication, to chaotic or regular patterns, or to emergent phenomena from local interactions. They hopefully 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 third paper of a series, we consider the vertices to be players of some game. Offspring inherit their parent’s strategies and vertices which behave poorly in games with their neighbours get destroyed. The process is analogous to the way different kinds of animals reproduce whilst unfit animals die. Some game based systems are analytically tractable, others are highly complex-causing small initial structures to grow and break into large collections of self replicating structures.

Best Response Games on Regular Graphs

With the growth of the internet it is becoming increasingly important to understand how the behaviour of players is affected by the topology of the network interconnecting them. Many models which involve networks of interacting players have been proposed and best response games are amongst the simplest. In best response games each vertex simultaneously updates to employ the best response to their current surroundings. We concentrate upon trying to understand the dynamics of best response games on regular graphs with many strategies. When more than two strategies are present highly complex dynamics can ensue. We focus upon trying to understand exactly how best response games on regular graphs sample from the space of possible cellular automata. To understand this issue we investigate convex divisions in high dimensional space and we prove that almost every division of k - 1 dimensional space into k convex regions includes a single point where all regions meet. We then find connections between the convex geometry of best response games and the theory of alternating circuits on graphs. Exploiting these unexpected connections allows us to gain an interesting answer to our question of when cellular automata are best response games.