Search

Evolutionary graph theory has considerably advanced the process of modelling the evolution of structured populations, which models the interactions between individuals as pairwise contests. In recent years, these classical evolution models have been extended to incorporate more realistic features, e.g. multiplayer games. A recent series of papers have developed a new evolutionary framework including structure, multiplayer interactions, evolutionary dynamics, and movement. However, so far, the developed models have mainly considered independent movement without coordinated behaviour. Although the theory underlying the framework has been developed and explored in various directions, several movement mechanisms have been produced which characterise coordinated movement, for example, herding. By embedding these newly constructed movement distributions, within the evolutionary setting of the framework, we demonstrate that certain levels of aggregation and dispersal benefit specific types of individuals. Moreover, by extending existing parameters within the framework, we are not only able to develop a general process of embedding any of the considered movement distributions into the evolutionary setting on complete graphs but also analytically produce the probability of fixation of a mutant on a complete N-sized network, for the multiplayer Public Goods and Hawk–Dove games. Also, by applying weak selection methods, we extended existing previous analyses on the pairwise Hawk–Dove Game to encompass the multiplayer version considered in this paper. By producing neutrality and equilibrium conditions, we show that hawks generally do worse in our models due to the multiplayer nature of the interactions. [ABSTRACT FROM AUTHOR]

Spatially resolved datasets are revolutionizing knowledge in molecular biology, yet are under-utilized for questions in evolutionary biology. To gain insight from these large-scale datasets of spatial organization, we need mathematical representations and modeling techniques that can both capture their complexity, but also allow for mathematical tractability. Evolutionary graph theory utilizes the mathematical representation of networks as a proxy for heterogeneous population structure and has started to reshape our understanding of how spatial structure can direct evolutionary dynamics. However, previous results are derived for the case of a single new mutation appearing in the population and the role of network structure in shaping fitness landscape crossing is still poorly understood. Here we study how network-structured populations cross fitness landscapes and show that even a simple extension to a two-mutational landscape can exhibit complex evolutionary dynamics that cannot be predicted using previous single-mutation results. We show how our results can be intuitively understood through the lens of how the two main evolutionary properties of a network, the amplification and acceleration factors, change the expected fate of the intermediate mutant in the population and further discuss how to link these models to spatially resolved datasets of cellular organization. [ABSTRACT FROM AUTHOR]

Whether and how the spatial arrangement of a population influences adaptive evolution has puzzled evolutionary biologists. Theoretical models make conflicting predictions about the probability that a beneficial mutation will become fixed in a population for certain topologies like stars, in which "leaf" populations are connected through a central "hub." To date, these predictions have not been evaluated under realistic experimental conditions. Here, we test the prediction that topology can change the dynamics of fixation both in vitro and in silico by tracking the frequency of a beneficial mutant under positive selection as it spreads through networks of different topologies. Our results provide empirical support that meta-population topology can increase the likelihood that a beneficial mutation spreads, broaden the conditions under which this phenomenon is thought to occur, and points the way toward using network topology to amplify the effects of weakly favored mutations under directed evolution in industrial applications. Lay Summary: Most natural populations are spatially structured, meaning that they are geographically subdivided and connected by migration. Whether spatial structure impacts adaptive evolution has been less clear as different theoretical approaches to modeling the spread of beneficial mutations through spatially structured populations make contrasting predictions. Our work uses evolution experiments and numerical simulations to show that spatial structure can impact the pace of adaptive evolution. Certain topologies, specifically a four-patch star with bidirectional migration through a central hub to each of three "leaf" populations, can accelerate the rate at which a beneficial mutation spreads through a population relative to an unstructured, well-mixed population. The cause of this acceleration is a reduced probability that beneficial mutations are stochastically lost when rare because they get concentrated in the central hub and then disperse outwards to the leaves. Our results offer the first experimental support for models of adaptive evolution in space based on evolutionary graph theory, may help understand the spread of invasive species or pathogens, and could be used in industrial settings to selectively enrich desired traits or biomolecules of interest. [ABSTRACT FROM AUTHOR]

Population structure has been known to substantially affect evolutionary dynamics. Networks that promote the spreading of fitter mutants are called amplifiers of selection, and those that suppress the spreading of fitter mutants are called suppressors of selection. Research in the past two decades has found various families of amplifiers while suppressors still remain somewhat elusive. It has also been discovered that most networks are amplifiers of selection under the birth-death updating combined with uniform initialization, which is a standard condition assumed widely in the literature. In the present study, we extend the birth-death processes to temporal (i.e., time-varying) networks. For the sake of tractability, we restrict ourselves to switching temporal networks, in which the network structure deterministically alternates between two static networks at constant time intervals or stochastically in a Markovian manner. We show that, in a majority of cases, switching networks are less amplifying than both of the two static networks constituting the switching networks. Furthermore, most small switching networks, i.e., networks on six nodes or less, are suppressors, which contrasts to the case of static networks. [ABSTRACT FROM AUTHOR]

Today, graph theory represents one of the most important modeling techniques in biology. One of the most important applications is in the study of metabolic networks. During metabolism, a set of sequential biochemical reactions takes place, which convert one or more molecules into one or more final products. In a biochemical reaction, the transformation of one metabolite into the next requires a class of proteins called enzymes that are responsible for catalyzing the reaction. Whether by applying differential equations or automata theory, it is not easy to explain how the evolution of metabolic networks could have taken place within living organisms. Obviously, in the past, the assembly of biochemical reactions into a metabolic network depended on the independent evolution of the enzymes involved in the isolated biochemical reactions. In this work, a simulation model is presented where enzymes are modeled as automata, and their evolution is simulated with a genetic algorithm. This protocol is applied to the evolution of glycolysis and the Krebs cycle, two of the most important metabolic networks for the survival of organisms. The results obtained show how Darwinian evolution is able to optimize a biological network, such as in the case of glycolysis and Krebs metabolic networks. [ABSTRACT FROM AUTHOR]

Populations evolve in spatially heterogeneous environments. While a certain trait might bring a fitness advantage in some patch of the environment, a different trait might be advantageous in another patch. Here, we study the Moran birth–death process with two types of individuals in a population stretched across two patches of size N , each patch favouring one of the two types. We show that the long-term fate of such populations crucially depends on the migration rate μ between the patches. To classify the possible fates, we use the distinction between polynomial (short) and exponential (long) timescales. We show that when μ is high then one of the two types fixates on the whole population after a number of steps that is only polynomial in N. By contrast, when μ is low then each type holds majority in the patch where it is favoured for a number of steps that is at least exponential in N. Moreover, we precisely identify the threshold migration rate μ⋆ that separates those two scenarios, thereby exactly delineating the situations that support long-term coexistence of the two types. We also discuss the case of various cycle graphs and we present computer simulations that perfectly match our analytical results. [ABSTRACT FROM AUTHOR]

Today, graph theory represents one of the most important modeling techniques in biology. One of the most important applications is in the study of metabolic networks. During metabolism, a set of sequential biochemical reactions takes place, which convert one or more molecules into one or more final products. In a biochemical reaction, the transformation of one metabolite into the next requires a class of proteins called enzymes that are responsible for catalyzing the reaction. Whether by applying differential equations or automata theory, it is not easy to explain how the evolution of metabolic networks could have taken place within living organisms. Obviously, in the past, the assembly of biochemical reactions into a metabolic network depended on the independent evolution of the enzymes involved in the isolated biochemical reactions. In this work, a simulation model is presented where enzymes are modeled as automata, and their evolution is simulated with a genetic algorithm. This protocol is applied to the evolution of glycolysis and the Krebs cycle, two of the most important metabolic networks for the survival of organisms. The results obtained show how Darwinian evolution is able to optimize a biological network, such as in the case of glycolysis and Krebs metabolic networks.

As ecosystems evolve, species can become extinct due to fluctuations in the environment. This leads to the evolutionary adaption known as bet-hedging, where species hedge against these fluctuations to reduce their likelihood of extinction. Environmental variation can be either within or between generations. Previous work has shown that selection for bet-hedging against within-generational variation should not occur in large populations. However, this work has been limited by assumptions of well-mixed populations, whereas real populations usually have some degree of structure. Using the framework of evolutionary graph theory, we show that through adding competition structure to the population, within-generational variation can have a significant impact on the evolutionary process for any population size. This complements research using subdivided populations, which suggests that within-generational variation is important when local population sizes are small. Together, these conclusions provide evidence to support observations by some ecologists that are contrary to the widely held view that only between-generational environmental variation has an impact on natural selection. This provides theoretical justification for further empirical study into this largely unexplored area. [ABSTRACT FROM AUTHOR]

The speed of evolution on structured populations is crucial for biological and social systems. The likelihood of invasion is key for evolutionary stability. But it makes little sense if it takes long. It is far from known what population structure slows down evolution. We investigate the absorption time of a single neutral mutant for all the 112 non-isomorphic undirected graphs of size 6. We find that about three-quarters of the graphs have an absorption time close to that of the complete graph, less than one-third are accelerators, and more than two-thirds are decelerators. Surprisingly, determining whether a graph has a long absorption time is too complicated to be captured by the joint degree distribution. Via the largest sojourn time, we find that echo-chamber-like graphs, which consist of two homogeneous graphs connected by few sparse links, are likely to slow down absorption. These results are robust for large graphs, mutation patterns as well as evolutionary processes. This work serves as a benchmark for timing evolution with complex interactions, and fosters the understanding of polarization in opinion formation.

Abstract The replicator equation is one of the fundamental tools to study evolutionary dynamics in well-mixed populations. This paper contributes to the literature on evolutionary graph theory, providing a version of the replicator equation for a family of connected networks with communities, where nodes in the same community have the same degree. This replicator equation is applied to the study of different classes of games, exploring the impact of the graph structure on the equilibria of the evolutionary dynamics.

Whether or not cooperation is favored in evolutionary games on graphs depends on the population structure and spatial properties of the interaction network. The population structure can be expressed as configurations. Such configurations extend scenarios with a single cooperator among defectors to any number of cooperators and any arrangement of cooperators and defectors on the network. For interaction networks modeled as regular graphs and for weak selection, the emergence of cooperation can be assessed by structure coefficients, which can be specified for each configuration and each regular graph. Thus, as a single cooperator can be interpreted as a lone mutant, the configuration-based structure coefficients also describe fixation properties of multiple mutants. We analyze the structure coefficients and particularly show that under certain conditions, the coefficients strongly correlate to the average shortest path length between cooperators on the evolutionary graph. Thus, for multiple cooperators fixation properties on regular evolutionary graphs can be linked to cooperator path lengths. [ABSTRACT FROM AUTHOR]

Highlights • A spreading disease model is set for a population in cellular automata. • Individuals' movements create groups where the disease is transmitted. • The average group size is a good indicator for disease spreading strength. • Based on evolutionary graph theory, the temperature of the lattice is proposed. • Temperature is also a good indicator of the disease spreading strength. Abstract Epidemiological modeling usually relies on contact between two individuals as the method for a contagious infection spread over the population. Although for some diseases the contact is indeed between only two individuals (HIV), many contagious diseases are favored to spread inside a group of individuals. For instance, consider flu: usually infected persons spread the disease on public transport, inside a room in their jobs or their homes. All these situations are related to groups of individuals that may get a disease due to the presence of an infected individual in the group. Here we use a population model structured by groups, where individuals move inside a neighborhood forming groups, where the disease may be transmitted. The population model is based on evolutionary graph theory and modeled by probabilistic cellular automata, and the disease is modeled by the classical SIR-model. A mean-field approach is presented in terms of ordinary differential equations, and population parameters are used to analyze the disease dynamic. The major results of this paper are: (1) the number of groups that an individual belongs and the lattice temperature can estimate the disease spread strength inside the population and; (2) when infected individuals do not move, this is not enough to control the disease spreading. [ABSTRACT FROM AUTHOR]

Highlights • Population structure can have a significant impact on the outcome of evolution. • Using techniques from physics we approximate evolutionary dynamics on graphs. • Existing pair approximation models are derived directly from the master equation. • Two new models are proposed to approximate the dynamics of individual nodes. • These models facilitate analysis of how initial conditions impact the process. Abstract Population structure can have a significant effect on evolution. For some systems with sufficient symmetry, analytic results can be derived within the mathematical framework of evolutionary graph theory which relate to the outcome of the evolutionary process. However, for more complicated heterogeneous structures, computationally intensive methods are required such as individual-based stochastic simulations. By adapting methods from statistical physics, including moment closure techniques, we first show how to derive existing homogenised pair approximation models and the exact neutral drift model. We then develop node-level approximations to stochastic evolutionary processes on arbitrarily complex structured populations represented by finite graphs, which can capture the different dynamics for individual nodes in the population. Using these approximations, we evaluate the fixation probability of invading mutants for given initial conditions, where the dynamics follow standard evolutionary processes such as the invasion process. Comparisons with the output of stochastic simulations reveal the effectiveness of our approximations in describing the stochastic processes and in predicting the probability of fixation of mutants on a wide range of graphs. Construction of these models facilitates a systematic analysis and is valuable for a greater understanding of the influence of population structure on evolutionary processes. [ABSTRACT FROM AUTHOR]

We consider a finite population of individuals that can move through a structured environment using our previously developed exible evolutionary framework. In the current paper the behaviour of the individuals follows a Markov movement model where decisions about whether they should stay or leave depends upon the group of individuals they are with at present. The interaction between individuals is modelled using a public goods game. We demonstrate that cooperation can evolve when there is a cost associated with movement. Combining the movement cost with a larger population size has a positive e ect on the evolution of cooperation. Moreover, increasing the exploration time, which is the amount of time an individual is allowed to explore its environment, also has a positive e ect. Unusually, we find that the evolutionary dynamics used does not have a signiFicant e ect on these results. [ABSTRACT FROM AUTHOR]

The incubation period for typhoid, polio, measles, leukemia and many other diseases follows a right-skewed, approximately lognormal distribution. Although this pattern was discovered more than sixty years ago, it remains an open question to explain its ubiquity. Here, we propose an explanation based on evolutionary dynamics on graphs. For simple models of a mutant or pathogen invading a network-structured population of healthy cells, we show that skewed distributions of incubation periods emerge for a wide range of assumptions about invader fitness, competition dynamics, and network structure. The skewness stems from stochastic mechanisms associated with two classic problems in probability theory: the coupon collector and the random walk. Unlike previous explanations that rely crucially on heterogeneity, our results hold even for homogeneous populations. Thus, we predict that two equally healthy individuals subjected to equal doses of equally pathogenic agents may, by chance alone, show remarkably different time courses of disease.

The fixation probability of a mutant in the evolutionary dynamics of Moran process is calculated by the Monte-Carlo method on a few families of clique-based graphs. It is shown that the complete suppression of fixation can be realized with the generalized clique–wheel graph in the limit of small wheel–clique ratio and infinite size. The family of clique–star is an amplifier, and clique-arms graph changes from amplifier to suppressor as the fitness of the mutant increases. We demonstrate that the overall structure of a graph can be more important to determine the fixation probability than the degree or the heat heterogeneity. The dependence of the fixation probability on the position of the first mutant is discussed. [ABSTRACT FROM AUTHOR]

The theoretical investigation of how spatial structure affects the evolution of social behavior has mostly been done under the assumption that parent-offspring strategy transmission is perfect, i.e., for genetically transmitted traits, that mutation is very weak or absent. Here, we investigate the evolution of social behavior in structured populations under arbitrary mutation probabilities. We consider populations of fixed size N , structured such that in the absence of selection, all individuals have the same probability of reproducing or dying (neutral reproductive values are the all same). Two types of individuals, A and B , corresponding to two types of social behavior, are competing; the fidelity of strategy transmission from parent to offspring is tuned by a parameter μ . Social interactions have a direct effect on individual fecundities. Under the assumption of small phenotypic differences (implying weak selection), we provide a formula for the expected frequency of type A individuals in the population, and deduce conditions for the long-term success of one strategy against another. We then illustrate our results with three common life-cycles (Wright-Fisher, Moran Birth-Death and Moran Death-Birth), and specific population structures (graph-structured populations). Qualitatively, we find that some life-cycles (Moran Birth-Death, Wright-Fisher) prevent the evolution of altruistic behavior, confirming previous results obtained with perfect strategy transmission. We also show that computing the expected frequency of altruists on a regular graph may require knowing more than just the graph's size and degree. [ABSTRACT FROM AUTHOR]

Natural selection is usually studied between mutants that differ in reproductive rate, but are subject to the same population structure. Here we explore how natural selection acts on mutants that have the same reproductive rate, but different population structures. In our framework, population structure is given by a graph that specifies where offspring can disperse. The invading mutant disperses offspring on a different graph than the resident wild-type. We find that more densely connected dispersal graphs tend to increase the invader's fixation probability, but the exact relationship between structure and fixation probability is subtle. We present three main results. First, we prove that if both invader and resident are on complete dispersal graphs, then removing a single edge in the invader's dispersal graph reduces its fixation probability. Second, we show that for certain island models higher invader's connectivity increases its fixation probability, but the magnitude of the effect depends on the exact layout of the connections. Third, we show that for lattices the effect of different connectivity is comparable to that of different fitness: for large population size, the invader's fixation probability is either constant or exponentially small, depending on whether it is more or less connected than the resident.

The Moran process on graphs is a popular model to study the dynamics of evolution in a spatially structured population. Exact analytical solutions for the fixation probability and time of a new mutant have been found for only a few classes of graphs so far. Simulations are time-expensive and many realizations are necessary, as the variance of the fixation times is high. We present an algorithm that numerically computes these quantities for arbitrary small graphs by an approach based on the transition matrix. The advantage over simulations is that the calculation has to be executed only once. Building the transition matrix is automated by our algorithm. This enables a fast and interactive study of different graph structures and their effect on fixation probability and time. We provide a fast implementation in C with this note ( Hindersin et al., 2016 ). Our code is very flexible, as it can handle two different update mechanisms (Birth–death or death–Birth), as well as arbitrary directed or undirected graphs. [ABSTRACT FROM AUTHOR]

We consider the Moran process in a graph called the "star" and obtain the asymptotic expression for the fixation probability of a single mutant when the size of the graph is large. The expression obtained corrects the previously known expression announced in reference [E Lieberman, C Hauert, and MA Nowak. Evolutionary dynamics on graphs. Nature, 433(7023):312-316, 2005] and further studied in [M. Broom and J. Rychtar. An analysis of the fixation probability of a mutant on special classes of non-directed graphs. Proc. R. Soc. A-Math. Phys. Eng. Sci., 464(2098):2609-2627, 2008]. We also show that the star graph is an accelerator of evolution, if the graph is large enough. [ABSTRACT FROM AUTHOR]

The structure of a population strongly influences its evolutionary dynamics. In various settings ranging from biology to social systems, individuals tend to interact more often with those present in their proximity and rarely with those far away. A common approach to model the structure of a population is evolutionary graph theory. In this framework, each graph node is occupied by a reproducing individual. The links connect these individuals to their neighbours. The offspring can be placed on neighbouring nodes, replacing the neighbours-or the progeny of its neighbours can replace a node during the course of ongoing evolutionary dynamics. Extending this theory by replacing single individuals with subpopulations at nodes yields a graph-structured metapopulation. The dynamics between the different local subpopulations is set by an update mechanism. There are many such update mechanisms. Here, we classify update mechanisms for structured metapopulations, which allows to find commonalities between past work and illustrate directions for further research and current gaps of investigation.

Recently, the study of structured populations using models of evolutionary processes on graphs has begun to incorporate a more general type of interaction between individuals, allowing multi-player games to be played among the population. In this paper, we develop a birth-death dynamics for use in such models and consider the evolution of populations for special cases of very small graphs where we can easily identify all of the population states and carry out exact analyses. To do so, we study two multi-player games, a Hawk-Dove game and a public goods game. Our focus is on finding the fixation probability of an individual from one type, cooperator or defector in the case of the public goods game, within a population of the other type. We compare this value for both games on several graphs under different parameter values and assumptions, and identify some interesting general features of our model. In particular there is a very close relationship between the fixation probability and the mean temperature, with high temperatures helping fitter individuals and punishing unfit ones and so enhancing selection, whereas low temperatures give a levelling effect which suppresses selection. [ABSTRACT FROM AUTHOR]

Population structures can be crucial determinants of evolutionary processes. For the Moran process on graphs certain structures suppress selective pressure, while others amplify it ( Lieberman et al., 2005 ). Evolutionary amplifiers suppress random drift and enhance selection. Recently, some results for the most powerful known evolutionary amplifier, the superstar, have been invalidated by a counter example ( Díaz et al., 2013 ). Here we correct the original proof and derive improved upper and lower bounds, which indicate that the fixation probability remains close to 1 − 1 / ( r 4 H ) for population size N → ∞ and structural parameter H ⪢ 1 . This correction resolves the differences between the two aforementioned papers. We also confirm that in the limit N , H → ∞ superstars remain capable of eliminating random drift and hence of providing arbitrarily strong selective advantages to any beneficial mutation. In addition, we investigate the robustness of amplification in superstars and find that it appears to be a fragile phenomenon with respect to changes in the selection or mutation processes. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In 2012 Broom and Rychtar developed a new framework to consider the evolution of a population over a non-homogeneous underlying structure, where fitness depends upon multiplayer interactions amongst the individuals within the population played in groups of various sizes (including one). This included the independent model, and as a special case the territorial raider model, which has been considered in a series of subsequent papers. Here individuals are based upon the vertex of a graph but move to interact with their neighbours, sometimes meeting in large groups. The most important single property of such populations is the fixation probability, the probability of a single mutant completely replacing the existing population. In a recent paper we considered the fixation probability for the Birth Death Birth (BDB) dynamics for three games, a Public Goods game, the Hawk–Dove game and for fixed fitnesses for a large number of randomly generated graphs, in particular seeing if important underlying graph properties could be used as predictors. We found two good predictors, temperature and mean group size, but some interesting and unusual features for one type of graph, Barabasi–Albert graphs. In this paper we use a regression analysis to investigate (the usual) three alternative evolutionary dynamics (BDD, DBB, DBD) in addition to the original BDB. In particular, we find that the dynamics split into two pairs, BDB/DBD and BDD/DBB, each of which give essentially the same results and found a good fit to the data using a quadratic regression involving the above two variables. Further we find that temperature is the most important predictor for the Hawk–Dove game, whilst for the Public Goods game the group size also plays a key role, and is more important than the temperature for the BDD/DBB dynamics. • A framework is used for the evolution of a population over a non-homogeneous structure. • The temperature and mean group size are good predictors for the fixation probability. • This is still true for the three other evolutionary dynamics used in this paper. • A regression analysis split the regressions into two pairs BDB/DBD and BDD/DBB. • These pairs gave essentially the same results finding a good fit to the data. [ABSTRACT FROM AUTHOR]

The emergence of cooperation is a central question in evolutionary biology. Microorganisms often cooperate by producing a chemical resource (a public good) that benefits other cells. The sharing of public goods depends on their diffusion through space. Previous theory suggests that spatial structure can promote evolution of cooperation, but the diffusion of public goods introduces new phenomena that must be modeled explicitly. We develop an approach where colony geometry and public good diffusion are described by graphs. We find that the success of cooperation depends on a simple relation between the benefits and costs of the public good, the amount retained by a producer, and the average amount retained by each of the producer’s neighbors. These quantities are derived as analytic functions of the graph topology and diffusion rate. In general, cooperation is favored for small diffusion rates, low colony dimensionality, and small rates of decay of the public good.

Intransitive competition occurs when competing strategies cannot be listed in a hierarchy, but rather form loops—as in the game rock–paper–scissors. Due to its cyclic competitive replacement, competitive intransitivity promotes strategy coexistence, both in rock–paper–scissors and in higher-richness communities. Previous work has shown that this intransitivity-mediated coexistence is strongly influenced by spatially explicit interactions, compared to when populations are well mixed. Here, we extend and broaden this line of research and examine the impact on coexistence of intransitive competition taking place on a continuum of small-world networks linking spatial lattices and regular random graphs. We use simulations to show that the positive effect of competitive intransitivity on strategy coexistence holds when competition occurs on networks toward the spatial end of the continuum. However, in networks that are sufficiently disordered, increasingly violent fluctuations in strategy frequencies can lead to extinctions and the prevalence of monocultures. We further show that the degree of disorder that leads to the transition between these two regimes is positively dependent on population size; indeed for very large populations, intransitivity-mediated strategy coexistence may even be possible in regular graphs with completely random connections. Our results emphasize the importance of interaction structure in determining strategy dynamics and diversity. [ABSTRACT FROM AUTHOR]

We study stochastic evolution of optional games on simple graphs. There are two strategies, A and B, whose interaction is described by a general payoff matrix. In addition, there are one or several possibilities to opt out from the game by adopting loner strategies. Optional games lead to relaxed social dilemmas. Here we explore the interaction between spatial structure and optional games. We find that increasing the number of loner strategies (or equivalently increasing mutational bias toward loner strategies) facilitates evolution of cooperation both in well-mixed and in structured populations. We derive various limits for weak selection and large population size. For some cases we derive analytic results for strong selection. We also analyze strategy selection numerically for finite selection intensity and discuss combined effects of optionality and spatial structure. [ABSTRACT FROM AUTHOR]

Abstract: Evolutionary graph theory has grown to be an area of intense study. Despite the amount of interest in the field, it seems to have grown separate from other subfields of population genetics and evolution. In the current work I introduce the concept of Fisher's (1930) reproductive value into the study of evolution on graphs. Reproductive value is a measure of the expected genetic contribution of an individual to a distant future generation. In a heterogeneous graph-structured population, differences in the number of connections among individuals translate into differences in the expected number of offspring, even if all individuals have the same fecundity. These differences are accounted for by reproductive value. The introduction of reproductive value permits the calculation of the fixation probability of a mutant in a neutral evolutionary process in any graph-structured population for either the moran birth–death or death–birth process. [ABSTRACT FROM AUTHOR]

Darwin suggested that the discovery of altruism between species would annihilate his theory of natural selection. However, it has not been formally shown whether between-species altruism can evolve by natural selection, or why this could never happen. Here, we develop a spatial population genetic model of two interacting species, showing that indiscriminate between species helping can be favoured by natural selection. We then ask if this helping behaviour constitutes altruism between species, using a linear-regression analysis to separate the total action of natural selection into its direct and indirect (kin selected) components. We show that our model can be interpreted in two ways, as either altruism within species, or altruism between species. This ambiguity arises depending on whether or not we treat genes in the other species as predictors of an individual's fitness, which is equivalent to treating these individuals as agents (actors or recipients). Our formal analysis, which focuses upon evolutionary dynamics rather than agents and their agendas, cannot resolve which is the better approach. Nonetheless, because a within-species altruism interpretation is always possible, our analysis supports Darwin's suggestion that natural selection does not favour traits that provide benefits exclusively to individuals of other species. [ABSTRACT FROM AUTHOR]

Evolutionary dynamics on graphs has remarkable features: For example, it has been shown that amplifiers of selection exist that-compared to an unstructured population-increase the fixation probability of advantageous mutations, while they decrease the fixation probability of disadvantageous mutations. So far, the theoretical literature has focused on the case of a single mutant entering a graph-structured population, asking how the graph affects the probability that a mutant takes over a population and the time until this typically happens. For continuously evolving systems, the more relevant case is that mutants constantly arise in an evolving population. Typically, such mutations occur with a small probability during reproduction events. We thus focus on the low mutation rate limit. The probability distribution for the fitness in this process converges to a steady state at long times. Intuitively, amplifiers of selection are expected to increase the population's mean fitness in the steady state. Similarly, suppressors of selection are expected to decrease the population's mean fitness in the steady state. However, we show that another set of graphs, called suppressors of fixation, can attain the highest population mean fitness. The key reason behind this is their ability to efficiently reject deleterious mutants. This illustrates the importance of the deleterious mutant regime for the long-term evolutionary dynamics, something that seems to have been overlooked in the literature so far.

Abstract: We present a new model of evolutionary dynamics in one-dimensional space. Individuals are arranged on a cycle. When a new offspring is born, another individual dies and the rest shift around the cycle to make room. This rule, which is inspired by spatial evolution in somatic tissue and microbial colonies, has the remarkable property that, in the limit of large population size, evolution acts to maximize the payoff of the whole population. Therefore, social dilemmas, in which some individuals benefit at the expense of others, are resolved. We demonstrate this principle for both discrete and continuous games. We also discuss extensions of our model to other one-dimensional spatial configurations. We conclude that shift dynamics in one dimension is an unusually strong promoter of cooperative behavior. [Copyright &y& Elsevier]

Abstract: Evolutionary dynamics are affected by population structure, mutation rates and update rules. Spatial or network structure facilitates the clustering of strategies, which represents a mechanism for the evolution of cooperation. Mutation dilutes this effect. Here we analyze how mutation influences evolutionary clustering on graphs. We introduce new mathematical methods to evolutionary game theory, specifically the analysis of coalescing random walks via generating functions. These techniques allow us to derive exact identity-by-descent (IBD) probabilities, which characterize spatial assortment on lattices and Cayley trees. From these IBD probabilities we obtain exact conditions for the evolution of cooperation and other game strategies, showing the dual effects of graph topology and mutation rate. High mutation rates diminish the clustering of cooperators, hindering their evolutionary success. Our model can represent either genetic evolution with mutation, or social imitation processes with random strategy exploration. [Copyright &y& Elsevier]

Abstract: We systematically study the temporal behavior of evolutionary dynamics in finite dimensional population based on evolutionary graph theory. Besides the spread of mutants, we also consider the spread of the impact of the initial mutant seed. The time-dependent behavior of these two spreading processes and their relationship are theoretically and computationally investigated. The ingredients and scaling behaviors of the interface between mutants and wild-type individuals are analyzed in detail, which have significant impact on temporal behavior of evolutionary dynamics. Since the evolutionary systems in nature are generally local and spatial, this research provides further understanding of temporal behavior in evolutionary dynamics at the theoretical level. [Copyright &y& Elsevier]

Our understanding of how cooperation can arise in a population of selfish individuals has been greatly advanced by theory. More than one approach has been used to explore the effect of population structure. Inclusive fitness theory uses genetic relatedness r to express the role of population structure. Evolutionary graph theory models the evolution of cooperation on network structures and focuses on the number of interacting partners k as a quantity of interest. Here we use empirical data from a hierarchically structured animal contact network to examine the interplay between in- dependent, measurable proxies for these key parameters. We find strong inverse correlations between estimates of r and k over three levels of social organization, suggesting that genetic relatedness and social contact structure capture similar structural information in a real population. [ABSTRACT FROM AUTHOR]

The social fine structure of a population plays a central role in ecological and evolutionary processes. Whilst many studies have investigated how morphological traits such as size affect social structure of populations, comparatively little is known about the influence of behaviours such as boldness and shyness. Using information on social interactions in a wild population of Trinidadian guppies ( Poecilia reticulata), we construct a social network. For each individual in the network, we quantify its behavioural phenotype using two measures of boldness, predator inspection tendency, a repeatable and reliably measured behaviour well studied in the context of co-operation, and shoaling tendency. We observe striking heterogeneity in contact patterns, with strong ties being positively assorted and weak ties negatively assorted by our measured behavioural traits. Moreover, shy fish had more network connections than bold fish and these were on average stronger. In other words, social fine structure is strongly influenced by behavioural trait. We assert that such structure will have implications for the outcome of selection on behavioural traits and we speculate that the observed positive assortment may act as an amplifier of selection contributing to the maintenance of co-operation during predator inspection. [ABSTRACT FROM AUTHOR]

Abstract: Evolutionary stability is a fundamental concept in evolutionary game theory. A strategy is called an evolutionarily stable strategy (ESS), if its monomorphic population rejects the invasion of any other mutant strategy. Recent studies have revealed that population structure can considerably affect evolutionary dynamics. Here we derive the conditions of evolutionary stability for games on graphs. We obtain analytical conditions for regular graphs of degree . Those theoretical predictions are compared with computer simulations for random regular graphs and for lattices. We study three different update rules: birth–death (BD), death–birth (DB), and imitation (IM) updating. Evolutionary stability on sparse graphs does not imply evolutionary stability in a well-mixed population, nor vice versa. We provide a geometrical interpretation of the ESS condition on graphs. [Copyright &y& Elsevier]

Abstract: Direct reciprocity is a mechanism for the evolution of cooperation based on the idea of repeated encounters between the same two individuals. Here we examine direct reciprocity in structured populations, where individuals occupy the vertices of a graph. The edges denote who interacts with whom. The graph represents spatial structure or a social network. For birth–death or pairwise comparison updating, we find that evolutionary stability of direct reciprocity is more restrictive on a graph than in a well-mixed population, but the condition for reciprocators to be advantageous is less restrictive on a graph. For death–birth and imitation updating, in contrast, both conditions are easier to fulfill on a graph. Moreover, for all four update mechanisms, reciprocators can dominate defectors on a graph, which is never possible in a well-mixed population. We also study the effect of an error rate, which increases with the number of links per individual; interacting with more people simultaneously enhances the probability of making mistakes. We provide analytic derivations for all results. [Copyright &y& Elsevier]

Abstract: We study evolutionary dynamics in a population whose structure is given by two graphs: the interaction graph determines who plays with whom in an evolutionary game; the replacement graph specifies the geometry of evolutionary competition and updating. First, we calculate the fixation probabilities of frequency dependent selection between two strategies or phenotypes. We consider three different update mechanisms: birth–death, death–birth and imitation. Then, as a particular example, we explore the evolution of cooperation. Suppose the interaction graph is a regular graph of degree h, the replacement graph is a regular graph of degree g and the overlap between the two graphs is a regular graph of degree l. We show that cooperation is favored by natural selection if . Here, b and c denote the benefit and cost of the altruistic act. This result holds for death–birth updating, weak-selection and large population size. Note that the optimum population structure for cooperators is given by maximum overlap between the interaction and the replacement graph (), which means that the two graphs are identical. We also prove that a modified replicator equation can describe how the expected values of the frequencies of an arbitrary number of strategies change on replacement and interaction graphs: the two graphs induce a transformation of the payoff matrix. [Copyright &y& Elsevier]