## Abstract

This paper presents an adaptation of the Moran birth–death model of evolutionary processes on graphs. The present model makes use of the full population state space consisting of 2^{N} binary-valued vectors, and a Markov process on this space with a transition matrix defined by the edge weight matrix for any given graph. While the general case involves solution of 2^{N} – 2 linear equations, symmetry considerations substantially reduce this for graphs with large automorphism groups, and a number of simple examples are considered. A parameter called graph determinacy is introduced, measuring the extent to which the fate of any randomly chosen population state is determined. Some simple graphs that suppress or enhance selection are analysed, and comparison of several examples to the Moran process on a complete graph indicates that in some cases a graph may enhance selection relative to a complete graph for only limited values of the fitness parameter.

## 1. Introduction

Evolutionary dynamics has been a subject of interest for over 50 years, but only recently has the question of how population structure influences evolutionary processes been extensively addressed [1,2]. The assumption in earlier work was that model populations are homogeneous; or if not, that population structure has little or no effect on dynamics [3,4]. Recent work with population models based on directed or undirected graphs shows to the contrary that population structure can significantly influence single vertex fixation probabilities and time to fixation [1,2,5–9].

This article presents an approach to computation of fixation probabilities for *m* mutants in a structured population of *N*>*m* individuals. In particular, general equations for fixation probabilities arising from a birth–death process in such a population are derived for the case in which population structure is represented by an edge weighted directed graph with *N* vertices. Following this, a large set of graphs called circular flows is defined and several examples are analysed, including star graphs and simple funnel graphs. The general result obtained in [7] for the single vertex fixation probability for star graphs is reproduced. Analysis of simple funnel graphs and a constricted cycle graph indicates that in such cases, selection is enhanced relative to selection in a homogeneous population, for only a limited range of the fitness parameter.

Consider a population of *N* individuals evolving in discrete time, consisting of *m* mutants with fitness *r* and *N* – *m* normals with relative fitness 1. At each iteration, a random individual is chosen to reproduce, and another (or the same) individual is chosen to die and be replaced by a clonal copy of the reproducing individual. The reproductive choices are biases by fitness: for *r*>1, mutants are more likely to be chosen for reproduction. Mathematically, this is represented on a complete graph with *N* vertices, with all edges (including loops at each vertex) given a weight 1/*N*, indicating the probability of an individual at any given vertex replacing an individual at an adjacent vertex. The population state at any time is represented by a length *N* binary vector *v*=(*v*_{1},…,*v*_{N}), where *v*_{i} is 0 or 1, respectively, when vertex *i* is occupied by a normal or a mutant. This is the birth–death Moran process [10]. Since mutations are assumed to be rare, much of the attention has been in computing the probability of a single mutation going to fixation in the population, but the fixation probability of general distributions of mutants is also of interest.

The Moran process is a biased random drift Markov process on the state space {0,1,…,*N*}, where a state *m* indicates a population state with *m* mutants and *N* – *m* normals. Following [11], states 0 and *N* are absorbing states and, if *p*_{m,m−1} and *p*_{m,m+1} are the respective probabilities of the state transitions and , the (*N*+1)×(*N*+1) Markov transition matrix has the form
1.1
Thus, if *x*_{k} is the probability of reaching fixation (state *N*) from state *k*, then
1.2
and the single vertex fixation probability *ρ* is *x*_{1}. Setting
1.3
and solving for *x*_{1} yields [11]
1.4
Determination of the fixation probability becomes a matter of finding *p*_{m,m±1}. For the Moran process, these are easily found to be
1.5
hence, a brief calculation yields [11]
1.6
Since it corresponds to an unstructured population, the Moran process provides a standard for comparison. Any graph with a fixation probability given by equation (1.6) is fixation equivalent to a Moran process—the population structure it describes has no effect on single mutant fixation probability, although it may influence time to fixation.

An edge weighted graph is said to be isothermal if the sum of all weights leading into a vertex is the same for all vertices. Lieberman *et al.* [1] prove that a graph with stochastic weight matrix *W* is fixation equivalent to a Moran process if and only if it is isothermal; or equivalently, if and only if *W* is doubly stochastic. Broom & Rychtár [7] prove that an undirected graph is isothermal if and only if it is regular.

With more general graphs, however, problems arise in the application of equations (1.3) and (1.4). In the general case, there can be states for which *p*_{m,m+1} is zero so that equation (1.3) cannot be used. It might be thought that averaging over all states having *m* mutants could resolve this problem, but theorem 1.1 shows this is not the case: averaging leads to reproduction of the Moran process values.

### Theorem 1.1

*Let* *v**=(v*_{1}*,…,v*_{N}*) be a population state vector for a graph G having weight matrix W, with v*_{i}*=0 if vertex i is a normal and v*_{i}*=1 if it is a mutant. Let S*_{m} *be the set of all population states containing m mutants. Clearly,* *. Define
*
1.7
*where p*_{m,m±1}(*v**) is the probability of* *v**∈S*_{m} *making a transition to an element of S*_{m±1}*.*

*Then, for all m,
*
1.8

### Proof.

Observing that the *p*_{m,m±1}(** v**) are themselves averages over the possible ways that the state described by

**can gain or lose one mutant, Proof follows from the following two lemmas.**

*v*

### Lemma 1.2

If *π*_{m,m±1}(** v**)=(

*N*−

*m*+

*rm*)

*p*

_{m,m±1}(

**) and is the average of**

*v**π*

_{m,m±1}(

**) over**

*v**S*

_{m}then, for all

*m*, .

### Proof of lemma 1.2.

By definition,
1.9
But *v*^{′}∈*S*_{N−m} can be chosen as the binary compliment of ** v**∈

*S*_{m}by taking . Thus, since the two binary coefficients are equal, equation (1.9) yields 1.10 Making use of and gives 1.11 Write the first term on the right-hand side in equation (1.11) as 1.12 Then, for each

*j*, there will be elements of

*S*

_{m}having

*v*

_{j}=1. Summing over

*S*

_{m}gives equation (1.12) as 1.13 and the proof is completed.

### Lemma 1.3

*Proof follows by observing that*
1.14
*Proof of theorem 1.1 follows directly from lemmas 1.2 and 1.3*.

Fixation from a single mutant is not possible on all graphs. In particular, this is the case if a graph has more than one root. If an *N*-vertex graph has a single root, the fixation probability for a single mutant will be 1/*N* since fixation is possible only from the root vertex. For a graph with *m* roots, there must be at least *m* mutants introduced if fixation is to be possible, in which case, the fixation probability is . If fixation is possible, the smallest possible fixation probability will be 1/*N*, which is also the probability for fixation of a neutral mutation (*r*=1) in a Moran process [2].

## 2. A full state space approach

For an *N*-vertex-directed graph *G* with stochastic edge weight matrix *W*, a population state is the *N*-dimensional binary vector ** v**=(

*v*

_{1},…,

*v*

_{N}), with

*v*

_{k}equal to 0 or 1 as vertex

*k*is occupied, respectively, by a normal or by a mutant. Thus, the full state space is

*V*(

*H*

^{N}), the vertex set of the

*N*-hypercube. As in the Moran birth–death process described in §1, with each iteration of the process, a single vertex is chosen to reproduce and an adjacent vertex is chosen to die and be replaced by a copy of the reproducing vertex. In this case, however, choice of the adjacent vertex

*j*is determined according to the probabilities

*w*

_{ij}, where

*i*is the reproducing vertex. The matrix

*W*defines a state transition matrix

*T*on

*V*(

*H*

^{N}). The matrix

*T*is easily constructed: for each state

**=(**

*v**v*

_{1},…,

*v*

_{N}), define vectors

**(**

*a***),**

*v***(**

*b***) with components 2.1 Thus,**

*v**a*

_{j}is the probability that, for the given state, an edge from a mutant vertex terminates at vertex

*j*and

*b*

_{j}is the probability that an edge from a normal vertex terminates at vertex

*j*. Proof of the following lemma follows from equations (2.1).

### Lemma 2.1 (Binary duality)

*For v∈S_{m}, let v^{′} be the binary compliment of v, defined by . Then, a(v^{′})=b(v) and b(v^{′})=a(v)*.

### Theorem 2.2

*For a birth–death process defined on a graph G with edge weight matrix W, let vectors* ** a**(

*v**) and*

**(**

*b*

*v**) be defined as in equation (2.1), where*

**ranges over the entire state space. Then, for all j, 1≤j≤N, the probabilities of change at a single vertex are the following.***v*—

*The probability of a transition from the state**v**=(v*_{1}*,…,v*_{j−1}*,0,v*_{j+1}*,…,v*_{N}*) to the state (v*_{1}*,…,v*_{j−1}*,1,v*_{j+1}*,…,v*_{N}*) is equal to*2.2—

*The probability of a transition from the state**v**=(v*_{1}*,…,v*_{j−1}*,1,v*_{j+1}*,…,v*_{N}*) to the state (v*_{1}*,…,v*_{j−1}*,0,v*_{j+1}*,…,v*_{N}*) is equal to*2.3—

*The probability that a state**v**remains unchanged is equal to*2.4

Proof of the theorem follows immediately from equation (2.1) and the definition of the birth–death process.

The state transition diagram is an edge weighted directed graph on 2^{N} vertices. The Markov transition matrix *T* derived from theorem 2.2 is row stochastic and has an eigenvalue 1 with eigenvector ** x**=

**, the 2**

*1*^{N}-dimensional vector of all ones.

The introduced mutation goes either to extinction or to fixation, hence the birth–death process has two absorbing states, represented by the *N*-dimensional vectors ** 0** and

**. Labelling of indices in**

*1**T*is relatively free, in order to allow for possible symmetries, but the row

*T*

_{0j}is chosen to correspond to the extinction state

**and the final row**

*0**T*

_{2N−1,j}is chosen to correspond to the fixation state

**.**

*1*Since is the probability of a *k*-step transition from state *i* to state *j*, the matrix consists of initial and final non-zero columns with all other entries equal to zero. Furthermore, , , *T**** x**=

**, and the solution of (**

*x**I*−

*T*)

**=0 is given by 2.5 where**

*x**u*and

*v*are free parameters. With this definition,

*η*

_{i}is the probability that state

*i*goes to extinction and

*μ*

_{i}is the probability that it goes to fixation. Since the general interest is in fixation probabilities, the usual assignment for

*u*and

*v*is

*u*=0,

*v*=1. The general form in equation (2.5) is included in order to avoid exclusion of the vector

**, which is important for defining the determinacy of a graph in equation (2.15).**

*η*The probability of fixation from a single mutant vertex is
2.6
Computing the solution of (*I*−*T*)** x**=0 will, in general, involve solving 2

^{N}−2 linear equations in an equal number of unknowns. This number can be substantially reduced, however, if the graph

*G*has a large automorphism group, allowing partition of states into equivalence classes [7,12].

For a Moran process, for example, the state equivalence classes are just the sets *S*_{m} for 0≤*m*≤*N* and the state space is isomorphic to {0,1,…,*N*}. For any state with *m* mutants, let *x*_{m} be the probability that a member of *S*_{m} goes to fixation. For the Moran process with self-replacement, *w*_{ij}=1/*N* for all *i*, *j*. Hence, ** a**(

**)=(**

*v**m*/

*n*)

**,**

*1***(**

*b***)=((**

*v**N*−

*m*)/

*N*)

**and the probabilities in equations (2.2)–(2.4) are 2.7 To derive an equation for**

*1**x*

_{m}, note that there are

*N*–

*m*zeros that can become ones, and

*m*ones that can become zeros, hence, which reduces to 2.8 with

*x*

_{0}=

*u*,

*x*

_{N}=

*v*as boundary conditions. These equations can be solved recursively, yielding the following theorem.

### Theorem 2.3

*For the Moran process, the solution of equation (2.8) is
*
2.9

Thus, for each *μ*_{i} such that the corresponding state is in *S*_{m}, the fixation probability is
2.10
and the overall single vertex fixation probability for *S*_{1} is *Nμ*_{1}/*N*, or
2.11
which is equivalent to equation (1.7).

For the general case, with ** v**=(

*v*

_{1},…,

*v*

_{N}), , define

*s*

_{v}as the denary form of the binary number (

*v*

_{1},…,

*v*

_{N}): . Then, for

**∈**

*v**V*(

*H*

^{N}), the system of equations for

**is summarized in the master equation 2.12 The vectors**

*x***and**

*η***span the null space of**

*μ**I*–

*T*and the

*determinacy*

*δ*(

*G*) of the population graph is defined as 2.13 Clearly, 0≤

*δ*(

*G*)≤1. This quantity measures the degree to which extinction or fixation is determined, starting from a randomly chosen initial state. If

*δ*=1 then, for all

*i*,

*μ*

_{i}is either 0 or 1 and any randomly chosen state will always go either to extinction or to fixation. This is the case, for example, for any single rooted graph—if the root vertex is not a mutant, any other set of mutants eventually becomes extinct, while if the root vertex is a mutant, the mutation eventually goes to fixation. Since exactly half of the states will have a mutant at the root, the average fixation probability over all states for such a graph will be . If

*δ*(

*G*)=0, then

**=**

*η**α*

**and, since**

*μ**η*

_{i}+

*μ*

_{i}=1, all population states have the same probability 1/(1+

*α*) of fixation.

Here, *δ*(*G*) describes an intrinsic property of the graph (*G*, *W*), and it gives an indication of the spread of fixation probabilities across the state space. From equations (2.9) and (2.10), for example, the sets of fixation probabilities for the classes *S*_{m} in the Moran process have cardinality , hence the distribution of these probabilities over the state space follows the binomial distribution. The difference in determinacy between a complete graph and a star graph is illustrated in §4.

## 3. Suppressing selection

If *ρ*_{M} is the fixation probability for a complete graph, representing a homogeneous population, then any graph *G* for which
3.1
suppresses selection in favour of drift. Graphs that suppress selection have biological interest when considering populations of cells in which it is desirable to suppress unfavourable mutants [8,11,13].

Nowak [11] offers a procedure for construction of graphs satisfying equation (3.1).

Take *G*=*G*_{1}∪*G*_{2}, where *G*_{1} is a complete graph and *G*_{2} is an arbitrary graph with no edge from *G*_{2} terminating in *G*_{1} while all vertices of *G*_{2} are accessible from *G*_{1}. Nowak gives the fixation probability of such a graph as^{1}
3.2
In general, however, this is an approximation based on the assumption of equal weights in *G*_{1} and equal access to *G*_{2} from all vertices of *G*_{1}. This is shown by consideration of the simple example illustrated in figure 1.

If *p*=0, the graph is a line graph, while if *p*=1, it is a two cycle with a third isolated vertex. Equation (2.12) yields the set of equations
3.3
having solution ** x**=

*u*

**+**

*η**v*

**, where 3.4 The single vertex fixation probability is**

*μ**ρ*

_{G}=(

*μ*

_{1}+

*μ*

_{2}+

*μ*

_{4})/3. This is 3.5 Figure 2

*a*shows the graph of

*ρ*

_{G}, the single vertex fixation probability for this graph, for varying values of

*p*, as well as for the approximation of equation (3.2), which provides an upper bound. For

*p*>0.7, this approximation formula and the exact formula of equation (3.5) are indistinguishable. For smaller values of

*p*, however, there are significant differences (for

*p*=0, the value is always one-third for the line graph). Figure 2

*b*shows the determinacy for this graph as a function of

*r*and

*p*, and figure 2

*c*compares this determinacy to that of a Moran process on three vertices for varying values of

*p*.

While the determinacy of the graph in figure 1 is larger than that of a complete graph (Moran) for lower values of *r*, this is reversed for large values. So long as *p*≠0, all curves in figure 2*c* approach one as *r* approaches infinity and are equal to one at *r*=0.

Suppose that for a graph *G*=*G*_{1}∪*G*_{2}, *G*_{1} is fixation equivalent to a Moran process, while no edge from *G*_{2} terminates in *G*_{1}. If the birth–death process reaches fixation in *G*_{1}, then *G*_{1} acts as a root for *G*_{2} and the process will fixate in *G*. If the vertex chosen for reproduction at any iteration of the birth–death process is in *G*_{2}, this can have no effect on *G*_{1}. Only iterations in which the reproducing vertex is in *G*_{1} can contribute to fixation. Furthermore, if the vertex chosen for death is in *G*_{2}, this can have no effect on the probability of fixation of the process in *G*_{1}, although it will delay this process. Thus, the birth–death process is a process on *G*_{1} that, due to ‘leakage’ into *G*_{2}, operates on a slower time scale, but otherwise remains fixation equivalent to a Moran process, together with a process on *G*_{2} in which *G*_{2} ‘fills up’.

Furthermore, the probability of fixation in *G*_{1} is just the fixation probability for *G*_{1} without *G*_{2}, multiplied by the probability that the initial mutant vertex is in *G*_{1} and this is |*G*_{1}|/|*G*|. Thus, the Nowak construction produces a graph with fixation probability given by equation (3.2), subject to the conditions given in theorem 3.1.

### Theorem 3.1

*Let G=G*_{1}*∪G*_{2}*, where G*_{1} *is fixation equivalent to the Moran process and G*_{2} *is a graph with no edge from G*_{2} *terminating in G*_{1}*, while all vertices of G*_{2} *are accessible from G*_{1}*. Furthermore, assume that for all i, j,
*
3.6
*Then, ρ*_{G} *is given exactly by equation (3.2).*

Necessity of the condition in equation (3.6) is illustrated by the graph in figure 3, which satisfies all conditions of theorem 3.1 with the exception of equation (3.6), which holds only if *p*=*q*.

The single vertex fixation probability for this graph is
3.7
which becomes equation (3.2) with *N*=3 only for *q*=*p*.

## 4. Enhancement of selection

If an edge weighted graph (*G*,*W*) is such that *ρ*_{G}>*ρ*_{M}, then selection is enhanced relative to a complete graph. Several such graphs are considered in [1]. Star graphs, in particular, have been extensively studied [1,7]. Lieberman *et al.* [1] prove that for large *N*=*n*+1, with *n* being the number of leafs, the single vertex fixation probability for a star graph is approximately given by a Moran process with selection *r*^{2},
4.1
Broom & Rychtár [7] compute the exact fixation probability as
4.2
Rather than immediately consider star graphs, however, this section begins with an analysis of some simple cases of a very general class of graphs.

*Definitions*

Let {

*G*_{s}|0≤*s*≤*k*} be a family of*k*+ 1 directed graphs with |*G*_{s}|=*n*_{s}and with each*G*_{s}having a strictly sub-stochastic weight matrix*W*_{s}. With , let {*M*_{s+1,s}} be a set of*n*_{s+1}×*n*_{s}matrices, with*s*+1 evaluated mod(*k*+1), such that the*N*×*N*matrix*W*with block form 4.3 is row stochastic. The graph*G*_{s}with weighted edge matrix*W*will be called a circular flow. This is a generalization of the layered networks defined in [6].If (

*G*,*W*) is a circular flow such that*n*_{s−1}<*n*_{s}for 1≤*s*≤*k*, then (*G*,*W*) is a funnel.A circular flow is simple and homogeneous if (i)

*W*_{s}=0 for all*s*and (ii)*M*_{s+1,s}=(1/*n*_{s})*J*_{s+1,s}, where*J*_{s+1,s}consists entirely of ones. A layered network is a simple homogeneous circular flow.

Analytic treatment of circular flows is difficult in general, and further attention is restricted to simple, homogeneous circular flows. With this restriction, all states with *m*_{s} mutants at level *s* are equivalent and the full state space vector can be partitioned into blocks of *n*_{s} elements. The resulting set of equivalence classes is represented by a vector ** m**=(

*m*

_{0},

*m*

_{1},…,

*m*

_{k}), where

*m*

_{s}indicates the number of mutants located at level

*s*. At each level

*s*, with the number of mutants at all other levels fixed, there will be

*n*

_{s}+1 distinct equivalence classes of states.

Suppose *m*_{s}=0 for 0≤*s*≤*k*−1. Then, there are *n*_{k+1} equivalence classes corresponding to 0≤*m*_{k}≤*n*_{k}. Now, allow *m*_{k−1} to be non-zero as well. This gives *n*_{k−1} possible classes since *m*_{k−1}=0 has already been included in the first case. Hence, there are *n*_{k−1}(*n*_{k}+1) possible equivalence classes satisfying *m*_{s}=0, 0≤*s*≤*k*−2. Continuing in this way produces a telescoping sum *n*_{k}+1+*n*_{k−1}(*n*_{k}+1)+*n*_{k−2}(*n*_{k−1}+1)(*n*_{k}+1)+…, which collapses to yield an upper bound for the total number of equivalence classes for a simple, homogeneous circular flow, including extinction and fixation,
4.4
For a simple homogeneous circular flow, application of equations (2.1) for the reduced vector ** m** yields
4.5
hence
4.6
where the indices

*s*+1 in the summation are evaluated mod(

*k*+1). Theorem 2.2 and equations (4.6) now yield the transition diagram where . Finally, given a class label (

*m*

_{0},…,

*m*

_{s−1},

*m*

_{s},

*m*

_{s+1},…,

*m*

_{k}), define 4.7 Using the notation , equation (2.12) becomes 4.8 where summation indices are taken mod(

*k*+1).

The single vertex fixation probability is then
4.9
If the direction of flow is reversed in a funnel, with edge weights adjusted accordingly, the graph is called a *cascade*. Figure 4 shows an *N*=6 graph that is a funnel or cascade depending on the direction of flow, and an *N*=5 bipartite graph.

Figure 5*a*,*b* shows plots of the fixation probability minus the corresponding Moran fixation probability for these graphs.

The two *N*=6 graphs of figure 4 enhance selection for only a limited range of fitness values. For the funnel, the fitness range for enhanced selection is 1<*r*<5.369515496 and for the cascade, it is 1<*r*<2.030404551. A similar result shows up for the *N*=7 funnel with (*n*_{0},*n*_{1},*n*_{2})=(1,2,4), for which *ρ*_{F}>*ρ*_{M} only so long as 1<*r*<11.556124. The bipartite graph of figure 5*b* is similar to a star graph and *ρ*_{F}>*ρ*_{M} for all *r*>1.

Equation (4.8) also applies to star graphs since a star with *n* leafs is just a two-level funnel graph with *n*_{0}=1 and *n*_{1}=*n*. The equivalence classes for the population are labelled (0,1),(0,2),…,(0,*n*), (1,0),(1,1),…,(1,*n*−1) and the multiplicity of class (*m*_{0},*k*) is . For a star graph, equation (4.8) takes on a particularly simple form, consisting of a set of *n* equations for *m*_{0}=0 and *n* equations for *m*_{0}=1,
4.10
The single vertex fixation probability is
4.11
where the first of the *m*_{0}=0 and *m*_{0}=1 equations have been used to solve for *x*_{n+1} in terms of *x*_{1}. The boundary conditions on equations (4.10) are *x*_{0}=0, *x*_{2n+1}=1. These equations can be solved recursively for *x*_{1} and *ρ*_{S} to obtain
4.12
Equations (4.10) are equivalent to eqns (5.1) and (5.2) in [7], and the single vertex fixation probability of equation (4.12) can be shown to be the same as the value computed in that paper, given here in equation (4.2).

Figure 6 shows a graph of the single vertex probabilities for 3≤*n*≤7, 0≤*r*≤10.

Figure 7 shows a typical graph for the difference between star and Moran fixation probabilities, showing that for *r*>1, the star enhances selection. Comparison to the graph of figure 5*b* suggests that all bipartite graphs may behave in a similar manner.

Figure 8*a* shows a plot of the determinacy of a typical star graph (in this case, *n*=3) compared with the corresponding determinacy for a complete graph on the same number of vertices. The star graph enhances selection and is also more determinate than a Moran process. One way to understand this is to consider the variance of fixation probabilities over the entire state space. Figure 8*b* shows this variance, computed for the *N*=4 complete graph and the *n*=3 star graph. The variance of the star graph is greater, indicating that the star graph has more excess or deficit about the average fixation probability than the *N*=4 complete graph. For the *n*=3 star with *r*>1 the single, double and triple vertex fixation probabilities are all greater than the equivalent probabilities for the Moran process, and less than these for *r*<1, as shown in figure 8*c*.

Two other forms of circular flow are cycles and constricted cycles.

*Definition*

A simple, homogeneous circular flow for which *n*_{i}=*n*_{j}=*n* for all *i*, *j*mod(*k*) will be called a *cycle* of width *n* and length *k*. If *n*_{i}=*n*_{j} for all *i*, *j*≠*s* and *n*_{s}<*n*_{i} (*i*≠*s*), then the graph is a *constricted cycle*.

Since the sum of all in degree weights for each vertex in a cycle is equal to one, the graph is isothermal, hence every cycle is fixation equivalent to a Moran process.

As a final example, consider the graph of figure 9, a cycle with a constriction. Figure 10 shows the difference between this fixation probability and the probability for a Moran process on five vertices.

The fixation probability for the graph of figure 9 is greater than that of a Moran process for 1<*r*<2.267235117. This suggests that the introduction of funnel or star-like constrictions in cycles of width *n* leads to enhancement of selection only for particular ranges of fitness values.

## 5. Discussion

Evolutionary dynamics is a broad and rapidly developing field, subsuming a wide variety of topics and directions of research. A relatively recent development has been the use of edge weighted graphs to model interaction patterns in heterogeneous populations. While early studies suggested that at least some common population structures have no influence on fixation probability, it is now clear that there are population structures that can exert a strong influence, either suppressing or enhancing the effects of selection relative to drift when compared with a homogeneous population. Furthermore, there are sound biological reasons to explore these population structures.

Recent work, for example, suggests that suppression of selection is particularly significant as a defence against rapidly reproducing deleterious mutations, as in cancers [8,13], and may have value in attempts to control the spread of infectious diseases [12]. Structures that enhance selection may prove useful for models of sensory neural networks, in which it is important to quickly identify a stimulus and produce an appropriate response.

A main point of interest arising in the cases studied in this article is that funnels, cascades and cycles with constriction provide enhancement of selection only for limited ranges of the fitness parameter. This places fitness (or, equivalently, any measure of constraint matching) in the role of control parameter. In neural networks, where interactions can be both excitatory and inhibitory, this suggests that inhibition and disinhibition of particular edges or vertices, or changes in the edge weights, can act to control the degree of enhancement or suppression of selection.

In order to begin addressing such possibilities, however, further work on networks with heterogeneous weights (such as shown in the graphs of figures 1 and 3), as well as networks with time-dependent or adjustable weights is required. The major difficulty anticipated in such studies is computational complexity. As indicated in §2, computation of fixation probabilities for a general population of *N* individuals involves solution of the 2^{N} – 2 equations arising from equation (2.12). Obtaining compact analytic expressions for fixation probabilities will require discovery of general recursive formulae such as that for star graphs derived in [7], given here in equations (4.2) and (4.12).

Other directions for continued research are the study of other simple graphs, graphs with non-uniform edge weight distributions, development of approximation methods for analysis of more complex graphs, and application to problems in evolutionary biology, neurophysiology and sociology. Two questions of applied interest are the following: (i) Given a graph *G* with edge weight matrix *W*, how can the probability of fixation be minimized or maximized by removal of a single, or small number of edges? More generally, how can the elements of *W* be modified to minimize or maximize this probability? (ii) Given a graph (*G*, *W*) with *N* vertices, and a number of mutants *m*≪*N*, what distribution of mutants on *G* give the greatest probability of fixation?

## Acknowledgements

Discussions on graph theory with Gary MacGillivray of the University of Victoria were seminal in developing ideas used in this article. An initial version of the article was presented in the Mathematical Biology Seminar at the University of Victoria, 27 September 2011. Detailed critique of the original manuscript by two anonymous referees, together with referral to reference [12] by a referee, is gratefully acknowledged. Supported by NSERC Discovery grant no. OGP0024871.

## Footnotes

- Received November 8, 2012.
- Accepted February 1, 2013.

- © 2013 The Author(s) Published by the Royal Society. All rights reserved.