## Abstract

The problem of finding birth–death fixation probabilities for configurations of normal and mutants on an *N*-vertex graph is formulated in terms of a Markov process on the 2^{N}-dimensional state space of possible configurations. Upper and lower bounds on the fixation probability after any given number of iterations of the birth–death process are derived in terms of the transition matrix of this process. Consideration is then specialized to a family of graphs called circular flows, and we present a summation formula for the complete bipartite graph, giving the fixation probability for an arbitrary configuration of mutants in terms of a weighted sum of the single-vertex fixation probabilities. This also yields a closed-form solution for the fixation probability of bipartite graphs. Three entropy measures are introduced, providing information about graph structure. Finally, a number of examples are presented, illustrating cases of graphs that enhance or suppress fixation probability for fitness *r*>1 as well as graphs that enhance fixation probability for only a limited range of fitness. Results are compared with recent results reported in the literature, where a positive correlation is observed between vertex degree variance and fixation probability for undirected graphs. We show a similar correlation for directed graphs, with correlation not directly to fixation probability but to the difference between fixation probability for a given graph and a complete graph.

## 1. Introduction

The influence of structure on the spread of information in a population has become a topic of major interest. Populations are represented by directed or undirected graphs with internal population structure coded into an edge-weight matrix that specifies interaction probabilities between population members. This model applies equally to the spread of rumours and innovations, to the spread of computer viruses and to the spread of genetic mutations. While the spread of a mutation in a homogeneous population has been studied for over 50 years, the effect of population structure received far less attention until the work of Lieberman *et al.* [1] highlighted its importance. Since then, however, evolutionary dynamics on directed and undirected graphs has become a focus of research attention [2–6]. Much of this effort has been directed to the study of fixation probabilities for single mutants randomly introduced into an otherwise genetically homogeneous population. This work shows that population structure can enhance or suppress selection relative to drift [7–10] and that whether selective effects are enhanced or suppressed may depend on both fitness and initial placement [11,12].

The modelling paradigm uses a graph with each vertex representing an individual population placeholder, occupied at any given moment by either a normal or mutant individual. A birth–death Moran process [13] operates on the population in discrete time. At every iteration, an individual is chosen at random to reproduce, and a second individual, located at a neighbouring vertex, is chosen to die and be replaced by a clonal copy of the reproducing individual. Normal population members have fitness 1 and mutants have fitness *r*. Choice of the reproducing individual is biased by fitness. This, and other update processes, have been extended to studies of the spread of information, innovation, rumours, diseases and computer viruses [14–18].

For a homogeneous population of size *N* represented by the complete graph *K*_{N}, the single-vertex fixation probability is given by
1.1In general, however, calculation of the birth–death fixation probability for a graph with *N* vertices involves solution of 2^{N}−2 linear equations in an equivalent number of unknowns [11,19]; hence, most studies seek asymptotic approximations [20–22], employ methods of ‘lumping’ vertices into equivalence classes [23] or rely on numerical computations [12,20,24]. Other than equation (1.1), few analytic results are known: Broom & Rychtář [19] obtained partial results for path graphs and found a closed-form solution for the single-vertex fixation probability of star graphs; Zhang *et al.* [25] computed *k*-vertex fixation probabilities for star graphs; and Voorhees [26] gave a solution for the single-vertex fixation probability of the complete bipartite graph *K*_{s,n}.

In addition to computation of fixation probabilities, various other questions have been seriously investigated. Two of particular interest are the following. (i) What initial vertex or set of vertices leads to the greatest fixation probability? (ii) Given an observed distribution of mutants, what is the most probably starting vertex producing this distribution?

In this paper, we compute birth–death fixation probabilities for a graph with *N* vertices using a Markov process defined on the state space of 2^{N} binary vectors having entries of 0 or 1 as the corresponding vertex is occupied by a normal or mutant population member. Results following from the definition of the transition matrix of this process are given, and a class of directed graphs called circular flows is defined. Summation formulae for the *k*-vertex fixation probability in terms of the single-vertex fixation probabilities are derived for complete graphs and complete bipartite graphs. Three entropy measures are introduced, and an alternate proof that a graph is fixation equivalent to a complete graph if and only if all single-vertex fixation probabilities are equal is given. Finally, a number of examples are considered. In particular, we note relations between vertex temperature, temperature variance and fixation probability similar to those found in the study of Broom *et al*. [12].

## 2. Birth–death evolutionary dynamics on graphs

Let *G*=(*V*,*E*) be a graph with finite vertex set *V* , |*V* |=*N*, and edge set *E*. *G* may be directed or undirected, and the possibility of self-loops at vertices is allowed. A population state is described by a binary vector ** v**=(

*v*

_{1},…,

*v*

_{N}), where

*v*

_{i}is zero or one as vertex

*i*is occupied by a normal or mutant population member. Thus, the population state space is the vertex set

*V*(

*H*

^{N}) of the

*N*-hypercube. Population structure is represented by an edge-weight matrix

*W*=(

*w*

_{ij}) with

*w*

_{ij}equal to the probability that

*if*vertex

*i*is chosen for reproduction,

*then*vertex

*j*will be chosen for death. The matrix

*W*is row stochastic.

In a birth–death process, a single vertex is selected at random for reproduction at each iterate of the process. If there are *m* mutants with fitness *r* and *N*−*m* population members with fitness 1, the probability of selecting the individual at vertex *i* for reproduction is biased by fitness, as indicated in equation (2.1),
2.1In the formulation used in [1,12,19], if *C* is the subset of vertices in *V* occupied by mutants, then the probability *P*_{C} that this set goes to fixation is
2.2with boundary conditions *P*_{ϕ}=0, *P*_{V}=1.

Broom & Rychtář [19] showed that the solution of this system of equations is unique. In [11], a different but equivalent approach is taken. Two vectors ** a**(

**) and**

*v***(**

*b***) are defined by**

*v***(**

*a***)=**

*v***⋅**

*v**W*and

**(**

*b***)=**

*v***′⋅**

*v**W*, where

*v*′

_{i}=1−

*v*

_{i}. Thus, for a given state vector

**,**

*v**a*

_{j}(

**) is the sum of all probabilities that an edge originating at a vertex occupied by a mutant terminates at vertex**

*v**j*and

*b*

_{j}(

**) is the sum of all probabilities that an edge originating at a vertex occupied by a non-mutant terminates at vertex**

*v**j*. In the language of [1], the sum

*a*

_{j}(

**)+**

*v**b*

_{j}(

**)=**

*v**t*

_{j}is the ‘temperature’ of vertex

*j*.

The following theorem from [11] allows construction of the transition matrix for the Markov process on the population state space.

### Theorem 2.1 ([11])

*Let a birth–death process be defined on a graph G with edge-weight matrix W. Then for all j*, 1≤*j*≤*N and for all states* *v**with* *the following hold*.

*The probability of a transition from the state*(*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 given by*2.3*The probability of transition from the state (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 given by*2.4*The probability that**v**remains unchanged is*2.5

Based on this theorem, a state transition matrix *T*=(*T*_{uv}) is defined on *V* (*H*^{N}). As a notational point, to avoid confusion between the *N* vertices of the graphs *G* and the 2^{N} elements of the state space, entities defined on the state space will be indexed with letters chosen from the latter part of the alphabet (e.g. *u*,*v*), while entities referring to vertices of the graph will be indexed with the letters *i*, *j*. State vectors ** u**,

**can be viewed as binary numbers and the corresponding indices**

*v**u*and

*v*are the corresponding denary values.

Since any set of mutants less than the full state space will go either to extinction or fixation, the Markov process with transition matrix *T* has only two steady states: extinction, represented by the vector **0** of all zeros; and, fixation, represented by the vector **1** of all ones. Writing and taking *x*_{v} as the probability that the corresponding state ** v** goes to fixation, the equation (

*I*−

*T*)⋅

**=0 for the Markov steady states, with**

*x**x*

_{0}=0 and

*x*

_{2N−1}=1, yields the system of master equations [11] 2.6A program has been implemented in Maple 15 that takes as input an edge-weight matrix

*W*and generates the solutions to equation (2.6) as output.

^{1}

## 3. The state transition matrix

Several results can be obtained by considering the state transition matrix *T*.

### Theorem 3.1

*Let G be a directed graph with weighted adjacency matrix W and associated state transition matrix T. Then, Det(T)=0 if and only if G contains no loops.*

### Proof.

Proof follows by demonstrating that if there are no loops in a graph (i.e. the diagonal elements of *W* are zero), then elementary row operations can be used to produce a row of zeros in the matrix *T* and this cannot work if there are non-zero diagonal elements in *W*. □

Given a state ** u**=(

*u*

_{1},

*u*

_{2},…,

*u*

_{N}), this defines the binary number

*u*

_{1}

*u*

_{2}…

*u*

_{N}with corresponding denary form given by . The 2

^{N}population states can be listed in numerical order, starting with 0, to define a 2

^{N}×

*N*matrix

*S*with

*S*

_{ui}=

*u*

_{i}. As a direct consequence of the definitions of

*T*and

*S*, we have the following.

### Lemma 3.1

*The probability that vertex i will contain a mutant after k iterations, starting from the initial state* ** u**,

*is given by*[

*T*

^{k}

*S*]

_{ui}.

### Theorem 3.2

*Given an initial state* *u**, the probability of fixation is* *for all i.*

### Proof.

Since the Markov process with transition matrix *T* converges to either extinction or fixation, for large *k*, [*T*^{k}]_{uv}∼0 unless ** v** is

**0**or

**1**, and from [11] 3.1where □

Based on this theorem, one method for computing the fixation probability of a state ** u** is to compute . This also provides a determination of upper and lower bounds for the fixation probability of any state

**.**

*u*

### Theorem 3.3

*Given an initial state* *u**and a number of birth–death iterations k,
*3.2*(Lemma 3.1 and theorem 3.3 are reported in *[27]*.)*

To estimate the fixation probability of a state ** u** from equation (3.2), set

*Δ*

_{u}(

*k*)=1−[

*T*

^{k}]

_{u0}−[

*T*

^{k}]

_{u1}and write the linear interpolation estimate for the fixation probability as 3.3This makes it possible to at least tentatively answer the following question: given that the observed state after

*k*iterations is

**, what are the most probably initial states to produce this observed configuration? The answer is obtained by finding One problem arising in this is that for large**

*v**k*, all entries of

*T*

^{k}other than in the first and final columns will be close to zero, leading to the danger of round-off error.

This problem can be addressed by dividing each entry in *T*^{k} by the appropriate column sum. Let and *D*(*k*)=diag[*D*(** v**,

*k*)]. Then, the column entries in

*T*

^{k}

*D*

^{−1}(

*k*) will be relative rather than absolute probabilities, and these can be computed from

*T*

^{k−1}

*D*

^{−1}(

*k*−1) as

*T*

^{k}

*D*

^{−1}(

*k*)=[

*TT*

^{k−1}

*D*

^{−1}(

*k*−1)][

*D*(

*k*)

*D*

^{−1}(

*k*−1)], where

*D*(

*k*)

*D*

^{−1}(

*k*−1) is just the diagonal matrix formed from the column sums of

*TT*

^{k−1}

*D*

^{−1}(

*k*−1).

## 4. Circular flows

In this section, we define circular flows as a class containing many graphs that have been previously studied in the literature, including cycles [3], stars [1,11,19], bipartite graphs [25], funnels [1,3,11], cascades [11] and layered networks [28].

### Definition 4.1

*Let* {*G*_{s}=(*V* _{s},*E*_{s})|0≤*s*≤*k*} *be a family of k*+1 *graphs with* |*V* _{s}|=*n*_{s} *and with each* *G*_{s} *having a strictly sub-stochastic edge-weight matrix* *W*_{s}. *Let* *and let* {*M*_{s+1,s}} *be a set of matrices with* *M*_{s+1,s} *of size* *n*_{s+1}×*n*_{s}, *where* *s*+1 *is evaluated* *mod*(*k*+1), *such that the* *N*×*N* *matrix* *W* *with the form*
4.1*is row stochastic. The graph* *with edge-weight matrix* *W* *is called a circular flow*. *G* *is homogeneous if*
4.2*where* 0≤*p*≤1, *I is the identity matrix*, *J*(*s*,*t*) *is the* *s*×*t* *matrix of all ones and* *c* *takes values in* {0,1}. *If* *p*=1, *G* *is simple. The two-level simple homogeneous circular flows are just the complete bipartite graph* *K*_{s,n} (*without loss of generality*, *s*≤*n*).

Circular flows are labelled by the (*k*+1)-tuple (*n*_{0},*n*_{1},…,*n*_{k}). If they are homogeneous, they are characterized in terms of the automorphism group Aut(*G*) consisting of all permutations on *N* objects with permutation matrices having the block diagonal form
4.3where *P*_{i} is an arbitrary *n*_{i}×*n*_{i} permutation matrix.

With one exception, we consider circular flows that are both simple and homogeneous. While equation (2.6) in general consists of a set of 2^{N}−2 equations, this number is significantly reduced for a homogeneous circular flow by considering equivalence classes of the orbits of Aut(*G*). Homogeneity implies that any *m*_{s}<*n*_{s} mutants at level *s* will have the same fixation probability as any other set of *m*_{s} mutants at that level. Hence, a reduced state space is defined with states denoted by listing the number of mutants at each level: ** m**=(

*m*

_{0},

*m*

_{1},…,

*m*

_{k}), 0≤

*m*

_{i}≤

*n*

_{i}. The total number of state equivalence classes is .

In order to index fixation probabilities for each equivalence class, define
4.4with the notation . With this reduction, equation (2.6) becomes [11]
4.5and the single-vertex fixation probability is
4.6with all summation indices taken mod(*k*+1) (*ι*(*s*) is the index in the sum of (4.6)).

Note that the circular flow (*n*_{0},…,*n*_{k}) is not unique. For example, (1,1,2), (1,2,1) and (2,1,1) are indistinguishable. Given a string (*n*_{0},…,*n*_{k}), let *σ* be the shift operator. Then, any string *σ*^{s}(*n*_{0},…,*n*_{k}) with 1≤*s*≤*k* labels the same circular flow. Thus, (*n*_{0},…,*n*_{k}) is the generic label for the shift equivalence class {*σ*^{s}(*n*_{0},…,*n*_{k})|0≤*s*≤*k*}.

## 5. Summation formulae

One point of interest is the relation between single-vertex fixation probabilities and the fixation probabilities for configurations in which more than one vertex is occupied by a mutant. All fixation probabilities approach one for large *r* values; hence, the relation between *k*-vertex and single-vertex fixation probabilities cannot be additive. For *r*=1, however, the following hold.

### Theorem 5.1 ([2,4])

*Let* *u**,* *v**be configurations such that* *u**⋅**v**=0 (i.e. the distribution of mutants in these two states is non-overlapping) with ρ*_{w} *the fixation probability for the configuration represented by the vector* *w**. If r=1, then ρ*_{u+v}*= ρ*_{u}*+ρ*_{v}*.*

While no general result for *r*≠1 is known, it is easy to determine the relation for complete graphs and graphs that are fixation equivalent to a complete graph.

### Theorem 5.2

*Let ρ*_{M}*(k,N) be the k-vertex fixation probability for the Moran process on the complete graph K*_{N} *or on a graph fixation equivalent to this graph. Then,
*5.1

### Proof.

This follows immediately from equation (1.1), the solution 5.2of equation (2.6) for the complete graph [11] and the identity □

### Remark

One way of understanding equation (5.1) is to begin with a set of *k* mutant vertices on a complete graph, pick one mutant vertex and then exclude it, keeping its single-vertex fixation probability of *ρ*_{M}(1,*N*). The remaining *k*−1 mutants reside on a graph with *N*−1 vertices. Pick another mutant vertex and exclude it, adding its fixation probability of *ρ*_{M}(1,*N*−1), multiplied by the factor (*r*^{N−2−1})/(*r*^{N−1}) to adjust denominators. Continue this process until all mutant vertices have been excluded.

Theorem 5.2 can be extended to the case of the complete bipartite graphs *K*_{s,n}.

### Theorem 5.3

*Let K*_{s,n} *be the complete bipartite graph with 1≤s<n and let x*_{k,m} *be the fixation probability for the state (k,m). Then,
*5.3

### Remark

For *s*=*n*, this reduces to the case of theorem 5.2.

### Proof.

For the *K*_{s,n} graph, equations (5.3) become
5.4with boundary conditions *x*_{0,0}=0, *x*_{s,n}=1. □

Substitution from equations (5.3) into (5.4) reduces these equations to identities, the exceptions being (*sr*+*n*)*x*_{s,n−1}−*nx*_{s−1,n−1}−*sr*=0 and (*nr*+*s*)*x*_{s−1,n}−*nx*_{s−1,n−1}−*nr*=0 that, using equation (6.4), reduce to equations that can be solved for *x*_{0,1}, yielding
5.5Since the solution of equation (5.4) is unique [19], the result follows.

Use of equations (4.6), (5.3) and (5.5) yields the formula given in [26] for the fixation probability of a complete bipartite graph.

**Corollary to theorem 5.3.** The single-vertex fixation probability for the complete bipartite graph *K*_{s,n} is
5.6

## 6. Information measures

Useful measures of the structure of a graph *G* are found in entropy/information functions that can be defined. A number of such functions have been studied in the literature [29,30]. The procedure is to construct a probability distribution associated with the graph, and use this distribution to define an entropy function (usually the Shannon entropy). The distribution used can be constructed from intrinsic features of the graph, or from the imposition of an external probability function (a brief review of entropy functions on graphs is found in [30]).

One of the simplest intrinsic functions is the automorphism group entropy, which gives a measure of the complexity of a graph in terms of vertex similarity. For a graph *G*, this is defined by the orbit equivalence classes of Aut(*G*): if *n*_{s} is the number of vertices in the *s*th equivalence class of Aut(*G*), the automorphism entropy of the graph is
6.1where *N* is the total number of vertices. For the complete graph *K*_{N}, Aut(*K*_{N}) is the full permutation group, there is a single equivalence class and *I*_{a}(*G*)=0. This will also be the case for all graphs that are fixation equivalent to a Moran process. The maximum value for *I*_{a}(*G*) occurs when Aut(*G*)={*I*}, in which case .

Other entropy measures can be defined that provide information on aspects of graph structure. If is any map assigning a probability to each vertex of *G*, then defines an entropy measure on *G*. One useful measure is constructed using the probability of extinction in a single iteration for a mutant introduced into an otherwise homogeneous normal population. If the mutant is located at vertex *j*, assuming no loops in the graph, this is given for a birth–death process by
6.2where *t*_{j} is the ‘temperature’ of vertex *j*, defined by [1,3].

The associated entropy is
6.3Since *W* is row stochastic, the sum of temperatures *t*_{j} equals *N* and
6.4indicating that *I*_{t} provides a measure of the temperature variation, or equivalently, the degree (or in degree) structure of the graph.

If *N* is considered as an ‘effective volume’, then *t*_{j}/*N* is analogous to the pressure exerted on vertex *j* by the population distribution (described by specifying a state ** u**) and the terms

*a*

_{j}(

**)/**

*u**N*,

*b*

_{j}(

**)/**

*u**N*are analogous to partial pressures exerted on the population member at vertex

*j*by the mutant and normal sub-populations, respectively. This concept shows up in population ecology, for example, with the concept of

*propagule pressure*used in studies of the spread of invasive species in an ecosystem [31].

Both *I*_{a} and *I*_{t} are independent of the fitness *r* and the fixation probabilities. Equation (6.3) for a simple homogeneous circular flow *G*=(*n*_{0},…,*n*_{k}) can be written as
6.5A simple calculation yields the next theorem.

### Theorem 6.1

*Let G be a simple homogeneous circular flow defined by (n*_{0}*,…,n*_{k}*). Then,
*6.6*Hence,
*6.7*While I*_{a} *relates to graph structure as determined by the graph automorphism group, I*_{t} *is connected to the in degree of each vertex; hence, their difference describes the graph connectivity structure. For a general graph, this difference is
*6.8*Another useful measure is the entropy associated with single-vertex fixation probabilities,
*6.9*where ρ*_{i} *is the single-vertex fixation probability for a mutant introduced at vertex i. The sum in the denominator is just* *, where* *is the average single-vertex fixation probability, that is, the usual fixation probability assigned to a graph. Broom et al. *[12] *show that this average fixation probability is positively correlated with the variance of the vertex degree for undirected graphs with up to eight vertices, and this carries over to the variance of in degree for directed graphs, as will be seen in §7. Since the temperature of a vertex depends on the vertex in degree, this correlation occurs for temperature variance as well.*

### Theorem 6.2

*A graph is fixation equivalent to a Moran process if and only if all single-vertex fixation probabilities are equal.*

### Proof.

Rewriting equation (6.8) yields
6.10with . For a compete graph, *I*_{ρ} is just log *N*. The second term on the right in equation (6.10) is non-zero unless *δρ*_{i}=0 for all *i*; hence, the fixation entropy equals that of a Moran process if and only if all single-vertex fixation probabilities are equal. This is equivalent to all vertex temperatures being equal since the temperature of a vertex is proportional to the probability of a single mutant placed at that vertex dying in the next iteration of the birth–death process; if the temperatures of two vertices differed, so will their fixation probabilities. Further, if all single-vertex fixation probabilities are equal, they must equal that of a Moran process, otherwise the sum of temperatures for all vertices would not equal *N* (equivalently, the matrix *W* would not be row stochastic). □

The entropies *I*_{a} and *I*_{t} can be computed for more general cases using equations (6.6). Figure 1 shows comparisons of four classes of circular flows, (1^{k},*n*)=(1,…,1,*n*), the bipartite graph (*s*,*n*), the (1,*s*,*n*) funnel and the (*n*,*s*,1) cascades, treating the variables *k* (number of single sites in (1,…,1,*n*)), *s* and *n* as continuous. The graphs (1,*s*,*n*) and (*n*,*s*,1) have the same automorphism group entropy, but different temperature entropies, with that of the (1,*s*,*n*) graph being higher, as indicated in figure 1*e*.

## 7. Examples

This section presents a number of examples illustrating similarities and differences between closely related graphs. Based on these examples, we are able to draw tentative conclusions about relations between variances, entropy measures and fixation probabilities. For the graphs of figures 2–5, we show the difference *ρ*_{G}−*ρ*_{M} between the graph fixation probability and the corresponding Moran probability, rather than just the fixation probability, since these are usually close to the Moran probability and differences do not show up well when graphed.

Table 1 shows the values of *I*_{a}, *I*_{t}, *V* _{t}, and the range for enhancement of selection for the graphs considered in figures 2–5.

The first graphs considered are simple homogeneous circular flows of length *k*+1 defined by *n*_{0}=*n*_{1}=*Λ*=*n*_{k−1}=1, *n*_{k}=*n*.

Figure 2 show these cases for 1≤*k*≤4 and 2≤*n*≤4. The cycle (*n*=1) is fixation equivalent to a Moran process on a complete graph. As *k* increases, figure 2 shows the fixation probabilities converging towards the *r*-axis, while the entropies *I*_{t} and *I*_{ρ} converge to log *N* and *I*_{a} converges to zero, as does the variance *V* _{ρ}.

### Lemma 7.1

*Let* (1^{k},*n*) *be the simple homogeneous circular flow* (1^{k},*n*), *n*_{i}=1,0≤*i*≤*k*−1. *Then, the following limits hold*:
7.1*Proof follows directly from the definitions, which involve division by* *N*=*k*+*n*.

Other limits that appear to hold are and .

Reference to table 1 and figure 2 shows that *ρ*_{G}−*ρ*_{M} and *V* _{ρ} are positively correlated with *V* _{t}, while *I*_{a} and *I*_{ρ} are negatively correlated. Figure 2*b* shows the comparison of all single-vertex fixation probabilities minus the Moran probability, which is the same for all vertices. In each case, the vertex for which this is most negative is the *k*−1 (highest temperature) vertex. In addition, the greatest positive value is for the class of *n* vertices, while the remaining vertices have positive values of *ρ*_{G}−*ρ*_{M} that increase with distance from the *k*−1 vertex. The final figure of figure 2*a* compares the graphs (1,1,*n*) with 2≤*n*≤5. As *n* increases, so do *V* _{ρ}, *ρ*_{G}−*ρ*_{M} and *I*_{ρ}, while *I*_{a} and *I*_{t} decrease.

Figure 3 considers the funnel graphs (1,2,*n*) and cascade graphs (*n*,2,1) for 3≤*n*≤6. For the (1,2,*n*) graphs with *n*<6, selection is enhanced for limited values of *r*>1, while for the (*n*,2,1) graphs, selection is enhanced for all *r*>1, except in the (3,2,1) case (table 1).

Comparison of figure 3*b*,*f* indicates that this difference relates to the fixation probability for the initial (*n*_{0}) vertices, which remain negative in the (1,2,*n*) case and become positive in the (*n*,2,1) case. The values of *r* for which this occurs are given by: (3,2,1), 4.6706; (4,2,1), 2.6302; (5,2,1), 1.9779; (6,2,1), 1.6777. The temperature of these vertices for the (*n*,2,1) graph is 2/*n*, while for the (1,2,*n*) graph, it is 2. For the (1,2,*n*), graphs *ρ*_{G}−*ρ*_{M}, *V* _{ρ} and *I*_{ρ} are positively correlated with *V* _{t}, while *I*_{a} is negatively correlated. *I*_{t} has a maximum value at *n*=4 and decreases for larger values. In addition, for the (1,2,3) case, the *ρ*_{G}−*ρ*_{M} curve for the initial (*n*_{0}) vertex intersects that for the second (*n*_{1}) vertex at *r*=6.5426, so that for values of *r* larger than this, the initial vertex has a lower fixation probability than the second vertex. For the (*n*,2,1) graphs, *ρ*_{G}−*ρ*_{M}, *V* _{ρ} and *I*_{ρ} are positively correlated with *V* _{t}, while *I*_{a} and *I*_{t} are negatively correlated.

It might be thought that cases with *r*>1 in which selection is enhanced or suppressed depending on the value of *r* are relatively rare, but the next set of examples (figures 4 and 5) show that many such cases exist. The ranges of fitness for which a graph enhances or suppresses selection are shown in table 1. One caveat is that when the range for enhancement is shown as 1<*r*, this means that apparently selection is enhanced for all *r* greater than 1, but this has only been tested up to *r* values where further inspection is impossible as a result of rounding errors.

Figure 4*a*,*b* shows fixation probabilities for several graphs that have limited enhancement ranges, as well as two graphs (1,1,2 and 2,2,4) that appear to enhance selection for all *r*>1. Figure 4*c*,*d* compares the fixation probabilities for the graphs (1,3,4) and (1,4,3) (figure 4*c*) or (1,2,3) and (1,3,2) (figure 4*d*), giving a good example of the effect that an interchange of two classes of vertices can have. In these graphs, the highest temperature vertex is the single vertex with temperature 4 for the (1,4,3) graph, 3 for the (1,3,4) and (1,3,2) graphs and 2 for the (1,2,3) graph. Figure 4*e* shows *V* _{ρ}, and figure 4*f* shows the fixation entropies for the (1,3,4) and (1,4,3) graphs. For these cases, the values of *ρ*_{G}−*ρ*_{M} and *V* _{ρ} are negatively correlated with *V* _{t}.

Nowak [3] describes two classes of graphs that suppress selection for all *r*>1. The first class consists of rooted graphs because if the mutant is not introduced at the root, fixation is impossible. The second consists of graphs of the form *G*=*G*_{1}∪*G*_{2}, where *G*_{1} is a complete graph and all vertices of *G*_{2} are accessible from *G*_{1}, but no vertex of *G*_{1} is accessible from *G*_{2}. In both of these cases, the suppression of selection is a result of a disconnection in the graphs—there are some vertices that are not accessible from other vertices. Figure 5 shows examples of a third class of graphs for which selection is suppressed without any such disconnection. Figure 5*a* shows *ρ*_{G}−*ρ*_{M} for three cases that suppress selection for all *r*>1. Figure 5*b* shows how vertex position influences enhancement or suppression of selection, whereas figure 5*c*,*d* shows the variance and fixation entropy for the cases of figure 5*b*. Figure 5*e*,*f* illustrates the effect of adding another vertex to a graph.

Referring to table 1, *ρ*_{G}−*ρ*_{M} is negatively correlated with *V* _{t} for the graphs (1,2,2,2), (1,1,2,2) and (1,1,3,2), while it is positively correlated for the (1,2,3), (1,1,2,3) and the (3,2,1), (1,1,3,2) comparisons of figure 5*e*,*f*. In figure 5*b*, the fixation probabilities for the (1,1,2,3) and (1,1,3,2) graphs are equal for *r*=9.1365 with those of the (1,1,3,2) graph, becoming larger for greater values of *r*.

One further example of interest is the graph shown in figure 6.

The weights of each edge directed from the level with three vertices are 1/2, while it is *p*/3 for the edges directed from the level with two vertices. For *p*=1, this is the complete bipartite graph *K*_{2,3}.

Figure 7*a* shows the value of *ρ*_{G}−*ρ*_{M} as a function of *r* and *p*, for *r*≥1. For values of *p* near one, this graph is like *K*_{2,3}, and for all *r*>1, it enhances selection. As *p* decreases, however, a point is reached where there is a maximum value of *r* for which selection is enhanced. Figure 7*b* shows this maximum *r* as a function of *p*. The cut off value of *p*, after which selection is enhanced for all *r*>1, is *p*∼0.52.

## 8. Discussion

Section 2 gave a review of the state-space method introduced in [11] for the study of fixation probabilities on graphs. In §3, considerations centred on the Markov transition matrix, providing results relating to computation of fixation probabilities for arbitrary initial configurations of mutants, as well as establishing upper and lower bounds for approximation of these probabilities. A class of graphs called circular flows was defined in §4, while §5 provided a general summation formula for *k*-vertex fixation probabilities of a complete bipartite graph (the simplest circular flow). A main goal of this paper has been to consider examples of fixation probabilities on graphs in order to identify regularities characterizing different population structures. To facilitate this, entropy and fixation probability variance measures were introduced in §6 and a number of examples were studied in §7.

In the study of Broom *et al*. [12], an inclusive study of all 853 distinct undirected graphs with seven vertices showed an overall positive correlation between fixation probabilities and the variance of vertex degree at a fixed value of fitness (*r*=2), leading to the conclusion that ‘high variability of the degree of vertices is the key element associated with high mutant fixation probability’. While some of our results support this conclusion, other cases indicate that the situation is more complex. Since we are considering directed graphs, we do not consider vertex degree but vertex in degree. In addition, rather than taking the variance of vertex in degree as a variable, we have used the variance of vertex temperature, a variable related to single-iteration extinction probabilities.

For graphs of the form (1^{k},*n*), figure 2 and table 1 indicate that this variance, *V* _{t}, is positively correlated with *ρ*_{G}−*ρ*_{M}, as is the variance *V* _{ρ} of single-vertex fixation probabilities, while these are negatively correlated with the automorphism (*I*_{a}), temperature (*I*_{t}) and fixation entropies (*I*_{ρ}).

For the funnel graphs (1,2,*n*) and (1,3,*n*) and the cascade graphs (*n*,2,1), (*n*,3,1), figure 3 and table 1 show positive correlation of *V* _{t}, *ρ*_{G}−*ρ*_{M}, *V* _{ρ} and *I*_{ρ}, while these are negatively correlated with *I*_{a}. The temperature entropy for the (1,2,*n*) graphs behaves differently, initially increasing and then decreasing, as it also does with the (1,3,*n*) cases examined. The graphs of figures 4 and 5, however, show examples in which *ρ*_{G}−*ρ*_{M} is negatively correlated with *V* _{t} with the cases of (2,3,3), (1,2,2) and (1,3,3) of figure 4 and in particular the graphs (1,2,2,2), (1,1,2,2) and (1,1,3,2) in figure 5*a* and the graphs (1,1,2,3) and (1,1,3,2) in figure 5*b*. A possible explanation for this is that the cases of negative correlation involve graphs for which *ρ*_{G}−*ρ*_{M} is negative for *r*>1, so that the fixation probability is less than that of a Moran process, for which the temperature variance is 0. But this does not explain the examples of figure 4*c*,*d* for which the graphs (1,3,2) and (1,4,3) have higher temperature variance than (1,2,3) and (1,3,4), respectively, (0.8056 and 1.1979 versus 0.4722 and 0.8229), yet have lower fixation probabilities for *r* values 1<*r*<7.9623 in the first case and 1<*r*<7.2809 in the second. A similar case occurs with the graphs (1,2,2) and (2,3,3)—the latter has the highest temperature variance and the highest value of *ρ*_{G}−*ρ*_{M} for 1<*r*<2.3236, but for *r*>2.3236, the (1,2,2) graph has the highest *ρ*_{G}−*ρ*_{M} value (although this remains negative).

These examples suggest that in general, *V* _{t} is positively correlated with |*ρ*_{G}−*ρ*_{M}|, but that fitness also plays a significant role.

Plots of the single-vertex values of *ρ*_{G}−*ρ*_{M} (figures 2*b* and 3*b*,*f*) also provide a way of determining most or least advantageous vertices for mutant spread. Figure 3*b* gives a particularly nice example and the lowest curves correspond to the middle (*n*_{1}) vertices, the central set of curves to the initial (*n*_{0}) vertex and the highest curves to the final (*n*_{2}) vertices. The best choice for mutant spread is obviously one of the final vertices and, in general, the best choice for mutant suppression is one of the two central vertices. But for the (1,2,3) funnel graph with *r*>6.5426, it is best to choose the initial vertex to have the best chance of suppression.

## Acknowledgements

This work was supported by NSERC Discovery Grant OGP 0024871 and an NSERC USRA grant to A.M., summer 2012. A version of this paper was presented in the University of Victoria Mathematical Biology Seminar, 22 October 2012. A.M. was an NSERC undergraduate student research assistant, May–August 2012.

## Footnotes

↵1 At present, this runs on a MacPro laptop for values of

*N*up to 7 in the general case and 19 in special cases (e.g. simple bipartite graphs).

- Received November 13, 2012.
- Accepted March 20, 2013.

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