Evolutionary dynamics on graphs

Static fitness

Fixation probability of a single mutant in a resident population where mutants have a fixed fitness r and residents have fitness 1. Individuals do not interact and therefore the fixation probability is entirely determined by the structure of the graph.

Frequency dependent fitness

Fixation probability of a single mutant in a resident population where the fitness of both mutants and residents is determined through interactions in a local neighborhood.

Moran process

1. Consider a homogeneous population of size N consiting of residents (white) and mutants (black).
2. At each time step an individual is chosen for reproduction with a probability proportional to its fitness (here, resident is selected for reprodcution).
3. A randomly chosen individual is eliminated (here, mutant is selected for death).
4. The offspring replaces the eliminated individual.

This so-called Moran process describes the stochastic evolution in a finite population of constant size. Suppose all resident individuals are identical and one new mutant is introduced. The new mutant has relative fitness r, as compared to the residents, whose fitness is 1. The fixation probability of the mutant is then given by:

The Moran process has two absorbing states: either the population consists of all residents or all mutants. No other stable equilibrium state is possible. Whenever an absorbing state is reached, mutants (residents) are said to have reached fixation.

This represents a specific balance between selection and drift: advantageous mutations have a certain chance - but no guarantee - of fixation, whereas disadvantageous mutants are likely - but again, no guarantee - to become extinct.

Isothermal theorem

Population structure can be introduced by assuming that the individuals occupy the nodes of a graph. The adjacency matrix W = [w_ij] then determines the structure of the graph, where w_ij denotes the probability that individual i places its offspring into node j. If w_ij = w_ji = 0 then the nodes i and j are not connected. The temperature of a node is given by the sum over the weights of all incoming links and indicates how often it is replaced, i.e. a hot node is replaced often and a cold node is rarely replaced. The isothermal theorem now states that all isothermal graphs have fixation probability R₁ if and only if all nodes have the same temperature. Isothermality is equivalent to requiring that W is doubly stochastic. All regular lattices are examples of isothermal graphs (e.g. square lattices as shown in (i) to the left).

Evolutionary suppressors

The characteristic balance between selection and drift in isothermal graphs can tilt to either side for graphs that are not isothermal. For example, suppose N individuals are arranged in a linear chain (see (i) to the left). Each individual places its offspring into the position immediately to its right. The leftmost individual is never replaced. Clearly, the fixation probability of a randomly placed mutant is 1/N, irrespective of r. The mutant can only reach fixation if it arises in the leftmost position, which happens with probability 1/N. This chain is an example of a simple population structure whose behaviour is dominated by random drift. Another example is a central hub that is connected to the nodes along the periphery but the peripherial nodes have no outgoing links (see (ii) to the left). More generally, any graph with a single root or small upstream population that feeds into large downstream populations acts as a suppressor of selection.

Evolutionary amplifiers

Intriguingly, it is also possible to create population structures that amplify selection and suppress random drift. For example, on the star structure, where all nodes are connected to a central hub and vice versa (see (i) to the left), the fixation probability of a randomly placed mutant becomes

for large N. Thus, any selective difference r is amplified to r². The super-star (see (ii) to the left for K = 3) and related structures have the amazing property that for large N, the fixation probability of any advantageous mutant converges to one, while the fixation probability of any disadvantageous mutant converges to zero. Hence, these population structures guarantee fixation of advantageous mutants however small their selective advantage. In general, we can prove that for sufficiently large population size N, a super-star of parameter K satisfies:

where K denotes the maximum number of edges connecting any two nodes, e.g. K = 1 for a fully connected graph, K = 2 for a star (any two nodes along the periphery are separated by two edges). Just as one-rooted graphs entirely suppress the effects of selection, super-stars function as arbitrarily strong amplifiers of selection and suppressors of random drift. However, note that amplification has it's price in that the average fixation time goes to infinity as the amplification increases.

Games on graphs

So far we assumed that the individuals had a static fitness of 1 and r for residents and mutants, repsectively. However, in many situations it might be more realistic to assume frequency dependent fitness, i.e., scenarios where the fitness of an individual is not determined by its 'genotype' (mutant versus resident) but rather through interactions with other members in the population. Consider, as before, two types A and B, but instead of constant fitness, their fitness now depends on the outcome of a game with a payoff matrix as shown in the table to the left. Such interactions are often called 2×2 games (two players and two strategic types). The ranking of the payoffs a, b, c, and d determines the characteristics of the game. For example, c > a > d > b defines the famous Prisoner's Dilemma if A corresponds to cooperation and B to defection.

In traditional evolutionary game dynamics, a mutant strategy A can invade a resident B if b > d. For games on graphs, the crucial condition for A invading B, and hence the very notion of evolutionary stability, can be quite different. In particular, isothermal graphs no longer have identical fixation probabilities.

Unfortunately, frequency dependent selection is far more complicated because the dynamics and fixation probabilities depend not only on the graph but also on type of interactions and, moreover, it is now possible to distinguish two graphs: the replacement graph (as before) and in addition the interaction graph.

At this point we have only preliminary results of this intriguing field for future research. For example, super-stars again possess powerful amplifying properties. If the payoff of an individual is determined by its downstream neighbor, the fixation probability for large N of a single A mutant is given by R_K (see above) with r = (b/d)(b/c)^K-1. Interestinlgy, the performance of mutants is unaffected by the performance of mutant-mutant interactions. For a super-star with large K, this r value diverges as long as b > c. Thus, even a dominated strategy (a < c and b < d) satisfying b > c will expand from a single mutant to conquer the entire super-star with a probability that can be made arbitrarily close to 1. The guaranteed fixation of this broad class of dominated strategies is a unique feature of evolutionary game theory on graphs: without structure, all dominated strategies die out. Other counter-intuitive results seem to hold for the superstar in other orientations.