EFTA01202576.pdf

Downloaded from hit pi'rspa.royalsocietypublishing.orgi on September 3, 2015 PROCEEDINGS A Amplifiers of selection rspa.royalsocietypublishing.org B. Adlaml, K. Chatterjee3 and M. A. Nowak1'2 'Program for Evolutionary Dynamics, Department of Organismic and Evolutionary Biology, and ]Department of Mathematics, Harvard University, Cambridge, MA 02138, USA Research CrossMark tglhe wain 31ST Austria, Klosterneuburg 3400, Austria Cite this article: Adlam B,Chatterjee K, Nowak MA. 2015 Amplifiers of selection. hoc. When a new mutant arises in a population, there is R.Soc A 411: 20150114. a probability it outcompetes the residents and fixes. http://dx.doi.org/10.1098/rspa2015.0114 The structure of the population can affect this fixation probability. Suppressing population structures reduce the difference between two competing variants, Received: 20 February 2015 while amplifying population structures enhance the Accepted: 30 July 2015 difference. Suppressors are ubiquitous and easy to construct, but amplifiers for the large population limit are more elusive and only a few examples Subject Areas: have been discovered. Whether or not a population applied mathematics, graph theory, structure is an amplifier of selection depends on mathematical modelling the probability distribution for the placement of the invading mutant. First, we prove that there exist only Keywords: bounded amplifiers for adversarial placement—that fixation probabilities, evolutionary graph is, for arbitrary initial conditions. Next, we show that the Star population structure, which is known theory, martingales, mutation, star graph, to amplify for mutants placed uniformly at random, temperature initialization does not amplify for mutants that arise through reproduction and are therefore placed proportional to Author for correspondence: the temperatures of the vertices. Finally, we construct M. A. Nowak population structures that amplify for all mutational events that arise through reproduction, uniformly at e-mail: random, or through some combination of the two. 1. Introduction Evolutionary dynamics occur in populations of reproducing individuals M. 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 12-101, 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 Electronic supplementary material is available at http://dx.doi.org/10.1098/rspa.2015.0114 or via http://rspanyalsocietypublishing.org. THE ROYAL SOCIETY it.) 2015 The Authorls) Published by the Royal Society. All rights reserved. PUBLISHING EFTA01202576  Downloaded from http://rsparoyalsocietypublishing.o4 on September 3, 2015 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 rspanyalsocietypublishing.org Proc. R. Soc. A 471: 20150114 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 11 individuals, the fixation probability p(r) is 1—r 1-r For simplicity of exposition, we focus here on advantageous (r> 1) or neutral (r= 1) mutants. Thus, in the limit of infinite population size, the fixation probability converges to 1 (1.2) r 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 pc(r) of many population structures of interest, which are described by some graph a can be written as (1.3) fc(r) wherefG is an increasing function of r that has a fixed point at I (that is,fc(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,14 We propose general and intuitive definitions of the classes using the (unction fo. At the highest level, a population structure is an amplifier of selection if fG(r)> r (or all r > 1 and a suppressor of selection ifk(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 fG(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 [4,6,13]. In the theorem, all symmetric population structures are obtained as a special case [14,15]. We call the function fc the implied scale of fitness. Intuitively, it characterizes how fitness would need to be distorted to produce the same fixation probability po 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 it 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 it leaf vertices (leaves), has an implied scale of fitness equal to r2 and is thus an amplifier of selection [1,6,16-18]. Mother 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. EFTA01202577  Downloaded from hnp://rspa.royalsocietypublishing.orgi on September 3.2015 5 4 rspa.royalsodetypublishing.org Pion. R. Soc A 471: 20150114 g 3 0 Figure 1. We modify the Star graph by adding self-loops of weight 1— y to the central vertex and weight 1— x to each leaf vertex (see (2.9)).The Star,on the left, is obtained when x = y = 1. It has a high-temperature central hub and low-temperature leaf vertices. The Looping Star is shown in the middle with x =1/(6 —1) and y =1/(6 — 1)2. The temperature difference between the centre and the leaves is significantly reduced. The graph on the right, with x = 0.05 and y = 0.95, shows that it is possible to make the centre colder than the leaves by increasing the weights of the self-loops. Vertex colours correspond to their temperatures given by the scale on the far-left and the edges are plotted proportional to their weights. (Online version in colour.) 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, fc(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 ri individuals, each of which is either wild-type or mutant with constant fitness 1 or r, respectively, undergoing reproduction and death in). 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 11,61. Formally, let C„ be a weighted, directed graph, where the vertex set V„ is '1,2,...,0 and the edge matrix lita is stochastic. During reproduction, an edge, originating from the reproducing vertex, is selected EFTA01202578  Downloaded from http://rspa.royalsocietypublishine.orof on September 3, 2015 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. rspasoyalsocietypublishing.org Proc. R. Soc. A 471: 20150114 (b) Initialization of the invading mutant The fixation probability is affected by many different factors 121. 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 p(r) is given by (1.1), which converges to (1 - H)1r>i as it oo, where 1„,z 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-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 11,141. 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 ith entry v, 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„ is denoted (r). Uniform and temperature initializations are particularly biologically relevant: mutants originating spontaneously arise at each vertex with equal probability, so define uoif:= (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 wy is the weight of the directed edge (i,.1) and the (i,f)th entry of W. Define the temperature of vertex j as 7):= E (2.1) i=1 Now define temp := (Turn, T„/n), which is a probability vector as W„ has non-negative entries and is stochastic, so T1 + • • • +T„ = n. Adversarial initialization, which is defined as the initialization v that minimizes 4(r), is also considered. For i II,...,nl, let i denote the vector that is zero for all entries other than the ith entry, which is 1. Formally, define adv a adv, := argminvpa(r) = argminipL(r), where the first minimum is over all probability vectors and the second is over (1,...,4 Note that adv may depend on the fitness of the mutant r. (c) Defining amplification in the general Moran process Under uniform initialization, it is known that population structure can distort fitness differences 11,6,161, 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 simplyfixation probability. EFTA01202579  Downloaded from http://rspa.royalsocietypublistnne.orai on September 3, 2015 For example, the Star is an amplifier for uniform initialization and its fixation probability p(r) is 1 r i 1 - r-2" (1 + o(1)). (2.2) rspa.royalsocietypublishing.org Proc R. Soc A 471: 20150114 The above expression converges to (1 - r-2)1r>1 as it -0 00 [16,18]. Thus, when a mutant arises uniformly at random at each vertex, a mutant with a 10% fitness advantage over the wild-type has approximately the same chance of fixing in the Star population as a mutant with a 21% fitness advantage in the well-mixed population. Conversely, simple one-rooted population structures are an example of suppressors of selection and they remove the dependence of the fixation probability on r [1]. Under uniform initialization, amplification is straightforward to define, as p(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 p(r) satisfies p(r) < (1 - r-1)I(1 - r-n) for r less than 1 and p(r)> (1 - r-1)/ (1 - r- ") 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 p(1) < 1/ n with equality if and only if the population structure is isothermal (equivalently T1 is constant in j or Wa 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 p(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 p(r) as r oo is 1, just as in the well-mixed population. However, some structures that appear to be amplifiers have lirn,-.co p(r)=(zr - 1)/n (see electronic supplementary material, corollary 4.5). This implies that though they may amplify for small values of r, there is some r such that p(r) < (1 — r-1)/(1 — r—"). 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 p(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 1 \ (2.3) f (r) I rti ' wheref : [1, co) —. [1, oo) is a non-decreasing function. We call f the implied scale of fitness (where we interpret 1/oo = 0). In the case of the Star with uniform initialization, the implied scale of fitnessf has been distorted, as f : r r2, (2.4) and thus, the Star is an amplifier as f(r) =r2 > 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 EFTA01202580  Downloaded from http://rspa.royalsocietypublishing.org/ on September 3, 2015 r> 1, and suppressing population structures have an implied scale of fitness such thatf (r) < r for all r > 1. We require thatf(1) =1as 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 rspa.royalsodetypublishing.org Proc R. Soc A 471: 20150114 to 1(as p is non-negative and non-decreasing), it suffices to consider r > 1in 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 11,6,22,271, 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 161. Formally, let Q (GnA )keti be a sequence of graphs such that m is a strictly increasing sequence of natural numbers. Often we set nk := k. Fix an initialization vector v, then define fi t (r):= (1- p' (r))-t. The sequence g is called a v-amplifier if lim inff'd (r)> r, (2.5) k—froo for r > 1and lim supa (r) = liminfg (r) = 1, (2.6) k_.00 k—..co "I for r < 1. Suppressors are defined similarly with the inequality in (2.5) reversed and the infimum replaced with the supremum. We use the lim inf and lim sup to avoid the technical question of the existence of the limit; if a limit does exist, then we denote it asfa(r) := limk„,p6 a (r). (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 ady-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 g is called a bounded wamplifier if it is a v-amplifier and limsupk_..„,faii(r)< r + c for some constant c > 0 (figure 2). Theorem 2.1. For any sequence of graphs g, we have limsupfa (r) < r + 1, (2.7) 00 • and hence the only amplifiers under adversarial initialization are bounded amplifiers. EFTA01202581  Downloaded from httpitrspa.royalsocietypublishing.org/ on September 3.2015 (b) rspasoyalsocietypublishing.org Prot R. Soc. A 471: 20150114 of r r Figure 2. The implied scale of fitness asks how fitness would have to be distorted to produce the same fixation probability in the well-mixed population. Population structure can distort the implied scale of fitness, and these distortions can be used to classify population structures. (a) The regions that classify the functions they contain and (b) examples of different implied scales of fitness: ti° and ? are amplifiers, 2t/(r + 1) is a suppressor and r and 10? /(t2 + 9) are neither, where the corresponding graphs are the Superstar, the Star, the first graph defined in electronic supplementary material, remark 2.4, the well-mixed population, and the second graph defined in electronic supplementary material, remark 2.4, respectively. The argument for theorem 2.1 is simple but not necessarily optimal (see electronic supplementary material, lemma 3.1). Given any graph Gm, consider the vertex i := argmaxi i „Tj that has the maximum temperature. We show po i (r) < 1 (2.8) r +I Hence/Lk (r) a r+ I, and so if/e(r) exists then/(r) ≤4(r) c r+ 1. (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 unit-amplifier, is in fact a suppressor for temperature initialization. Contrastingly, we show that the Looping Star is both a unit-amplifier and a temp- amplifier. We set nk := k + 1. Moreover, we consider graphs with n + 1 vertices here instead of n, as it is more convenient for computations. For x e (0,1) and y e (0,1), define the graph Gn+1(x,y) by its weight matrix, 1_y y tt x 1 —x 0 0 0 1- x 0 Wn+1 (2.9) x 0 1— x 0 x 0 0 1 — xi Intuitively, G,,cgx,y) represents a Star graph where the centre is surrounded by ti leaves; the centre has a self-loop of weight I —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 EFTA01202582  Downloaded from hltp:.".1spa.royalsocietypublishing.orgt on September 3. 2015 (a) 1.0 (b) 0.8 rspa.royalsodetypublishing.org Proc R. Soc A 471: 20150W 0.6 0A 0.2 2 4 6 8 10 0 2 4 6 8 10 r r Figure 3. While the Star amplifies when the Moran process is initialized uniformly at random, it performs very poorly when the process is initialized proportional to temperature. Modifying the Star with self-loops produces an amplifier for mutants initialized uniformly at random and proportional to temperature. (a) Pertains to a Star of size 20, whereas (b) a Looping Star of size 20. We plot the fixation probabilities of both structures under temperature and uniform initializations. The solid black line is (1 — r-1)/(1 - r—°) and the dashed bladdine is (1 — r-1)/(1 — r-21. (Online version in colour.) Star graph, is obtained as Gm.' (1, 1), where there are no self-loops and it is known that Pral(r) "A " (1 - r-2 )/(1 - r-1"). Thus, for (S,H-1)n>a, denoted by S, we haveft(r)= r2 and hence the sequence of Star graphs is a mil-amplifier. However, under temperature initialization this property is reversed due to the extreme temperature differences between the centre and leaves in the Star (see electronic supplementary material, remark 4.3). Theorem 2.2. The Star is a temp-suppressor. Infact, lira„,,,,pr:(r)= 0 and so frP(r)= 1. (2.10) 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 := Gn+101-1, and the sequence L := (Lac' )„EN. Theorem 2.3. The Looping Star is simultaneously a unit•amplifier and temp-amplifier. Infact, lint prP (r) lim (r) = ph4.02) (2.11) n—nx, n—o oo and so fr i(r)=fr(r)= r2. (2.12) Thus, the fixation probability for the Looping Star graphs in the limit is like the well-mixed population with fitness r2 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. EFTA01202583  Downloaded from http://rspa.royalsocietypublishing.orar on September 3.2015 Table1. Examples of different implied scales of fitness with our results shown in bold. classification rspa.royalsocietypublishing.org Proc R. Soc A 471: 20150114 well-mixed (or any isothermal) unit • well-mixed (or any isothermal) temp I star unit 12 unit-amplifier star temp 1 temp-maximal suppressor k-Superstar (with k oc) unit rim (where k(n) —* '3) unit-maximal amplifier well-mixed with downstream unit 2r /(r +1) unit-suppressor star with downstream unit 10r2/(r2 + 9) S rooted population unit 1 unit-maximal suppressor rooted population temp 1 temp-maximal suppressor Looping Star unif r2 unif-amplifier Looping Star temp r2 temp-amplifier any structure adv <r 1 adv-bounded amplifier 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 amplifiersfor adversarial initialization or, equivalently,for all g and all r> 1, fe(r)< r. A further question which has been studied only in the uniform initialization case is the existence of arbitrarily strong amplifiers 11,6,311. A sequence of graphs 9 is called a maximal v-amplifier if if r.1 (Si) otherwise. Conversely, a sequence of graphs 9 is called a maximal v-suppressor if fa(r)= 1 for all 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 und-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 [41. For fixed s > 0, let 9 be a sequence of approximately isothermal graphs, so that for all non-empty S c V,,, we have awc ) ary(S) (3.2) EFTA01202584  Downloaded from http:Msparoyalsocletypubishing.o4 on September 3, 2015 where 700(5) and uPt(5) correspond to the sum of the outgoing and ingoing edges, respectively, 10 from the subset S. So by the robust isothermal theorem f41, rspa.royalsocietypublishing.org Proc R. Soc A 471: 20150114 1—r su 4 . (r)I 5 s. (3.3) 0 1— r Thus, Ifaf(r) — < O(r2s), which implies that, for small e and r, the implied scale of fitness is approximately linear. In particular, ifs„ is allowed to depend on it such that sa —. 0, thenj(r) = r. 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"1, where the Markov chain keeps track whether the centre is a wild-type or a mutant and how many of the it 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 (1 — r2)(n3x2 + (n + 1)nrxy + y2) PG.4;01 7 (4.1) (n + 1)(nrx + y)((nrx + y)(a: t r(nx + ry)) and temp (1— r2)(n3(1 — x)x2 + ttlxy(r + x)+ nxy(r + y) — (y —1)9) (4.2) +1)(nrx + y)((nn + y)(:1 --Ailt+q) n r(nx + ry)) From the above we derive theorems 2.2 and 23 by setting x = 1/n and y =1/0 and taking the limit as n oo (see electronic supplementary material, subsection 4.2). Data accessibility. Electronic supplements material accompanies the article online. Audio's contributions. B.A., K.C. and M. 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. 511407-N23 (RISE). M. gratefully acknowledges support from the John Templeton Foundation. References 1. Nowak MA. 2006 Evolutionary dynamics: exploring the equations of life. Cambridge,MA: Belknap Press of Harvard University Press. EFTA01202585  Downloaded from http://rsparoyalsocletypubishinn.orgf on September 3, 2015 2. Patwa Z, Wahl LM. 2008 The fixation probability of beneficial mutations. f. R. Soc. Interface 5, 1279-1289. (doi:10.1098/rsif.2008.0248) 3. Nowak MA, Sasaki A, Taylor C, Fudenberg D. 2004 Emergence of cooperation and rspanyalsodetypublishing.org Proc. R. Soc. A 471: 20150114 evolutionary stability in finite populations. Nature 428, 646-650. (doi:10.1038/nature02414) 4. Adlam B, Nowak MA. 2014 Universality of fixation probabilities in randomly structured populations. Sci. Rep. 4, 6692. (doi:10.1038/srep06692) 5. Fudenberg D, Nowak MA, Taylor C, Imhof LA. 2006 Evolutionary game dynamics in finite populations with strong selection and weak mutation. Theor. Popul. Biol. 70, 352-363. (doi:10.1016/j.tpb.2006.07.006) 6. Lieberman E, Hauert C, Nowak MA. 2005 Evolutionary dynamics on graphs. Nature 433, 312416. (doi:10.1038/naturo03211.1) 7. Imhof LA, Nowak MA. 2006 Evolutionary game dynamics in a Wright-Fisher process. J. Math. Biol. 52, 667-681. (doi:10.1007/s00285.005-1B69-8) 8. Traulsen A, Pacheco JM, Nowak MA. 2007 Pairwise comparison and selection temperature in evolutionary game dynamics. J. Theor. Biol. 246,522-529. (doi:10.1016/j4tbi.2007.01.002) 9. Tamita CE, Ohtsuki H, Antal T, Fu F, Nowak MA. 2009 Strategy selection in structured populations. J. Theor. Biol. 259, 570-581. (doi:10.1016/j.jtbi.2009.03.035) 10. Masuda N, Ohtsuki H. 2009 Evolutionary dynamics and fixation probabilities in directed networks. New J. Phys. 11,033012. (doi:10.1088/1367-2630/11/3/033012) 11. Moran PAP. 1962 The statistical processes of evolutionary theory. Oxford, UK: Oxford University Press. 12. Nowak MA, Michor F, lwasa Y. 2003 The linear process of somatic evolution. Proc. Nall Acad. Sri. USA 100, 14966-14969. (doi:10.1073/pnas.2535419100) 13. Kaveh K, Komarova NL, Kohandel M. 2015 The duality of spatial death-birth and birth- death processes and limitations of the isothermal theorem. R. Soc. open sci. 2, 140465. (doi:10.1098/rsos.140465) 14. Maruyama T. 1974 A Markov process of gene frequency change in a geographically structured population. Genetics 76, 367-377. 15. Maruyama T. 1974 A simple proof that certain quantities are independent of the geographical structure of population. Theor. Papa Biol. 5, 148-154. (doi:10.1016/0040-5809(74)90037-9) 16. Broom M, Rychtif J. 2008 An analysis of the fixation probability of a mutant on special classes of non-directed graphs. Proc. R. Soc. A 464, 2609-2627. (doi:10.1098/rspa.2008.0058) 17. Houchmandzadeh B, Vallade M. 2011 The fixation probability of a beneficial mutation in a geographically structured population. New I. Plays. 13, 073020. (doi:10.1088/1367-2630/ 13/7/073020) 18. Monk T, Green P, Paulin M. 2014 Martingales and rotation probabilities of evolutionary graphs. Pmc. R. Soc. A 470, 20130730. (doi:10.1098/rspa.2013.0730) 19. Levin SA, Paine RT. 1974 Disturbance, patch formation, and community structure. Proc. NMI Acad. Sri. USA 71, 2744-2747. (doi:10.1073/pnas.71.7.2744) 20. Levin SA. 1976 Population dynamic models in heterogeneous environments. Altritl. Rev. £cot. Syst. 7, 287410. (doi:10.1146/annurev.es.07.110176.001443) 21. Durrett R, Levin SA. 1994 Stochastic spatial models: a user's guide to ecological applications. Phil. Thins. R. Soc. Land. B 343, 329-350. (doi:10.1098/rstb.1994.0028) 22. Frean M, Rainey PB, Traulsen A. 2013 The effect of population structure on the rate of evolution. Proc. R. Soc. B 280, 20130211. (doi:10.1098/rspb.2013.0211) 23. Barton N. 1993 The probability of fixation of a favoured allele in a subdivided population. Genet. Res. 62,149-157. (doi:10.1017/50016672300031748) 24. Whitlock M. 2003 Fixation probability and time in subdivided populations. Genetics 164, 767-779. 25. Allen B, Sample C, Dementieva YA, Medeiros RC, Paoletti C, Nowak MA. 2014 The molecular dock of neutral evolution can be accelerated or slowed by asymmetric spatial structure. PLoS Comput. Biol. 11, e1004108. (doi:10.1371/jourrtal.pcbi.1004108) 26. Antal T, Redner S, Sood V. 2006 Evolutionary dynamics on degree-heterogeneous graphs. Phys. Rev. Lett. 96, 188104. (doi:10.1103/ PhysRevLett.96.188104) 27. Hindersin L, Traulsen A. 2014 Counterintuitive properties of the fixation time in network- structured populations. J. R. Soc. Interface 11,20140606. (doi:10.1098/rsif.2014.0606) 28. Hindersin L, Traulsen A 2015 Almost all random graphs are amplifiers of selection for birth-death dynamics, but suppressors of selection for death-birth dynamics. (http://andv.org/abs/1504.03832). EFTA01202586  Downloaded from http://rsparoyalsocietypubtishino.oroi on September 3, 2015 29. Voorhees B. 2013 Birth-death fixation probabilities for structured populations. Proc. R. Soc. A 469, 20120248. (doi:10.1098/rspa.2012.0248) 30. Voorhees B, Murray A. 2013 Fixation probabilities for simple digraphs. Proc. R. Soc. A 469, rspa.royalsocietypublishing.org Proc. R. Soc. A 471: 20150114 20120676. (doi:10.1098/rspa.2012.0676) 31. Diaz J, Goldberg LA, Mertzios GB, Richerby D, Sema M, Spirakis PG. 2013 On the fixation probability of superstars. Pmc. R. Soc. A 469, 20130193. (doi:10.1098/rspa.2013.0193) 32. Jamieson•Lane A, Hauer! C. 2013 Fixation probabilities on superstars, revisited and revised. (http://arxiv.org/abs/1312.6M) 33. Ohtsuki H, Pacheco JM, Nowak MA. 2007 Evolutionary graph theory: breaking the symmetry between interaction and replacement. J. Theor. Biol. 246, 681-694. (doi:10.1016/j. jtbi.2007.01.024) 34. Helbing D, Szolnoki A, Pere M, Szabo G. 2010 Punish, but not too hard: how costly punishment spreads in the spatial public goods game. New I. Phys. 12, 083005. (doi:10.1088/ 1367-2630/12/8/083005) 35. Helbing D, Szolnoki A, Pere M, Szab6 G. 2010 Evolutionary establishment of moral and double moral standards through spatial interactions. PLoS Comput. Biol. 6, e1000758. (doi:10.1371/joumal.pcbi.1000758) 36. Wu B, Thou D, Fu F, Luo Q, Wang L, Traulsen A. 2010 Evolution of cooperation on stochastic dynamical networks. PLoS ONE 5, e11187. (doi:10.1371/joumal.pone.0011187) 37. Fu F, Liu L-H, Wang L. 2007 Evolutionary Prisoner's Dilemma on heterogeneous Newman- Watts small-world network. Em'. Phys. J. B 56, 367-372. (doi:10.1140/epjb/e2007-00124-5) 38. Broom M, Hadjichrysanthou C, Rychtat J. 2010 Evolutionary games on graphs and the speed of the evolutionary process. Pmc. R. Soc. A 466, 1327-1346. (doi:10.1098/rspa.2009.0487) 39. Ohtsuki H, Nowak MA. 2006 Evolutionary games on cycles. Proc. R. Soc. B 273, 2249-2256. (doi:10.1098/rspb.2006.3576) 40. Nowak MA, Tamita CE, Antal T. 2010 Evolutionary dynamics in structured populations. Phil. Trans. R. Soc. B 365, 19-30. (doi:10.1098/rstb.2009.0215) 41. Fu F, Wang L, Nowak MA, Hauert C. 2009 Evolutionary dynamics on graphs: efficient method for weak selection. Phys. Rev. E 79, 46707. (doi:10.1103/PhysRevE.79.046707) 42. Nowak MA, May RM. 1992 Evolutionary games and spatial chaos. Nature 359, 826-829. (doi:10.1038/359826a0) 43. Ohtsuki H, Hauert