Royal Society Publishing

Fixation probabilities for simple digraphs

Burton Voorhees, Alex Murray

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 2N-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 [26]. 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 [710] 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 [1418].

For a homogeneous population of size N represented by the complete graph KN, the single-vertex fixation probability is given by Embedded Image1.1In general, however, calculation of the birth–death fixation probability for a graph with N vertices involves solution of 2N−2 linear equations in an equivalent number of unknowns [11,19]; hence, most studies seek asymptotic approximations [2022], 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 Ks,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 2N 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=(v1,…,vN), where vi 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 (HN) of the N-hypercube. Population structure is represented by an edge-weight matrix W=(wij) with wij 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 Nm 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), Embedded Image2.1In the formulation used in [1,12,19], if C is the subset of vertices in V occupied by mutants, then the probability PC that this set goes to fixation is Embedded Image2.2with boundary conditions Pϕ=0, PV=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(v) and b(v) are defined by a(v)=vW and b(v)=v′⋅W, where vi=1−vi. Thus, for a given state vector v, aj(v) is the sum of all probabilities that an edge originating at a vertex occupied by a mutant terminates at vertex j and bj(v) is the sum of all probabilities that an edge originating at a vertex occupied by a non-mutant terminates at vertex j. In the language of [1], the sum aj(v)+bj(v)=tj 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≤jN and for all states v with Embedded Image the following hold.

  1. The probability of a transition from the state (v1,…,vj−1,0,vj+1,…,vN) to the state (v1,…,vj−1,1,vj+1,…,vN) is given by Embedded Image2.3

  2. The probability of transition from the state (v1,…,vj−1,1,vj+1,…,vN) to the state (v1,…,vj−1,0,vj+1,…,vN) is given by Embedded Image2.4

  3. The probability that v remains unchanged is Embedded Image2.5

Based on this theorem, a state transition matrix T=(Tuv) is defined on V (HN). As a notational point, to avoid confusion between the N vertices of the graphs G and the 2N 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, v can be viewed as binary numbers and the corresponding indices 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 Embedded Image and taking xv as the probability that the corresponding state v goes to fixation, the equation (IT)⋅x=0 for the Markov steady states, with x0=0 and x2N−1=1, yields the system of master equations [11] Embedded Image2.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=(u1,u2,…,uN), this defines the binary number u1u2uN with corresponding denary form given by Embedded Image. The 2N population states can be listed in numerical order, starting with 0, to define a 2N×N matrix S with Sui=ui. 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 [TkS]ui.

Theorem 3.2

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

Proof.

Since the Markov process with transition matrix T converges to either extinction or fixation, for large k, [Tk]uv∼0 unless v is 0 or 1, and from [11] Embedded Image3.1where Embedded Image □

Based on this theorem, one method for computing the fixation probability of a state u is to compute Embedded Image. 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, Embedded Image3.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−[Tk]u0−[Tk]u1 and write the linear interpolation estimate for the fixation probability as Embedded Image3.3This makes it possible to at least tentatively answer the following question: given that the observed state after k iterations is v, what are the most probably initial states to produce this observed configuration? The answer is obtained by finding Embedded Image One problem arising in this is that for large k, all entries of Tk 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 Tk by the appropriate column sum. Let Embedded Image and D(k)=diag[D(v,k)]. Then, the column entries in TkD−1(k) will be relative rather than absolute probabilities, and these can be computed from Tk−1D−1(k−1) as TkD−1(k)=[TTk−1D−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 TTk−1D−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 {Gs=(V s,Es)|0≤sk} be a family of k+1 graphs with |V s|=ns and with each Gs having a strictly sub-stochastic edge-weight matrix Ws. Let Embedded Image and let {Ms+1,s} be a set of matrices with Ms+1,s of size ns+1×ns, where s+1 is evaluated mod(k+1), such that the N×N matrix W with the form Embedded Image4.1is row stochastic. The graph Embedded Image with edge-weight matrix W is called a circular flow. G is homogeneous if Embedded Image4.2where 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 Ks,n (without loss of generality, sn).

Circular flows are labelled by the (k+1)-tuple (n0,n1,…,nk). 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 Embedded Image4.3where Pi is an arbitrary ni×ni 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 2N−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 ms<ns mutants at level s will have the same fixation probability as any other set of ms mutants at that level. Hence, a reduced state space is defined with states denoted by listing the number of mutants at each level: m=(m0,m1,…,mk), 0≤mini. The total number of state equivalence classes is Embedded Image.

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

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

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 uv=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= ρuv.

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 KN or on a graph fixation equivalent to this graph. Then, Embedded Image5.1

Proof.

This follows immediately from equation (1.1), the solution Embedded Image5.2of equation (2.6) for the complete graph [11] and the identity Embedded Image □

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 (rN−2−1)/(rN−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 Ks,n.

Theorem 5.3

Let Ks,n be the complete bipartite graph with 1≤s<n and let xk,m be the fixation probability for the state (k,m). Then, Embedded Image5.3

Remark

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

Proof.

For the Ks,n graph, equations (5.3) become Embedded Image5.4with boundary conditions x0,0=0, xs,n=1. □

Substitution from equations (5.3) into (5.4) reduces these equations to identities, the exceptions being (sr+n)xs,n−1nxs−1,n−1sr=0 and (nr+s)xs−1,nnxs−1,n−1nr=0 that, using equation (6.4), reduce to equations that can be solved for x0,1, yielding Embedded Image5.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 Ks,n is Embedded Image5.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 ns is the number of vertices in the sth equivalence class of Aut(G), the automorphism entropy of the graph is Embedded Image6.1where N is the total number of vertices. For the complete graph KN, Aut(KN) is the full permutation group, there is a single equivalence class and Ia(G)=0. This will also be the case for all graphs that are fixation equivalent to a Moran process. The maximum value for Ia(G) occurs when Aut(G)={I}, in which case Embedded Image.

Other entropy measures can be defined that provide information on aspects of graph structure. If Embedded Image is any map assigning a probability to each vertex of G, then Embedded Image 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 Embedded Image6.2where tj is the ‘temperature’ of vertex j, defined by Embedded Image [1,3].

The associated entropy is Embedded Image6.3Since W is row stochastic, the sum of temperatures tj equals N and Embedded Image6.4indicating that It 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 tj/N is analogous to the pressure exerted on vertex j by the population distribution (described by specifying a state u) and the terms aj(u)/N, bj(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 Ia and It are independent of the fitness r and the fixation probabilities. Equation (6.3) for a simple homogeneous circular flow G=(n0,…,nk) can be written as Embedded Image6.5A simple calculation yields the next theorem.

Theorem 6.1

Let G be a simple homogeneous circular flow defined by (n0,…,nk). Then, Embedded Image6.6Hence, Embedded Image6.7While Ia relates to graph structure as determined by the graph automorphism group, It is connected to the in degree of each vertex; hence, their difference describes the graph connectivity structure. For a general graph, this difference is Embedded Image6.8Another useful measure is the entropy associated with single-vertex fixation probabilities, Embedded Image6.9where ρi is the single-vertex fixation probability for a mutant introduced at vertex i. The sum in the denominator is just Embedded Image, where Embedded Image 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.

Remark

Variants of this theorem have been given in [1,2,19] and elsewhere.

Proof.

Rewriting equation (6.8) yields Embedded Image6.10with Embedded Image. 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 Ia and It can be computed for more general cases using equations (6.6). Figure 1 shows comparisons of four classes of circular flows, (1k,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 1e.

Figure 1.

Graphs (a) =1…1,n; (b) =s,n (sn), blue=Ia, red=It and (ce) blue is Ia, red is It for (1,s,n), yellow is It for (n,s,1).

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 25, 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.

Figure 2.

(a) ρGρM fixation probabilities for 11n, 111n and 1111n with 2≤n≤4, (b) single-vertex probability differences for 11n, 111n and 1111n, 2≤n≤4, (c) variances and (d) fixation entropy.

Figure 3.

(a) ρGρM, (b) single-vertex probabilities minus ρM for G(1,2,n), (c) fixation variance, (d) entropies for (1,2,n), (e) ρGρM, (f) single-vertex probabilities minus ρM for (n,2,1), (g) fixation variance and (h) entropies for (n,2,1).

Figure 4.

(ad) ρGρM, (e) V ρ and (f) Iρ.

Figure 5.

(af) Examples of suppression and enhancement of selection.

Table 1 shows the values of Ia, It, V t, and the range for enhancement of selection for the graphs considered in figures 25.

View this table:
Table 1.

Automorphism and temperature entropies, temperature variance and range for selection enhancement for graphs considered in figures 25.

The first graphs considered are simple homogeneous circular flows of length k+1 defined by n0=n1=Λ=nk−1=1, nk=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 It and Iρ converge to log N and Ia converges to zero, as does the variance V ρ.

Lemma 7.1

Let (1k,n) be the simple homogeneous circular flow (1k,n), ni=1,0≤ik−1. Then, the following limits hold: Embedded Image7.1Proof follows directly from the definitions, which involve division by N=k+n.

Other limits that appear to hold are Embedded Image and Embedded Image.

Reference to table 1 and figure 2 shows that ρGρM and V ρ are positively correlated with V t, while Ia and Iρ are negatively correlated. Figure 2b 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 2a compares the graphs (1,1,n) with 2≤n≤5. As n increases, so do V ρ, ρGρM and Iρ, while Ia and It 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 3b,f indicates that this difference relates to the fixation probability for the initial (n0) 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 Ia is negatively correlated. It 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 (n0) vertex intersects that for the second (n1) 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 Ia and It 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 4a,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 4c,d compares the fixation probabilities for the graphs (1,3,4) and (1,4,3) (figure 4c) or (1,2,3) and (1,3,2) (figure 4d), 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 4e shows V ρ, and figure 4f 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=G1G2, where G1 is a complete graph and all vertices of G2 are accessible from G1, but no vertex of G1 is accessible from G2. 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 5a shows ρGρM for three cases that suppress selection for all r>1. Figure 5b shows how vertex position influences enhancement or suppression of selection, whereas figure 5c,d shows the variance and fixation entropy for the cases of figure 5b. Figure 5e,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 5e,f. In figure 5b, 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.

Figure 6.

K2,3 graph with connecting edge at first level. (Online version in colour.)

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 K2,3.

Figure 7a 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 K2,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 7b 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.

Figure 7.

(a) ρGρM as a function of p and r for figure 6 graph and (b) r>1 root of ρGρM versus value of p.

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 (1k,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 (Ia), temperature (It) 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 Ia. 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 5a and the graphs (1,1,2,3) and (1,1,3,2) in figure 5b. 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 4c,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 2b and 3b,f) also provide a way of determining most or least advantageous vertices for mutant spread. Figure 3b gives a particularly nice example and the lowest curves correspond to the middle (n1) vertices, the central set of curves to the initial (n0) vertex and the highest curves to the final (n2) 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.

References

View Abstract