## Abstract

There is a growing interest in the study of evolutionary dynamics on populations with some non-homogeneous structure. In this paper we follow the model of Lieberman *et al*. (Lieberman *et al*. 2005 *Nature* **433**, 312–316) of evolutionary dynamics on a graph. We investigate the case of non-directed equally weighted graphs and find solutions for the fixation probability of a single mutant in two classes of simple graphs. We further demonstrate that finding similar solutions on graphs outside these classes is far more complex. Finally, we investigate our chosen classes numerically and discuss a number of features of the graphs; for example, we find the fixation probabilities for different initial starting positions and observe that average fixation probabilities are always increased for advantageous mutants as compared with those of unstructured populations.

## 1. Introduction

Evolutionary dynamics models are widespread, but have generally assumed homogeneous populations. The study of evolutionary dynamics on graphs was investigated in the paper by Lieberman *et al*. (2005), other important work on this subject being in Erdös & Renyi (1960), Nagylaki & Lucier (1980) and Barabasi & Albert (1999). Each vertex or node represents an individual in the population, and individuals can reproduce into neighbouring vertices, i.e. those connected by an edge. In Lieberman *et al*. (2005), at each stage an individual was selected randomly, with probability proportional to its fitness, which then copied itself into one of the vertices it was connected to. It should be noted that there are other possible dynamics. An example is the biased voter model, e.g. see Bramson & Griffeath (1981), where an individual is chosen at random to be removed and is replaced by a copy of one of its neighbours. Lieberman *et al*. (2005) considered directed graphs where connections between vertices can be one-way only (e.g. it is possible for an individual at 1 to reproduce into 2, but not for one at 2 to reproduce into 1), with general weightings indicating the probability that any particular vertex would be replaced, given the chosen replacing vertex. They showed several interesting and important results; for instance, different graph structures could yield different probabilities for the fixation of a single mutant. In homogeneous populations, the probability of fixation in a population with *N* individuals (and so *N* vertices) is given by the Moran probability,(1.1)where resident individuals have baseline fitness 1 and mutants have fitness *r* (each individual being chosen as the reproducing individual with probability proportional to its fitness). It was shown in Lieberman *et al*. (2005) that this probability holds under a condition on the weightings on the graph, any graph satisfying this condition being referred to as an *isothermal* graph. However, other graph structures allow the probability of fixation of an advantageous mutant (*r*>1) to converge to either 0 or 1 as *N* tends to infinity.

Most of the interesting results from Lieberman *et al*. (2005) relied on graphs being directed and the weights of connections from a given vertex to be different from each other. In this paper we look at non-directed graphs with equal weights. We show that in this setting, the formula (1.1) holds for regular graphs, graphs where every vertex has the same degree, and only for them. We then show that evolutionary dynamics on a graph with *N* vertices leads to a system of 2^{N} equations; with the exception of a circle (a regular graph case) and a line (a non-regular graph). We use symmetries to reduce the number of equations to 2*n*+1 for a star with *N*=*n*+1 vertices. In Lieberman *et al*. (2005), the approximation of the fixation probability for stars for large *n* was given by(1.2)Here we find the exact fixation probabilities for any *r* and *n*.

We then analyse the dynamics on the line. The analysis is quite hard to perform even in this simple case, although we make substantial progress. We also make suggestions about how to attack the more general problem without simply resorting to numerical methods and simulation.

## 2. Evolutionary dynamics on graphs

Let *G*=(*V*, *E*) be a finite, undirected and connected graph, where *V* is the set of vertices and *E* is the set of edges. We assume that the graph is simple, i.e. no vertex is connected to itself and there are no parallel edges. We study evolutionary dynamics as described in Lieberman *et al*. (2005; see also Nowak 2006). We treat the dynamics as a discrete time Markov chain. At the beginning, a vertex is chosen uniformly at random and replaced by a mutant with fitness *r*, all remaining vertices having fitness 1.

If the mutants already inhabit precisely the vertices in the set *C*⊂*V*, then in the next step the mutants will inhabit vertices in either

a set

*C*∪(*j*),*j*∉*C*, provided (a) a vertex*i*∈*C*is chosen for reproduction and (b) it places its offspring into vertex*j*, ora set ,

*i*∈*C*, provided (a) a vertex*j*∉*C*is selected for reproduction and (b) it places its offspring into*i*, orthe set

*C*, provided an individual from*C*replaces another individual from*C*.

The states and *V* are the absorbing points of the dynamics. The transition probabilities of the above Markov chain are determined by (i) the probability that a given vertex will be selected for reproduction and (ii) the probability that, once selected, it places its offspring into another given vertex.

We set the fitness of an individual at vertex *i* as *f*_{i}∈{1,*r*}, where *f*_{i}=*r* means that the individual is a mutant. An individual at *i* is selected for reproduction with the probability(2.1)

The graph structure is represented by a matrix *W*=(*w*_{ij}), where *w*_{ij} is the probability of replacing a vertex *j* by a copy of a vertex *i*, provided vertex *i* was selected for reproduction,where *e*_{i} is the number of edges incident to the vertex *i*, so that edges have equal weights.

Let *P*_{C} denote the probability of mutant fixation, given mutants currently inhabit a set *C*. The rules of the dynamics yield (see Lieberman *et al*. 2005)(2.2)with and *P*_{V}=1.

This system has a unique solution following from the uniqueness of a Markov chain, given a known initial distribution. There is a unique distribution over the states at time 0 (a single mutant is introduced to the population at a randomly chosen vertex). The Kolmogorov equations then give a unique distribution at step *s*+1, conditional on uniqueness at step *s*. As *s* tends to infinity, there is convergence to the set of absorbing states (either all mutants or all residents). This yields a unique limiting distribution, thus a unique fixation probability from the initial distribution.

The system (2.2) of linear equations is very large (typically of the order of 2^{|V|} equations, see §4) and very sparse (from any state *C*, one can go to at most |*V*| other states).

## 3. Regular graphs

A graph is called isothermal if is constant as a function of *i*. A graph is isothermal if and only if the matrix *W*=(*w*_{ij}) is double stochastic (Lieberman *et al*. 2005), i.e.It is proved in Lieberman *et al*. (2005) that if a graph is isothermal then(3.1)Here we give a different proof of this statement and one more equivalent condition to being isothermal.

*A simple connected undirected graph G*=(*V*, *E*) *is isothermal if and only if it is regular*.

Clearly, if *G* is regular, *e*_{i} is constant, and thus *G* is isothermal. Now suppose that the relation in the other direction is not true. Consider a set . Since, by our assumption, *C*≠*V*, there must be a vertex *i*∈*C* that is connected to a vertex . Then,a contradiction. ▪

In order to solve (2.2) for an isothermal graph, let us assume that *P*_{C} only depends upon the size of *C*, so that(3.2)By theorem 3.1, *w*_{ij} attains only one non-zero value (1/*k*, where *k* is the degree of any vertex in *G*) and thus (2.2) reduces to(3.3)This is a standard difference equation that gives the required Moran probabilities. Consequently, our assumption (3.2) leads to a solution of (2.2) and by the uniqueness of the solution, the solution must satisfy the property (3.2).

## 4. Complexity of the dynamics

Since at every vertex of a graph *G*=(*V*, *E*) there can be either a resident or a mutant, there are up to 2^{|V|} potential mutant formations and thus up to 2^{|V|} equations in (2.2).

Some formations of mutants on a given graph are identical owing to symmetries (automorphisms) of the graph. Certain graphs (like a complete graph, or a star graph—see §5) thus have only a few possible mutant–resident patterns since their automorphism group is very rich. For other graphs, like a line, the graph structure itself yields only symbolic reduction of the number of patterns because the automorphism group consists of only a few non-trivial elements.

Taking the automorphism group of a graph *G*, Aut(*G*), into account, we can use Burnside's orbit-counting theorem (Tucker 1994) to find the exact number of possible formations. Consider the set *X* consisting of all possible 2^{|V|} mutant–resident patterns. For *f*∈Aut(*G*), let Fix(*f*)={*v*∈*V*, *f*(*v*)=*v*}. If Fix(*f*)≠*V*, then *f* fixes 2^{|Fix(f)|+1} elements of *X* (one has freedom to put a mutant or a resident in any vertex *v*∈Fix(*f*), and one can place either mutants or residents into all vertices of ). Clearly, identity on *G* is the only *f*∈Aut(*G*) that fixes all elements of *G*. Burnside's theorem then yields the total number of mutant–resident formations (MRF) of *G* as(4.1)

The above equation considers the graph structure only, not the rules of the dynamics at all. Clearly, any non-initial state of the dynamics contains at least one parent–offspring pair of connected vertices. Consequently, alternating patterns, i.e. patterns where any pair of connected vertices is inhabited by a mutant at one vertex and a resident at the other vertex, cannot be attained as a result of the dynamics. Alternating patters are possible if and only if the graph does not contain an odd cycle (i.e. if the graph is bipartite). There are at most two alternating patterns.

On a circle or on a line, any mutant formation resulting from the dynamics consists of a connected segment. Hence, they are of the order of |*V*|^{2} patterns on a circle (|*V*| possibilities where the segment starts and |*V*|−1 possibilities where it ends, plus the patterns with all or no mutants) and |*V*|^{2}/2 patterns on a line (|*V*| possibilities to start and on average |*V*|/2 possibilities where the segment can end). Moreover, the rotations on the circle help us to reduce the number of equations to |*V*|; the symmetry of a line also reduces the number of equations by a factor 1/2 to approximately |*V*|^{2}/4.

The theorem 4.1 shows that for the vast majority of graphs, the system (2.2) consists of roughly MRF(*G*) equations.

*If a graph contains a vertex of degree of at least 3* (*i.e. the graph is neither a line nor a circle*) *and the dynamics is in any non-absorbing state, then there is a non-zero probability that the dynamics will evolve to any of the possible MRF*(*G*) *states* (*MRF*(*G*)−2 *states if the graph is bipartite*).

Before proving theorem 4.1, we prove a result required for the proof.

*Let vertices v*_{1} *and v*_{2} *be connected to a vertex t*. *Furthermore, assume that there is a mutant in* *and a resident in v*_{1}. *Then, we can fill any pattern to any subtree structure connected to t and not containing v*_{1} *and v*_{2}.

The proof goes by the induction on the height of the subtree structure. If the height is 1 (i.e. the structure is only the vertex *t*), we can clearly fill it by a mutant or a resident. Now assume that we can fill any pattern to the subtree of height *n*−1 and that our structure has a height *n*.

First, spread the residents (from *v*_{1}) to get the structure that contains only residents (figure 1*a*). Next, spread the mutants (from *v*_{2}) to every vertex but the leaves where there are residents in the target pattern. After this step, all of the leaves have the inhabitants of the target pattern (figure 1*b*). Cut the leaves and what remains is the structure of height *n*−1. This can be filled by any pattern by the induction hypothesis. This concludes the proof of lemma 4.2. ▪

We now prove theorem 4.1 using multiple applications of lemma 4.2. To do this, there are some technical difficulties that have to be overcome. Firstly, the original graph has to be ‘trimmed’ to become a tree so we can apply the lemma. Secondly, we need space to manoeuvre since lemma 4.2 does not allow us to fill patterns ‘behind’ the vertices *v*_{1} and *v*_{2}, and thus we need to arbitrarily flip the roles of vertices connected to *t*. We obtain this space by collapsing the target pattern by a single vertex, which allows us to have the central vertex completely free for our use. Finally, the trimming could cause some patterns to become inaccessible (alternating) on the tree, although they were not alternating on the original graph, so we have to deal with these patterns in one more step.

Firstly, we trim the graph to get a tree. Denote one of the vertices with a degree of at least 3 by *t*_{0} and label three of its neighbours as *t*_{1}, *t*_{2}, *t*_{3}. Next, trim the graph by cutting a sufficient number of edges to get a connected tree (a graph with no cycle) consisting of all of the original vertices and yet keeping all of the edges *t*_{0}*t*_{j}, *i*=1, 2, 3 intact. Label the remaining neighbours (if any) of *t*_{0} by *t*_{4}, …, *t*_{k}. We will show that we can reach any state that is non-alternating (on this tree) from any non-absorbing state even if only the edges of this trimmed graph are used.

Then we collapse a pattern to get the central vertex *t*_{0} for free usage. Since the target state is not alternating, there are two connected vertices with the same type of inhabitants. We may assume that the vertices are on the branch (linear set) *B*=*b*_{0}*b*_{1}*b*_{2}*b*_{3}...*b*_{l} with *b*_{0}=*t*_{0} and *b*_{1}=*t*_{1}; let *b*_{i} and *b*_{i+1} be the two vertices with the same inhabitants and with the lowest index *i* possible. Let *S* denote the target state and *S*^{*} the state that is the same as the target state except that at vertices *b*_{j}, *j*=1, …, *i* it has inhabitants from the vertices *b*_{j−1} of the target state. Note that *S* and *S*^{*} are each attainable from the other by a shift of the pattern along the line (see figure 2*a*,*b* for an illustration of this).

We now move the mutants into a position where lemma 4.2 can be applied. From above it is enough to reach the state *S*^{*}. Also, we may assume that in *S*^{*}, *t*_{1} is inhabited by a mutant (i.e. in the original target state, *t*_{0} is inhabited by a mutant). If the contrary is true, we would just interchange the role of residents and mutants in the following arguments.

Clearly, any non-absorbing state can evolve into a state with one mutant only. If the mutant is not at *t*_{2} already, we can relabel *t*_{2} and *t*_{3} such that the shortest path from the mutant's position to *t*_{2} goes through *t*_{0}. Now the mutants can spread to *t*_{2} by this shortest path, leaving the trail of mutants behind. The trail can be cleared by spreading residents from either *t*_{1} or *t*_{3} (see figure 2*c–e* for illustration).

Applying lemma 4.2 for the first time, we can fill any pattern to subtrees starting at *t*_{3}, *t*_{4},…,*t*_{k}.

We now rotate the mutant–resident pattern around *t*_{0} and fill the branch behind vertex *t*_{1}; we then rotate again and fill behind *t*_{2}. We use lemma 4.2 to place a resident at *t*_{3} (thus having a mutant at *t*_{2} and a resident at *t*_{3}) and use lemma 4.2 again to fill the pattern *S*^{*} to the subtree starting at *t*_{1}. At the end, there will be a mutant in *t*_{1}. Since now we have a mutant in *t*_{1} and a resident in *t*_{3}, we can fill the required pattern to the subtree starting at *t*_{2}. If there has to be a mutant at *t*_{3}, place it there by spreading from *t*_{1} through *t*_{0}. In any case, finish by shifting the pattern from *S*^{*} to *S*.

So far, we have been able to reach any state that is not alternating on the trimmed graph. It is possible that an alternating state on the trimmed graph is not an alternating state on the original graph. If we want to reach this pattern, let us pick vertices *w*_{1}, *w*_{2} witnessing that the pattern is not alternating on the original graph. We may assume that they are both inhabited by mutants. If we change the mutant in *w*_{1} into a resident, we get a pattern that is not alternating on the trimmed graph. In particular, we can reach it as shown above. To reach the required pattern, it only remains to spread the mutant from *w*_{2} into *w*_{1}; we can do that because vertices *w*_{1} and *w*_{2} are connected in the original graph. ▪

## 5. Dynamics on stars

In this section, we consider a star—a non-directed graph with *N*=*n*+1 vertices labelled 0, 1, …, *n* where the only edges are between vertices 0 and *i*, *i*=1, …, *n*. The vertex 0 is called a centre and the vertices 1, …, *n* can be called the leaves. The automorphism group is isomorphic to the group of permutations on leaves and the state of the dynamics can be described by the number of mutants at the leaves and by an indicator of whether or not there is a mutant at the centre (see figure 3 for a scheme of the dynamics). Let denote the probability of fixation, given that there are *i* mutants at the leaves and there is a (there is no, respectively) mutant at the centre. The rules of the dynamics yield the following system of 2*n*+1 equations:(5.1)and(5.2)for *i*=0, …, *n* with boundary conditions and . The equation (5.1) can be rearranged to(5.3)We can use (5.3) and (5.2) to inductively calculate as a function of to get

Since , we getSince, by (5.1) and (5.2),and we get as the average fixation probability for a mutant,Note that for large *n* we getwhich means that we are recovering the formula (1.2) from Lieberman *et al*. (2005).

Figure 4 contains illustrations of the results for fixation probability and a comparison with the formula (1.2) and with the fixation for a Moran process (1.1).

## 6. Dynamics on lines

In this section we consider a line with *N*=*n*+1 vertices labelled 0, 1, …, *n*, which is a non-directed graph where vertices *i* and *j* are connected if and only if |*i*−*j*|=1. Hence, the vertices 0 and *n* are connected to just a single vertex, and will be referred to as the *end vertices*, while all other vertices are connected to exactly two others.

In this section, we code the admissible mutant configuration by a pair of numbers (*i*, *j*), 0≤*i*≤*j*≤*n*+1, translate the dynamics (2.2) into this coding, identify the evolution under this dynamics with a random walk on a triangle in a two-dimensional square lattice and then reduce the number of equations from the order of *n*^{2}/4 to *n*.

### (a) States and transition probabilities

The mutant population starts with a single individual; new mutants can arise only in vertices on neighbouring points on the line, and mutants can only be lost from vertices connected to a resident individual. Thus, the population of mutants forms a line segment *i*, *i*+1, …, *j*−1 for some pair (*i*, *j*) where *i*≤*j*, and the state of the system can be described by this pair of numbers only. The evolution of the population can thus be seen as a two-dimensional random walk on a triangular set,Let *P*_{i,j} denote the probability of mutant fixation given that we are at the state (*i*, *j*). Once the population reaches the diagonal state (*i*, *j*) for 0≤*i*≤*n*+1, the mutants are extinct, i.e.(6.1)Once a mutant reaches an end vertex, i.e. the population is in the state (0, *j*) or (*j*, *n*+1) for some 0≤*j*≤*n*+1, it will never be removed from the end vertex unless through extinction, since it can only be removed by a resident on its sole neighbouring vertex, which in turn can only be present if the end vertex individual is the sole mutant in the population. Hence, the population stays on these boundary lines once it reaches them. In §6*b* we calculate that(6.2)

We thus have to solve the two-dimensional random walk on a set *T* given the boundary conditions (6.1) and (6.2).

We proceed to investigate the transitions in the interior of *T*. First, it should be noted that for most choices of a vertex for reproduction, the population does not change. The only change occurs when we choose a vertex on a boundary between mutants and non-mutants. When 2≤*i*<*j*≤*n*−1, there are two boundaries and a change of state may occur if any of the vertices *i*−1, *i*, *j*−1 or *j* are chosen. None of these vertices is an end vertex and thus(6.3)

When a mutant occupies one of the end vertices, there is just one mutant–resident boundary, and only two choices of vertices allow a change of state,(6.4)(6.5)

(6.6)and(6.7)

When a mutant occupies a vertex next to an end vertex (1 or *n*−1), with a resident at the corresponding end vertex, we have, for 2≤*j*≤*n*−1,(6.8)

(6.9)

(6.10)

The system (6.3)–(6.10) is of the order of *n*^{2}/2 equations. By symmetry (equations (6.7) and (6.10)), the system reduces to the order of *n*^{2}/4 equations.

### (b) Boundary conditions

The equations (6.4)–(6.6) are difference equations for *P*_{0,j}. Using standard methods (e.g. Norris 1997, ch. 1), by (6.5), we have to find the roots ofSince the roots are *x*=1 and 1/*r*, we get(6.11)The values *A*, *B* are determined after technical calculation using equations (6.4) and (6.6). This yields, for 0≤*j*≤*n*+1,(6.12)

### (c) The inner boundary

Using the equations (6.8)–(6.10), we obtain(6.13)

(6.14)

Since we can calculate *P*_{0,j}, *j*=0, …, *n*, we just need to calculate *P*_{2,j} in terms of *P*_{1,k}, *k*=1, …, *n* to get a system of *n* equations for *n* unknowns *P*_{1,k}, *k*=1, …, *n*.

### (d) Interior points

In Miller (1994), a two-dimensional random walk on a square lattice,with arbitrary boundary conditions at stateswas solved. In this paper, we relabel the boundary coordinates of the square to be appropriate to the application from our problem, givingwith boundary conditions at states,

Our goal is to extend the random walk from *T* to *S* while giving fictional boundary conditions on *S* such that the restriction of the extended walk will give us exactly the original walk on *T* with the boundary conditions (6.1) and (6.2). This is illustrated in figure 5.

In the notation of Miller (1994), we have(6.15)where *T*_{(a,} _{b)ij} is the expected number of times the state (*a*, *b*) is visited given that the initial state is (*i*, *j*). By Miller (1994, eqn (4.3)),(6.16)whereNote that(6.17)

### (e) Fictitious boundary conditions

It should be noted that in this section we are not dealing with the fixation probabilities as such, but rather finding methods of solving an arbitrary set of equations. Thus, we will have expressions in terms that resemble probabilities, though they are not so (e.g. *P*_{i,j} where *i*>*j*), which have negative solutions. These solutions, however, obey the correct transition equations and have the correct boundary conditions for the region of interest.

In this section, we give the fictitious boundary conditions for the random walk on the whole square. So far, in §6*c* we have equations for *P*_{1,a} and *P*_{a,n} for all 1≤*a*≤*n*. We need to calculate *P*_{a,1} and *P*_{n,a}. By (6.1) and (6.15)–(6.17)The above can be true ifThis implies that

### (f) Reduction to n equations

DenoteConsequently, by (6.10), (6.15) and (6.16),(6.18)Referring back to (6.13) and (6.14), this gives us the following linear simultaneous equations in the probabilities *P*_{1,j}, 2≤*j*≤*n*−1 and *P*_{1,n},After solving the above system for *P*_{1,k}, we can reconstruct *P*_{i,j} for all *i*, *j* by (6.18). The fixation probability for a line is then given by(6.19)

## 7. A comparison between line and circle with a numerical example

Using the above equations, we can find the fixation probabilities for any given position, and thus the overall fixation probability for a line for a particular case. A circle is a regular graph and hence by theorem 3.1 it has the Moran fixation probability. In general, the fixation probability of a random mutant is greater on a line than on a circle for mutants that are fitter than the residents *r*>1 and is less on a line for mutants that are less fit. In figure 6, we can see how the average fixation probability for a line decreases as the number of vertices increases. The decrease is much steeper for *r*<1. For any *r*, the average fixation probability for a line approaches the Moran probability (demonstrated in figure 7). If *r*>1, the fixation probability for a line is greater than the fixation probability for the Moran process and it is smaller otherwise. Figure 8 shows how the absolute and relative differences change as *r* changes from 0 to larger numbers. The absolute difference is at its largest for mutants that are advantageous, but not overwhelmingly so. This is reasonable as these have an intermediate probability of fixation and so structural changes have the greatest possibility of altering this probability. Highly advantageous mutants are likely to achieve fixation whatever the structure, and non-advantageous ones are unlikely to do so (note that the large relative difference for small *r* in figure 8*b* corresponds to a very small fixation probability in each case). The dependence of the difference between a line and a circle on *r* is more or less the same for other *n* as the one shown for a line with *n*+1=10 vertices.

Why is the mutant fitter on a line than a circle if and only if *r*>1? The key reason for this is related to the behaviour at the end vertices. The fixation probabilities for a mutant placed into a specific vertex are given in figure 9. The end vertices 0 and *n* have the highest fixation probability—because the only way the mutant can go extinct is by being replaced by a resident from vertex 1 or *n*−1. But even if a resident at 1 or *n*−1 is selected for reproduction, it has only a 50% chance (if *n*+1>3) of placing its offspring in the corner.

There is a steep drop in fixation probabilities for the vertex adjacent to the corner, 1 or *n*−1, since a mutant placed at 1 has a very high chance of being replaced by a resident from 0 (which, if selected has to place its offspring at 1).

As a vertex gets closer to the middle of the line, then the fixation probability increases if *r*>1, and decreases if *r*<1. If *r*>1, then when the line is sufficiently long, the vertices close to the middle have approximately the same fixation probability as given by the formula for the Moran process. Generally, the higher the value of *r*, the shorter the line can be to have the central vertices equivalent to the corresponding Moran process. In other words, the higher the *r*, the shorter is the range of the effect of the corner endpoint. Being near the centre can be thought of as equivalent to being in a circle; for an advantageous mutant once it has spread to be next to the corner (the first time it is influenced by the corner), it is likely that there will be many mutants and fixation will be almost assured. Usually advantageous mutants are eliminated early, due to bad luck, and so the corners do not affect the fixation probability of such mutants much (and hence the larger *r*, the stronger this effect).

However, this is not true for the case *r*<1. This is an interesting qualitative distinction between *r*<1 and *r*>1, and occurs because non-advantageous mutants are unlikely to reach fixation unless by chance they reach a large proportion of the population, and so the corner will influence their fixation probability no matter where they start. In fact, securing a corner position seems important for their eventual survival, so being near a corner is better than being in the centre, even though this means that very early removal is more likely (the non-advantageous mutant needs to be lucky to reach fixation).

A similar pattern holds for larger groups of mutants on the line. Figure 10 shows the situation once a small group of mutants has been established, comparing the fixation probabilities for such a configuration of several mutants in their different possible positions.

Any ‘middle’ configuration of *k* mutants has approximately the same fixation probability. The corner configuration has a probability equivalent to having one more vertex in a non-corner position; the reason for this relates to the fact that the fixation probability of a corner mutant is approximately twice that of its neighbour for mutants whose fitness is close to that of the residents. This is true for various line lengths and numbers of mutants (note that this approximation becomes less good as the number of mutants increases, and the fixation probability becomes high).

## 8. Discussion

In this paper, we have considered the use of evolutionary dynamics on graphs popularized by Lieberman *et al*. (2005). We have found an analytic way, using the work of Miller (1994), to obtain the fixation probability of mutant populations for one particular type of graph, a line. We cannot find explicit functional forms, but rather a set of *N* simultaneous linear equations, where *N* is the population size, which need to be solved and then yield the probability of fixation in any allowable situation. This is a significant saving on the order of *N*^{2} equations derived directly by considering the transition probabilities between the states of our system.

We have used our solutions to consider various examples and explore the relationship between the fixation probability of a mutant on the circle, given by the Moran probability, and the fixation probability on the line, both the average of such probability and its value for given starting positions. We find that for mutants that are fitter than the resident population, the fixation probability on the line is larger than on the circle. There is also an interesting pattern in the fixation probability for the different starting positions on the line. The best place for a mutant to start is always in the corner. For advantageous mutants, the place next to the corner is the worst and fixation probabilities increase towards the central positions. For mutants that are not advantageous, the further from the corner they are, the worse the position they are in. It should be noted that the probability of fixation for non-advantageous mutants for graphs with more than a small number of vertices is generally low, thus the results for advantageous mutations are more interesting.

In §4 we show that for more complex graphs (which are the vast majority of graphs not of our linear type), almost all system states are reachable from almost all others, and so the number of equations generated by considering the transition probabilities is not of the order of *N*^{2} but much larger. For some graphs with a lot of symmetry, the number of equations can be reduced considerably, and in §5 we analyse one such well-known case, the star, to produce an exact solution for the fixation probability of a mutant. However, graphs that can be solved in this way are special cases and the approaches that we take here for a line or a star will be hard to take elsewhere. Thus, it is probable that we will have to resort to more numerical methods, as in Santos *et al*. (2006), Paley *et al*. (2007) and Rychtář & Stadler (2008).

However, to gain an insight into the deeper aspects of the problem and the effect of various structures, analysis is useful, and in future work we intend to use approximation methods to investigate this. This has the benefit of extending to larger more complex graphical systems, such as the small-world networks of Bollobas & Chung (1988; see also Watts & Strogatz 1998; Newman & Watts 1999; Newman *et al*. 2006; Durrett 2007). Small-world graphs are regular in form with most vertices unconnected, but with a few added random connections that generally make the path length between any two vertices short.

In summary, in this paper, we have found analytic solutions for the mutant fixation probabilities of important classes of graphs, used these solutions to gain further understanding of the underlying processes on graphs in general and also demonstrated the practical limitations to extending our methods. We have thus taken a small step in our journey towards understanding the complex nature of evolutionary dynamics on graphs.

## Acknowledgments

The research was supported by EPSRC grant EP/E043402/1 and by NSF 0634182.

## Footnotes

- Received February 8, 2008.
- Accepted April 23, 2008.

- © 2008 The Royal Society