## Abstract

When a new mutant arises in a population, there is a probability it outcompetes the residents and fixes. The structure of the population can affect this fixation probability. Suppressing population structures reduce the difference between two competing variants, while amplifying population structures enhance the difference. Suppressors are ubiquitous and easy to construct, but amplifiers for the large population limit are more elusive and only a few examples have been discovered. Whether or not a population structure is an amplifier of selection depends on the probability distribution for the placement of the invading mutant. First, we prove that there exist only bounded amplifiers for adversarial placement—that is, for arbitrary initial conditions. Next, we show that the Star population structure, which is known to amplify for mutants placed uniformly at random, does not amplify for mutants that arise through reproduction and are therefore placed proportional to the temperatures of the vertices. Finally, we construct population structures that amplify for all mutational events that arise through reproduction, uniformly at random, or through some combination of the two.

## 1. Introduction

Evolutionary dynamics occur in populations of reproducing individuals [1]. Mutation generates new variants and selection chooses between variants with different reproductive rates. The *fixation probability* of an invading mutant, which is a key quantity of stochastic evolutionary dynamics [2–10], is the probability that when an individual is introduced into a population of finite size *n* its lineage takes over the entire population. The evolutionary dynamics that we consider are given by the standard Moran process, where at any one time-step an individual is randomly chosen for reproduction proportional to fitness and its offspring then replaces a random individual [11]. The relative fitness of the invading mutant is *r* and is independent of the frequencies of different types in the population. For this process [1], where the population is well-mixed so each offspring is equally likely to replace any one of the *n* individuals, the fixation probability *ρ*(*r*) is
*r*>1) or neutral (*r*=1) mutants. Thus, in the limit of infinite population size, the fixation probability converges to

When the population structure is no longer well-mixed, it can have a drastic effect on the fixation probability. In evolutionary graph theory, population structure is described by weighted, directed graphs [6]; the vertices are occupied by individuals and the edges describe where to place the offspring. For example, the well-mixed population is given by the complete graph with identical weights on all edges. In the limit of large population size, the fixation probability *ρ*_{G}(*r*) of many population structures of interest, which are described by some graph *G*, can be written as
*f*_{G} is an increasing function of *r* that has a fixed point at 1 (that is, *f*_{G}(1)=1).

It is common to classify population structures based on their fixation probability but there are no established or general definitions for these classes [6,12]. We propose general and intuitive definitions of the classes using the function *f*_{G}. At the highest level, a population structure is an *amplifier of selection* if *f*_{G}(*r*)>*r* for all *r*>1 and a *suppressor of selection* if *f*_{G}(*r*)<*r* for all *r*>1. This is motivated by equation (1.2) and by using the well-mixed population as a canonical point of comparison. Amplifiers exaggerate the fitness differences between the invading mutant and the residents, whereas suppressors reduce fitness differences. Many population structures have the same fixation probability as (1.1), so that *f*_{G}(*r*)=*r*; in fact, the isothermal theorem proves this equality for all population structures where the propensity for change is the same in each position [6,4,13]. In the theorem, all symmetric population structures are obtained as a special case [14,15]. We call the function *f*_{G} the *implied scale of fitness*. Intuitively, it characterizes how fitness would need to be distorted to produce the same fixation probability *ρ*_{G} in the well-mixed population.

The implied scale of fitness (and similarly the fixation probability) can also depend on the initial location of the invading mutant or the probability distribution specifying where it arises. A typical initial condition, that we call *uniform initialization*, is that the new mutant arises with equal probability in all of the *n* vertices of the graph. Here mutations are independent of reproduction and occur at all locations at a constant rate per unit time. In cultural evolution, this is particularly natural and corresponds to each person generating new ideas at a constant rate. For uniform initialization, the Star (figure 1), where a central vertex (centre) is surrounded by *n* leaf vertices (leaves), has an implied scale of fitness equal to *r*^{2} and is thus an amplifier of selection [1,6,16–18].

Another natural initialization, which we call *temperature initialization*, is to place new mutants on a vertex proportional to the rate at which offspring replace that vertex. Therefore, the occurrence of mutants is proportional to the *temperature* of the vertex, which is the sum of all incoming edge weights. During the evolutionary dynamics, ‘hotter’ vertices are replaced more often, so new mutants are more probably to arise in hot vertices when we consider mutations that occur during reproduction. For example, in the Star the centre is hot, whereas the leaves are cold, so under temperature initialization, mutants arise much more frequently in the centre than the leaves. Under temperature initialization, we show that the Star is a suppressor and its implied scale of fitness is 1.

Crucially, it follows that not only the frequency, but also the mechanism of mutation can affect the rate at which mutants fix in a population. Using the implied scale of fitness, we are able to quantify these effects and extend the usual classifications of population structure to all initializations. Another initialization we consider is *adversarial initialization*, where we suppose that the mutant is initialized by an adversary to minimize the fixation probability. Adversarial initialization is primarily of theoretical interest—in particular—if a population structure is an amplifier for this initialization, then it is an amplifier for arbitrary initialization. This leads us to three main questions:

### Question 1

Is there a population structure that amplifies for all initializations simultaneously?

### Question 2

Is there an amplifier for temperature initialization?

### Question 3

Is there an amplifier for both temperature initialization and uniform initialization?

We give a partial answer to question 1: any such amplifier is bounded in the sense that it can only increase fitness by 1, that is, *f*_{G}(*r*)≤*r*+1. We show that the answer to questions 2 and 3 is yes, and we construct specific examples.

## 2. Results

### (a) The Moran-type updating on graphs

The *Moran process* considers a population of *n* individuals, each of which is either wild-type or mutant with constant fitness 1 or *r*, respectively, undergoing reproduction and death [11]. The process starts when a single mutant is introduced into a homogeneous wild-type population. At each discrete time-step, an individual is chosen randomly for reproduction proportional to its fitness; another individual is chosen uniformly at random for death and is replaced by a new individual of the same phenotype as the reproducing individual. In the long run, this Markovian process has only two possible outcomes: the mutants fix and the wild-type dies out or the reverse. The probability of the first event is the fixation probability.

Population structure is modelled by running the process on a graph where vertices represent individuals and edges represent interactions between individuals [1,6]. Formally, let *G*_{n} be a weighted, directed graph, where the vertex set *V* _{n} is {1,2,…,*n*} and the edge matrix *W*_{n} is stochastic. During reproduction, an edge, originating from the reproducing vertex, is selected randomly with probability equal to its edge weight. The terminal vertex of the chosen edge takes on the type of the vertex at the origin of the edge.

### (b) Initialization of the invading mutant

The fixation probability is affected by many different factors [2]. Typically, the fixation probability depends on the population size *n* and the ratio of the fitnesses of the mutant and the wild-type *r* [1,14]. For example, in the well-mixed population, where all individuals interact with each other equally, the fixation probability *ρ*(*r*) is given by (1.1), which converges to (1−*r*^{−1}) **1**_{r≥1} as **1**_{r≥1} is an indicator function.

However, fixation probabilities also depend on population structure when we lose the symmetry and homogeneity of the well-mixed population [6,16,17,19,20–24]. For general population structures, the fixation probability typically depends on the initial location of the mutant [25,26], unlike the well-mixed population where the probability of the mutant fixing is given by (1.1) regardless of where the mutant arises [1,14]. For example, if a population has an upstream and downstream part, a mutant is more probably to fix if it originates in the upstream part of the population (see electronic supplementary material, lemma 2.3). Thus, it is important to consider how mutants arise.

Primarily, we consider two standard ways mutants may arise in a population. First, mutants may arise spontaneously and with equal probability at any vertex in the population structure—termed *uniform initialization*. Second, mutants may arise through reproduction and thus arise at a vertex proportional to the number of reproductive events at that vertex—termed *temperature initialization*. In many population structures, uniform and temperature initialization result in different fixation probabilities.

Let **v** be a probability vector where the *i*th entry *v*_{i} is the probability that the mutant is introduced at vertex *i*. The fixation probability of a mutant with fitness *r* initialized according to **v** on the graph *G*_{n} is denoted *ρ*^{v}_{Gn}(*r*). Uniform and temperature initializations are particularly biologically relevant: mutants originating spontaneously arise at each vertex with equal probability, so define unif:=(1/*n*,…,1/*n*). Mutants originating via reproduction arise at a vertex with probability proportional to the frequency of reproductive events replacing that vertex, that is, the sum of the incoming edge weights in the model. Recall that *w*_{ij} is the weight of the directed edge (*i*,*j*) and the (*i*,*j*)th entry of *W*_{n}. Define the temperature of vertex *j* as
*T*_{1}/*n*,…,*T*_{n}/*n*), which is a probability vector as *W*_{n} has non-negative entries and is stochastic, so *T*_{1}+⋯+*T*_{n}=*n*.

*Adversarial initialization*, which is defined as the initialization **v** that minimizes **i** denote the vector that is zero for all entries other than the *i*th entry, which is 1. Formally, define *r*.

### (c) Defining amplification in the general Moran process

Under uniform initialization, it is known that population structure can distort fitness differences [1,6,16], where the well-mixed population serves as a canonical point of comparison. Intuitively, amplifiers of selection exaggerate variations in fitness by increasing (respectively decreasing) the chance of fitter (respectively weaker) mutants fixing compared with their chance of fixing in the well-mixed population. This is exactly the original definition of an amplifier given in [1] for uniform initialization. It is important to note that amplifiers do not simply increase the fixation probability for all values of *r*. Rather, they enhance the difference in fixation probability between two competing variants. Hence they are amplifiers of *selection* and not simply *fixation probability*.

For example, the Star is an amplifier for uniform initialization and its fixation probability *ρ*(*r*) is
*r*^{−2})**1**_{r≥1} as *r* [1].

Under uniform initialization, amplification is straightforward to define, as *ρ*(1)=1/*n* for any population structure—the fixation probability for a neutral mutant cannot be changed [1]. Thus, all fixation probabilities intersect the point (1,1/*n*). So, in comparison to the well-mixed population, we can define amplifiers as structures whose fixation probability *ρ*(*r*) satisfies *ρ*(*r*)<(1−*r*^{−1})/(1−*r*^{−n}) for *r* less than 1 and *ρ*(*r*)>(1−*r*^{−1})/(1−*r*^{−n}) for *r* greater than 1. Note that this definition implicitly requires that the fixation probability of a neutral mutant remains 1/*n*, which in the large population limit implies that *f*(1)=1.

When the mutant arises in other ways, defining amplification is more complicated. In the case of temperature initialization, it has been demonstrated that *ρ*(1)≤1/*n* with equality if and only if the population structure is *isothermal* (equivalently *T*_{j} is constant in *j* or *W*_{n} is doubly stochastic) [25]. In any isothermal population structure, the fixation probability is the same as (1.1), regardless of where the mutant arises [1,6]. Thus, *a fortiori*, for any isothermal population structure the fixation probability of a mutant initialized proportional to temperature is also (1.1). Therefore, it is impossible to satisfy the original definition of amplification and suppression under temperature initialization, unless *ρ*(1)<1/*n*. So not all fixation probabilities pass through (1,1/*n*) anymore. Thus, we need a more subtle definition of amplification.

To define amplification for arbitrary initial conditions, we must look at the large population limit for two reasons. First, many small graphs are amplifiers under uniform initialization using the standard definition [27,28]. However, these effects are negligible for large graphs and disappear completely in the large population limit [4]. This is a marked distinction with an amplifier such as the Star, whose amplifying properties survive in the large population limit and cannot be considered negligible. This is why we say amplifiers have proved to be elusive in general. Second, the fixation probabilities of some population structures have pathological behaviour in the large *r* limit that complicates rigorously defining amplification. It is natural to expect that the limit of *ρ*(*r*) as *r*, there is some *r* such that *ρ*(*r*)<(1−*r*^{−1})/(1−*r*^{−n}). Other examples of graphs that amplify only for particular values of *r* have been described [29,30]. While the biological relevance of the large fitness limit is questionable, it is necessary we consider them for a rigorous, mathematical definition of amplification.

Thus, we define amplification in the large population limit using the implied scale of fitness: The fixation probability *ρ*(*r*) is defined for finite populations and its expression can be very complicated, but often the function takes a simpler form in the large population limit such as
*f* the implied scale of fitness (where we interpret *f* has been distorted, as
*f*(*r*)=*r*^{2}>*r* for all *r*>1 and *f*(1)=1. In general, we define amplifying population structures as having an implied scale of fitness such that *f*(*r*)>*r* for all *r*>1, and suppressing population structures have an implied scale of fitness such that *f*(*r*)<*r* for all *r*>1. We require that *f*(1)=1 as the fixation probability of a neutral mutant should not change (at least in the large population limit). Note that as, *f* is non-decreasing and greater than or equal to 1 (as *ρ* is non-negative and non-decreasing), it suffices to consider *r*≥1 in our definition.

In all isothermal population structures, the implied scale of fitness takes the simple form *f*(*r*)=*r* for all initializations. However, the scale can be distorted and it gives us a natural way of parametrizing the distorting effect population structure has on fitness. In this paper, we consider amplification and suppression under temperature initialization, uniform initialization and mixtures of both.

### (d) Amplifiers and classification

A fundamental question in evolutionary graph theory is the existence of amplifiers [1,6,22,27], which we define as above using the implied scale of fitness. As we consider the large population limit, we must consider sequences of graphs. There is no constraint on which graphs can form a sequences and we do not require that the sequence of graphs is defined for all population sizes—only that it is defined for arbitrarily large population sizes. This is necessary due to examples like the Superstar [6].

Formally, let *n*_{k} is a strictly increasing sequence of natural numbers. Often we set *n*_{k}:=*k*. Fix an initialization vector **v**, then define **v**-amplifier if
*r*>1 and
*r*≤1. Suppressors are defined similarly with the inequality in (2.5) reversed and the infimum replaced with the supremum. We use the

### (e) Three basic questions

The existence of amplifiers has been extensively studied under uniform initialization. However, the existence of amplifiers for the equally important temperature initialization has not been considered before. We consider several basic questions regarding the existence of temp-amplifiers, which we restate from before using our precise notation.

Question 1. Does there exist an adv-amplifier?

Question 2. Does there exist a temp-amplifier?

Question 3. Does there exist a sequence of graphs that is simultaneously a unif-amplifier and temp-amplifier?

### (f) Partial answer to question 1

The strength of amplification is variable and we distinguish amplifiers that only shift the scale up to a constant additive factor: a sequence of graphs *bounded* **v**-*amplifier* if it is a **v**-amplifier and *c*>0 (figure 2).

### Theorem 2.1

*For any sequence of graphs* *we have
**and hence the only amplifiers under adversarial initialization are bounded amplifiers.*

The argument for theorem 2.1 is simple but not necessarily optimal (see electronic supplementary material, lemma 3.1). Given any graph *G*_{nk}, consider the vertex *i*:=arg max_{1≤j≤n}*T*_{j} that has the maximum temperature. We show
*f*^{i}_{Gnk}(*r*)≤*r*+1, and so if

### (g) Positive answers to questions 2 and 3

We define the sequence of Star graphs and its extension, the Looping Star (figure 1). We then show the sequence of Star graphs, which is a unif-amplifier, is in fact a suppressor for temperature initialization. Contrastingly, we show that the Looping Star is both a unif-amplifier and a temp-amplifier.

We set *n*_{k}:=*k*+1. Moreover, we consider graphs with *n*+1 vertices here instead of *n*, as it is more convenient for computations. For *x*∈(0,1] and *y*∈(0,1], define the graph *G*_{n+1}(*x*,*y*) by its weight matrix,
*G*_{n+1}(*x*,*y*) represents a Star graph where the centre is surrounded by *n* leaves; the centre has a self-loop of weight 1−*y* and edges of weight *y*/*n* to each leaf; each leaf has a self-loop of weight 1−*x* and an edge of weight *x* to the centre (figure 1). The well-studied Star graph, *S*_{n+1}, is obtained as *G*_{n+1}(1,1), where there are no self-loops and it is known that *ρ*^{unif}_{Sn}(*r*)≈(1−*r*^{−2})/(1−*r*^{−2n}). Thus, for (*S*_{n+1})_{n≥0}, denoted by

### Theorem 2.2

*The Star is a* temp*-suppressor. In fact,* *and so
*

However, we show, rather surprisingly, that simply by adding self-loops to the centre and leaves in the correct ratio, it is possible to modify the Star to mitigate the temperature difference while retaining its amplifying properties. Define the Looping Star graph *L*_{n+1}:=*G*_{n+1}(*n*^{−1},*n*^{−2}) and the sequence

### Theorem 2.3

*The Looping Star is simultaneously a* unif*-amplifier and* temp*-amplifier. In fact,
**and so
*

Thus, the fixation probability for the Looping Star graphs in the limit is like the well-mixed population with fitness *r*^{2} instead of *r*, for both temperature as well as uniform initialization (figure 3).

## 3. Discussion

Until now the fundamental question of the existence of amplifiers has only been considered in the case of uniform initialization, which corresponds to one important case of biological relevance where mutants arise spontaneously. We consider the equally important case where mutants arise proportional to the rate of reproduction (table 1). The question is stated formally by generalizing the definition of amplification to apply to any initialization using the implied scale of fitness, which quantifies exactly how population structure distorts fitness differences. After showing that the Star loses its amplifying properties under temperature initialization, our question is answered by modifying the Star into a sequence of graphs that amplify for both uniform and temperature initializations simultaneously.

Adversarial initialization, which minimizes the fixation probability over all initial conditions, has not been considered before. In theorem 2.1, we derive a general result on the limitations of amplifiers by asking what they can do in the worst case. We prove that only bounded adv-amplifiers exist. However, we conjecture that theorem 2.1 is not optimal and can be strengthened to state that no amplifiers (including bounded amplifiers) exist for adversarial initialization.

### Conjecture

*There are no amplifiers for adversarial initialization or, equivalently, for all* *and all r*≥1,

A further question which has been studied only in the uniform initialization case is the existence of arbitrarily strong amplifiers [1,6,31]. A sequence of graphs *maximal* **v**-*amplifier* if
*maximal* **v**-*suppressor* if *r*≥1. In a maximal amplifier, the implied scale of fitness is reduced to two points and any arbitrarily slight fitness advantage guarantees fixation. Whereas, in a maximal suppressor, the implied scale of fitness is collapsed to a single point and changes in fitness have no impact on the fixation probability of 0. The existence of a maximal amplifier for temperature initialization is an open question and a possible direction for future work. It is unknown whether the technique of adding self-loops can be adapted to the Superstar, which is a maximal unif-amplifier, to produce a maximal temp-amplifier [6,31,32].

While maximal-amplifiers and maximal-suppressors distort the implied scale of fitness as much as possible, there is a sense in which the scale is robust. Robustness results for the isothermal theorem may be used directly to control distortions to the implied scale of fitness for any initialization **v** [4]. For fixed *ε*≥0, let *w*_{O}(*S*) and *w*_{I}(*S*) correspond to the sum of the outgoing and ingoing edges, respectively, from the subset *S*. So by the *robust isothermal theorem* [4],
*ε* and *r*, the implied scale of fitness is approximately linear. In particular, if *ε*_{n} is allowed to depend on *n* such that *ε*_{n}→0, then

Finally, although we focused on constant fitness, we note it is natural to consider mutants with a different strategy dictating their interactions. Models where fitness is dependent on the frequency of the different types in the population have received much attention [33–44]. So an interesting, open problem is to make sense of amplifying population structures in this case.

## 4. Methods

In this section, we describe the key ideas used to establish our results.

### (a) Intuition for theorem 2.1

The result is obtained by a simple analysis of Markov chains. We consider the Markov chain representing the evolutionary process on the graph. For a vertex *i* with maximal temperature, its temperature is at least 1, as the sum of the temperatures of all vertices is normalized to be *n*. Initialize the mutant at vertex *i*, then when the state of the Markov chain changes, the mutant is replaced by a wild-type with probability at least 1/(*r*+1). Hence the fixation probability is at most 1−1/(*r*+1) and the desired result follows.

### (b) Intuition for theorems 2.2 and 2.3

For the Looping Star, we again consider the Markov chain for the evolutionary process. By symmetry, we can consider the Markov chain on a reduced state space of size 2(*n*+1) rather than size 2^{n+1}, where the Markov chain keeps track whether the centre is a wild-type or a mutant and how many of the *n* leaves are occupied by mutants. Next, we define an exponential martingale (using ideas from [18]) to analyse the Markov chain, and then Doob's optional stopping theorem [45] for martingales implies
*x*=1/*n* and *y*=1/*n*^{2} and taking the limit as

## Data accessibility

Electronic supplementary material accompanies the article online.

## Authors' contributions

B.A., K.C. and M.A.N. performed the research and wrote and reviewed the manuscript.

## Competing interests

The authors declare no competing financial interests.

## Funding

K.C. gratefully acknowledges support from ERC Start grant no. (279307: Graph Games), Austrian Science Fund (FWF) grant no. P23499-N23, and FWF NFN grant no. S11407-N23 (RiSE). M.A.N. gratefully acknowledges support from the John Templeton Foundation.

- Received February 20, 2015.
- Accepted July 30, 2015.

- © 2015 The Author(s)

Published by the Royal Society. All rights reserved.