The effect of different network growth rules

Back to Games and networks

The idea here is just to see how different kind of rules that individuals have for forming connections affects the way that the network grows, and particularly how related individuals are clustered in the network. Because this part of the project is exploratory, it can be done in any language (C++/Matlab/?)

The basic structure of the model is something like this. We start with some graph (random, or some other kind) with all nodes of different colors.

At each time step,

1. A random individual is chosen to reproduce an offspring of the same color,
2. the offspring makes connections to other individuals in the graph according to some rule (see below), and
3. a random node dies (to keep population size fixed).

We want to see how related individuals (those of the same color) will cluster in the resulting graph.

There a couple of important things to consider when designing the rules for making connections. First of all, how many connections should each individual make? Some possibilities:

1. The number of connections could be drawn from a predetermined degree distribution (non-heritable)
2. The number of connections could be genetically determined (so, for this part of the project, we'd keep it fixed)
3. The number of connections could be based somehow on the parent's number of connections (heritable, but not genetically encoded)

The problem with the first is that it wouldn't allow organisms to evolve to make many connections. The problem with the second is that we might expect such gene to fix, and then in the limiting distribution all individuals will have the same degree, which is not very realistic. Maybe a compromise would be to have the number of connections be drawn from a Poisson distribution, with the mean determined genetically? Perhaps the best way to resolve this is to figure out type of network real animal social networks resemble (small world?) and then look at the algorithms which others have used to produce these.

The second part is to determine which nodes each individual will choose to connect to. We determined that this should be done with some probability which differs based on the shortest path length from the parent to the candidate. Altruists will want to connect to other altruists, so they should evolve a decreasing function, with very high probability of connecting to the parent, slightly less probability of connecting to the parent's neighbors, and so on (closer relatives are more likely to be altruists as well.) Selfish individuals will also want to connect to altruists, but their close relatives are unlikely to be altruists, so they would prefer to connect to individuals who are not closely related. Depending on the size and structure of the graph (i.e. what proportion of all nodes are close to the focal one) this may not be much different from choosing connections completely randomly.

The challenge is to try to figure out a way to get a representative variety of rules while only changing a single variable. One idea is to use something like a Boltzmann distribution, where the probability is proportional to exp(-k/T), where k is the shortest path length between the parent and the potential neighbor, and T is the "temperature", which is genetically determined. When the temperature is high, the distribution will concentrate near k=0 (the parent); when the temperature is low, the distribution will be uniform over all path lengths. We also talked about truncating the path lengths, e.g., all individuals 4 or more edges away are equivalent. If the graph is kind of small-worldish, this would be particularly effective. It might even be sufficient to consider all individuals more than two edges away as being equivalent.