Search

Many evolving ecosystems have spatial structures that can be conceptualized as networks, with nodes representing individuals or homogeneous subpopulations and links the patterns of interaction and replacement between them. Prior models of evolution on networks do not take ecological niche differences and eco-evolutionary interplay into account. Here, we combine a resource competition model with evolutionary graph theory to study how heterogeneous topological structure shapes evolutionary dynamics under global frequency-dependent ecological interactions. We find that the addition of ecological competition for resources can produce a reversal of roles between amplifier and suppressor networks for deleterious mutants entering the population. Moreover, we show that this effect is a non-linear function of ecological niche overlap and discuss intuition for the observed dynamics using simulations and analytical approximations.

This paper introduces evolutionary game theory as an analysis tool to study the evolution of the cooperative behavior of nodes in the opportunistic network. At the same time, considering the spatial distribution of nodes in the opportunistic network and the corresponding cooperative interaction relationship, the evolutionary graph theory is further applied to study the cooperative behavior in the context of considering the network space. In the collaboration model of this article, the vertices in the evolutionary graph theory are used to represent the nodes in the network, and the edges in the graph represent that the node pairs are within the communication range of each other. The node will play a game with neighboring nodes according to the payout matrix. Through repeated games between nodes, the network reaches a relatively stable final state, and the distribution of nodes with different behaviors in the final state of the network is checked. By adjusting the network parameters, we can analyze the distribution and evolution of cooperation in the network, and study the stability of the network. We realize the credible collaborative evolutionary game model by building a comprehensive simulation platform and verify its effectiveness and scalability. We design and implement an evolutionary game model independent of routing protocols, so that the model can be quickly deployed in traditional routing protocols. Subsequently, simulations verified that the reputation model played a role in guiding nodes to actively participate in network collaboration during the collaborative evolution process. And the greater the strength of the reputation incentive mechanism, the better the effect of the evolutionary model. The evolution model is deployed in multiple routing protocols, verifying that the model can play a role in different routing protocols. In addition, the evolution model can also play a role in different network environments and has good scalability.

The effect of population structure on evolutionary dynamics is a long-lasting research topic in evolutionary ecology and population genetics. Evolutionary graph theory is a popular approach to this problem, where individuals are located on the nodes of a network and can replace each other via the links. We study the effect of complex network structure on the fixation probability, but instead of networks of individuals, we model a network of sub-populations with a probability of migration between them. We ask how the structure of such a meta-population and the rate of migration affect the fixation probability. Many of the known results for networks of individuals carry over to meta-populations, in particular for regular networks or low symmetric migration probabilities. However, when patch sizes differ we find interesting deviations between structured meta-populations and networks of individuals. For example, a two patch structure with unequal population size suppresses selection for low migration probabilities.

Whether the spatial arrangement of a population influences adaptive evolution has been a long-standing question in population genetics. In contrast to standard population genetic models, evolutionary graph theory (EGT) predicts certain topologies amplify (increase) the probability that a beneficial mutation will spread in the population relative to a well-mixed population. Here, we test these predictions empirically by tracking the fixation dynamics of an antibiotic resistant mutant under positive selection as it spreads through networks of different topologies both in vitro and in silico. We show that star-like topologies involving bi-directional dispersal between a central hub and peripheral leaves can be amplifiers of selection relative to a well-mixed network, consistent with the predictions of EGT. We further show that the mechanism responsible for amplification is the reduced probability that a rare beneficial mutant will be lost due to drift when it encounters a new patch. Our results provide the first empirical support for the prediction of EGT that spatial structure can amplify the spread of a beneficial mutation and broadens the conditions under which this phenomenon is thought to occur. We also show the importance of considering the migration rate, which is not independently adjustable in most previous models. More generally, our work underscores the potential importance of spatial structure in governing adaptive evolution by showing how the interplay between spatial structure and evolutionary forces determine the fate of a beneficial mutation. It also points the way towards using network topology to amplify the effects of weakly favoured mutations under directed evolution in industrial applications.

To design population topologies that can accelerate rates of solution discovery in directed evolution problems or in evolutionary optimization applications, we must first systematically understand how population structure shapes evolutionary outcome. Using the mathematical formalism of evolutionary graph theory, recent studies have shown how to topologically build networks of population interaction that increase probabilities of fixation of beneficial mutations, at the expense, however, of longer fixation times, which can slow down rates of evolution under elevated mutation rate. Here we find that moving beyond dyadic interactions is fundamental to explain the trade-offs between probability and time to fixation. We show that higher-order motifs, and in particular three-node structures, allow tuning of times to fixation, without changes in probabilities of fixation. This gives a near-continuous control over achieving solutions that allow for a wide range of times to fixation. We apply our algorithms and analytic results to two evolutionary optimization problems and show that the rate at which evolving agents learn to navigate their environment can be tuned near continuously by adjusting the higher-order topology of the agent population. We show that the effects of population structure on the rate of evolution critically depend on the optimization landscape and find that decelerators, with longer times to fixation of new mutants, are able to reach the optimal solutions faster than accelerators in complex solution spaces. Our results highlight that no one population topology fits all optimization applications, and we provide analytic and computational tools that allow for the design of networks suitable for each specific task.

Evolutionary graph theory investigates how spatial constraints affect processes that model evolutionary selection, e.g. the Moran process. Its principal goals are to find the fixation probability and the conditional distributions of fixation time, and show how they are affected by different graphs that impose spatial constraints. Fixation probabilities have generated significant attention, but much less is known about the conditional time distributions, even for simple graphs. Those conditional time distributions are difficult to calculate, so we consider a close proxy to it: the number of times the mutant population size changes before absorption. We employ martingales to obtain the conditional characteristic functions (CCFs) of that proxy for the Moran process on the complete bipartite graph. We consider the Moran process on the complete bipartite graph as an absorbing random walk in two dimensions. We then extend Wald’s martingale approach to sequential analysis from one dimension to two. Our expressions for the CCFs are novel, compact, exact, and their parameter dependence is explicit. We show that our CCFs closely approximate those of absorption time. Martingales provide an elegant framework to solve principal problems of evolutionary graph theory. It should be possible to extend our analysis to more complex graphs than we show here.

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., 18 pages, 8 figures

Cancer cells obtain mutations which rely on the production of diffusible growth factors to confer a fitness benefit. These mutations can be considered cooperative, and studied as public goods games within the framework of evolutionary game theory. The population structure, benefit function and update rule all influence the evolutionary success of cooperators. We model the evolution of cooperation in epithelial cells using the Voronoi tessellation model. Unlike traditional evolutionary graph theory, this allows us to implement global updating, for which birth and death events are spatially decoupled. We compare, for a sigmoid benefit function, the conditions for cooperation to be favoured and/or beneficial for well mixed and structured populations. We find that when population structure is combined with global updating, cooperation is more successful than if there were local updating or the population were well-mixed. Interestingly, the qualitative behaviour for the well-mixed population and the Voronoi tessellation model is remarkably similar, but the latter case requires significantly lower incentives to ensure cooperation., 40 Pages, 15 Figures. Accepted version

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. Supplementary Information The online version supplementary material available at 10.1007/s00285-021-01597-z.

At the core of any system of interacting entities lie evolution, its driving force of change, and a graph, encoding its structure. In this thesis we investigate how the former affects the latter, and vice versa, whereby we resort to the tools of evolutionary game theory, population dynamics, and graph theory. We begin our journey by considering evolutionary dynamics as they unfold in the absence of population structure from a deterministic and stochastic point of view, then steer to the realm of static graphs endowed with evolutionary games subject to a host of imitation processes, and, at last, stop for a while to leverage the knowledge acquired along the way to develop the modified Petford--Welsh algorithm, a highly scalable decentralised heuristic approach to cluster detection. Picking up where we left off, we then expound on more elaborate forms of imitation dynamics by paying a visit to a plethora of models of contagion, cascade, and consensus dynamics. Soon thereafter, we leave behind the world of simple graphs, enter the domain of multilayer and evolving graphs, and examine how they co-evolve with the evolutionary processes pertaining to them. Finally, we reach our destination, where we put to use the theory that we have become acquainted with to devise a model of the flow of the news across a co-evolving graph comprised of a layer of news providers and a layer of news consumers. V središču vsakega sistema entitet v interakciji se nahajata graf, ki ponazarja njegovo strukturo, in evolucija kot gonilna sila sprememb. V tem delu raziskujemo, kakšen je njun medsebojni vpliv, pri čemer posežemo po orodjih evolucijske teorije iger, populacijske dinamike in teorije grafov. Najprej si z determinističnega in s stohastičnega vidika ogledamo, kako se evolucijska dinamika odvija, kadar populacije niso strukturirane, tik za tem v zgodbo vključimo statične grafe, podvržene evolucijskim igram in raznim procesom imitacije, in ob koncu poglavja spotoma pridobljeno znanje vpletemo v razvoj prirejenega Petford--Welshevega algoritma, decentraliziranega hevrističnega pristopa k odkrivanju gruč, ki se zlahka spopade z rastočo količino podatkov. Nato obrnemo novo stran in preidemo na bolj zapletene oblike imitacijske dinamike, pri čemer pod drobnogled vzamemo cel nabor modelov dinamike okužbe, kaskad in soglasja. Kaj kmalu opustimo obravnavo statičnih grafov in se posvetimo večplastnim in razvijajočim se grafom, kjer preučujemo njihov sorazvoj z evolucijskimi procesi, ki so jim podrejeni. Pripoved nazadnje sklenemo tako, da z uporabo teorije, s katero smo se seznanili, ustvarimo model pretoka novic po večplastnem grafu -- s plastjo ponudnikov novic in plastjo njihove publike -- ki se spreminja sočasno s potekom dinamike.

Evolutionary game theory is a powerful method for modelling animal conflicts. The original evolutionary game models were used to explain specific biological features of interest, such as the existence of ritualised contests, and were necessarily simple models that ignored many properties of real populations, including the duration of events and spatial and related structural effects. Both of these areas have subsequently received much attention. Spatial and structural effects have been considered in evolutionary graph theory, and a significant body of literature has been built up to deal with situations where the population is not homogeneous. More recently a theory of time constraints has been developed to take account of the fact that different events can take different times, and that interaction times can explicitly depend upon selected strategies, which can, in turn, influence the distribution of different opponent types within the population. Here, for the first time, we build a model of time constraint games which explicitly considers a spatial population, by considering a population evolving on an underlying graph, using two graph dynamics, birth–death and death-birth. We consider one short time scale along which frequencies of pairs and singles change as individuals interact with their neighbours, and another, evolutionary time scale, along which frequencies of strategies change in the population. We show that for graphs with large degree, both dynamics reproduce recent results from well-mixed time constraint models, including two ESSs being common in Hawk-Dove and Prisoner’s Dilemma games, but for low degree there can be marked differences. For birth–death processes the effect of the graph degree is small, whereas for death-birth dynamics there is a large effect. The general prediction for both Hawk-Dove and Prisoner’s dilemma games is that as the graph degree decreases, i.e., as the number of neighbours decreases, mixed ESS do appear. In particular, for the Prisoner’s dilemma game this means that cooperation is easier to establish in situations where individuals have low number of neighbours. We thus see that solutions depend non-trivially on the combination of graph degree, dynamics and game.

Cooperation is prevalent in nature, not only in the context of social interactions within the animal kingdom but also on the cellular level. In cancer, for example, tumour cells can cooperate by producing growth factors. The evolution of cooperation has traditionally been studied for well-mixed populations under the framework of evolutionary game theory, and more recently for structured populations using evolutionary graph theory (EGT). The population structures arising due to cellular arrangement in tissues, however, are dynamic and thus cannot be accurately represented by either of these frameworks. In this work, we compare the conditions for cooperative success in an epithelium modelled using EGT, to those in a mechanical model of an epithelium—the Voronoi tessellation (VT) model. Crucially, in this latter model, cells are able to move, and birth and death are not spatially coupled. We calculate fixation probabilities in the VT model through simulation and an approximate analytic technique and show that this leads to stronger promotion of cooperation in comparison with the EGT model.

A biologically motivated individual-based framework for evolution in network-structured populations is developed that can accommodate eco-evolutionary dynamics. This framework is used to construct a network birth and death model. The evolutionary graph theory model, which considers evolutionary dynamics only, is derived as a special case, highlighting additional assumptions that diverge from real biological processes. This is achieved by introducing a negative ecological feedback loop that suppresses ecological dynamics by forcing births and deaths to be coupled. We also investigate how fitness, a measure of reproductive success used in evolutionary graph theory, is related to the life-history of individuals in terms of their birth and death rates. In simple networks, these ecologically motivated dynamics are used to provide new insight into the spread of adaptive mutations, both with and without clonal interference. For example, the star network, which is known to be an amplifier of selection in evolutionary graph theory, can inhibit the spread of adaptive mutations when individuals can die naturally.

Evolutionary graph theory models the effects of natural selection and random drift on structured populations of competing mutant and non-mutant individuals. Recent studies have found that fixation times in such systems often have right-skewed distributions. Little is known, however, about how these distributions and their skew depend on mutant fitness. Here we calculate the fitness dependence of the fixation-time distribution for the Moran Birth-death process in populations modeled by two extreme networks: the complete graph and the one-dimensional ring lattice, obtaining exact solutions in the limit of large network size. We find that with non-neutral fitness, the Moran process on the ring has normally distributed fixation times, independent of the relative fitness of mutants and non-mutants. In contrast, on the complete graph, the fixation-time distribution is a fitness-weighted convolution of two Gumbel distributions. When fitness is neutral the fixation-time distribution jumps discontinuously and becomes highly skewed on both the complete graph and the ring. Even on these simple networks, the fixation-time distribution exhibits rich fitness dependence, with discontinuities and regions of universality. Extensions of our results to two-fitness Moran models, times to partial fixation, and evolution on random networks are discussed., Comment: 16 pages, 7 figures, 1 table; SM: 8 pages

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.

We consider a finite population of individuals that can move through a structured environment using our previously developed flexible 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 effect 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 effect. Unusually, we find that the evolutionary dynamics used does not have a significant effect on these results.

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., 9 pages, 4 figures

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., eLife digest When one child goes to school with a throat infection, many of his or her classmates will often start to come down with a sore throat after two or three days. A few of the children will get sick sooner, the very next day, while others may take about a week. As such, there is a distribution of incubation periods – the time from exposure to illness – across the children in the class. When plotted on a graph, the distribution of incubation periods is not the normal bell curve. Rather the curve looks lopsided, with a long tail on the right. Plotting the logarithms of the incubation periods, however, rather than the incubation periods themselves, does give a normal distribution. As such, statisticians refer to this kind of curve as a “lognormal distribution". Remarkably, many other, completely unrelated, diseases – like typhoid fever or bladder cancer – also have approximately lognormal distributions of incubation periods. This raised the question: why do such different diseases show such a similar curve? Working with a simple mathematical model in which chance plays a key role, Ottino-Löffler et al. calculate how long it takes for a bacterial infection or cancer cell to take over a network of healthy cells. The model explains why a lognormal-like distribution of incubation periods, modeled as takeover times, is so ubiquitous. It emerges from the random dynamics of the incubation process itself, as the disease-causing microbe or mutant cancer cell competes with the cells of the host. Intuitively, this new analysis builds on insights from the “coupon collector’s problem”: a classical problem in mathematics that describes the situation where a person collects items like baseball cards, stamps, or cartoon monsters in a videogame. If a random item arrives every day, and the collector’s luck is bad, they may have to wait a long time to collect those last few items. Similarly, in the model of Ottino-Löffler et al., the takeover time is dominated by dramatic slowdowns near the start or end of the infection process. These effects lead to an approximately lognormal distribution, with long waits, as seen in so many diseases. Ottino-Löffler et al. do not anticipate that their findings will have direct benefits for medicine or public health. Instead, they believe their results could help to advance basic research in the fields of epidemiology, evolutionary biology and cancer research. The findings might also make an impact outside biology. The term “contagion” has now become a familiar metaphor for the spread of everything from computer viruses to bank failures. This model sheds light on how long it takes for a contagion to take over a network, for a variety of idealized networks and spreading processes.

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.

Evolutionary graph theory combines evolutionary games with population structure, induced by the graph. The games used are limited to pairwise games occurring on the edges of the graph. Multiplayer games can be important in biological modelling, however, and so recently a new framework for modelling games in structured populations allowing games with arbitrary numbers of players was introduced. In this paper we develop the model to investigate the effect of population structure on the level of aggression, as opposed to a well-mixed population for two specific types of graph, using a multiplayer hawk-dove game. We find that the graph structure can have a significant effect on the level of aggression, and that a key factor is the variability of the group sizes formed to play the games; the more variable the group size, the lower the level of aggression, in general.

Evolution occurs in populations of reproducing individuals. The trajectories and outcomes of evolutionary processes depend on the structure of the population. Evolutionary graph theory is a powerful approach to studying the consequences of spatial or social population structure. The vertices of the graph represent individuals. The edges determine who interacts with whom for game payoff and who competes with whom for reproduction. Interaction and competition can be governed by the same graph or by two different graphs. In this paper, we review the basic approach for evolutionary games on graphs and provide new proofs for key results. We formalize the method of identity by descent to derive conditions for strategy selection on finite, weighted graphs. We generalize our results to nonzero mutation rates, and to the case where the interaction and competition graphs do not coincide. We conclude with a perspective of open problems and future directions.

Historically most evolutionary models have considered infinite populations with no structure. Recently more realistic evolutionary models have been developed using evolutionary graph theory, which considered the evolution of structured populations. The structures involved in these populations are typically fixed, however, and real populations change their structure over both long and short time periods. In this paper we consider the dynamics of such a population structure. The timescales involved are sufficiently short that no individuals are born or die, but the links between individuals are in a constant state of flux, being actively governed by the preferences of the members of the population. The process is modelled using a Markov chain over the possible structures. We find that under the specified process the population evolves to a closed class of structures, and we show a method to find the stationary distribution on this class. We also consider some special cases of interest.

Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described my the Moran process. Recently, this approach has been generalized in \cite{LHN} by arranging individuals on the nodes of a network. Undirected networks seem to have a smoother behavior than directed ones, and thus it is more challenging to find suppressors/amplifiers of selection. In this paper we present the first class of undirected graphs which act as suppressors of selection, by achieving a fixation probability that is at most one half of that of the complete graph, as the number of vertices increases. Moreover, we provide some generic upper and lower bounds for the fixation probability of general undirected graphs. As our main contribution, we introduce the natural alternative of the model proposed in \cite{LHN}, where all individuals interact simultaneously and the result is a compromise between aggressive and non-aggressive individuals. That is, the behavior of the individuals in our new model and in the model of \cite{LHN} can be interpreted as an "aggregation" vs. an "all-or-nothing" strategy, respectively. We prove that our new model of mutual influences admits a \emph{potential function}, which guarantees the convergence of the system for any graph topology and any initial fitness vector of the individuals. Furthermore, we prove fast convergence to the stable state for the case of the complete graph, as well as we provide almost tight bounds on the limit fitness of the individuals. Apart from being important on its own, this new evolutionary model appears to be useful also in the abstract modeling of control mechanisms over invading populations in networks. We demonstrate this by introducing and analyzing two alternative control approaches, for which we bound the time needed to stabilize to the "healthy" state of the system., 21 pages, 3 figures

Inspired by recent works on evolutionary graph theory, an area of growing interest in mathematical and computational biology, we present the first known examples of undirected structures acting as suppressors of selection for any fitness value $r > 1$. This means that the average fixation probability of an advantageous mutant or invader individual placed at some node is strictly less than that of this individual placed in a well-mixed population. This leads the way to study more robust structures less prone to invasion, contrary to what happens with the amplifiers of selection where the fixation probability is increased on average for advantageous invader individuals. A few families of amplifiers are known, although some effort was required to prove it. Here, we use computer aided techniques to find an exact analytical expression of the fixation probability for some graphs of small order (equal to $6$, $8$ and $10$) proving that selection is effectively reduced for $r > 1$. Some numerical experiments using Monte Carlo methods are also performed for larger graphs., New title, improved presentation, and further examples. Supporting Information is also included

In evolutionary processes, population structure has a substantial effect on natural selection. Here, we analyze how motion of individuals affects constant selection in structured populations. Motion is relevant because it leads to changes in the distribution of types as mutations march toward fixation or extinction. We describe motion as the swapping of individuals on graphs, and more generally as the shuffling of individuals between reproductive updates. Beginning with a one-dimensional graph, the cycle, we prove that motion suppresses natural selection for death-birth updating or for any process that combines birth-death and death-birth updating. If the rule is purely birth-death updating, no change in fixation probability appears in the presence of motion. We further investigate how motion affects evolution on the square lattice and weighted graphs. In the case of weighted graphs we find that motion can be either an amplifier or a suppressor of natural selection. In some cases, whether it is one or the other can be a function of the relative reproductive rate, indicating that motion is a subtle and complex attribute of evolving populations. As a first step towards understanding less restricted types of motion in evolutionary graph theory, we consider a similar rule on dynamic graphs induced by a spatial flow and find qualitatively similar results indicating that continuous motion also suppresses natural selection., Comment: 25 pages; final version

The classical models of evolution have been developed to incorporate structured populations using evolutionary graph theory and, more recently, a new framework has been developed to allow for more flexible population structures which potentially change through time and can accommodate multiplayer games with variable group sizes. In this paper we extend this work in three key ways. Firstly by developing a complete set of evolutionary dynamics so that the range of dynamic processes used in classical evolutionary graph theory can be applied. Secondly, by building upon previous models to allow for a general subpopulation structure, where all subpopulation members have a common movement distribution. Subpopulations can have varying levels of stability, represented by the proportion of interactions occurring between subpopulation members; in our representation of the population all subpopulation members are represented by a single vertex. In conjunction with this we extend the important concept of temperature (the temperature of a vertex is the sum of all the weights coming into that vertex; generally, the higher the temperature, the higher the rate of turnover of individuals at a vertex). Finally, we have used these new developments to consider the evolution of cooperation in a class of populations which possess this subpopulation structure using a multiplayer public goods game. We show that cooperation can evolve providing that subpopulations are sufficiently stable, with the smaller the subpopulations the easier it is for cooperation to evolve. We introduce a new concept of temperature, namely “subgroup temperature”, which can be used to explain our results.

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 sizeN, 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,AandB, 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 (implyingweak selection), we provide a formula for the expected frequency of typeAindividuals 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.

Evolution occurs in populations of reproducing individuals. The structure of a biological population affects which traits evolve. Understanding evolutionary game dynamics in structured populations is difficult. Precise results have been absent for a long time, but have recently emerged for special structures where all individuals have the same number of neighbors. But the problem of determining which trait is favored by selection in the natural case where the number of neighbors can vary, has remained open. For arbitrary selection intensity, the problem is in a computational complexity class which suggests there is no efficient algorithm. Whether there exists a simple solution for weak selection was unanswered. Here we provide, surprisingly, a general formula for weak selection that applies to any graph or social network. Our method uses coalescent theory and relies on calculating the meeting times of random walks. We can now evaluate large numbers of diverse and heterogeneous population structures for their propensity to favor cooperation. We can also study how small changes in population structure---graph surgery---affect evolutionary outcomes. We find that cooperation flourishes most in societies that are based on strong pairwise ties., 68 pages, 10 figures

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.

Recently, models of evolution have begun to incorporate structured populations, including spatial structure, through the modelling of evolutionary processes on graphs (evolutionary graph theory). One limitation of this otherwise quite general framework is that interactions are restricted to pairwise ones, through the edges connecting pairs of individuals. Yet, many animal interactions can involve many players, and theoretical models also describe such multiplayer interactions. We shall discuss a more general modelling framework of interactions of structured populations with the focus on competition between territorial animals, where each animal or animal group has a “home range” which overlaps with a number of others, and interactions between various group sizes are possible. Depending upon the behaviour concerned we can embed the results of different evolutionary games within our structure, as occurs for pairwise games such as the Prisoner's Dilemma or the Hawk–Dove game on graphs. We discuss some examples together with some important differences between this approach and evolutionary graph theory.

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.

Evolutionary game dynamics have been traditionally studied in well-mixed populations where each individual is equally likely to interact with every other individual. Recent studies have shown that the outcome of the evolutionary process might be significantly affected if the population has a non-homogeneous structure. In this paper we study analytically an evolutionary game between two strategies interacting on an extreme heterogeneous graph, the star graph. We find explicit expressions for the fixation probability of mutants, and the time to absorption (elimination or fixation of mutants) and fixation (absorption conditional on fixation occurring). We investigate the evolutionary process considering four important update rules. For each of the update rules, we find appropriate conditions under which one strategy is favoured over the other. The process is considered in four different scenarios: the fixed fitness case, the Hawk–Dove game, the Prisoner’s dilemma and a coordination game. It is shown that in contrast with homogeneous populations, the choice of the update rule might be crucial for the evolution of a non-homogeneous population.

Population structure can strongly affect evolutionary dynamics. The most general way to describe population structures are graphs. An important observable on evolutionary graphs is the probability that a novel mutation spreads through the entire population. But what drives this spread of a mutation towards fixation? Here, we propose a novel way to understand the forces driving fixation by borrowing techniques from evolutionary demography to quantify the invasion fitness and the effective population size for different graphs. Our method is very general and even applies to weighted graphs with node dependent fitness. However, we focus on analytical results for undirected graphs with node independent fitness. The method will allow to conceptually integrate evolutionary graph theory with theoretical genetics of structured populations., Author summary Evolving populations, companies, social circles are networks in which genes, resources and ideas circulate. Imagine a useful novelty is introduced in the network: a favorable mutation, a new product concept or a smart idea. Will this novelty be retained and propagated through the network or rather lost? Using tools originally devised for demographic research, we model the dynamics of the very initial spread of a useful novelty in a network. The network structure has a strong impact on these dynamics by affecting the effective network size through random effects. This effective network size, which correlates with the probability that a novelty spreads and is different from the actual size (i.e. number of nodes), varies with network structure. The effective size can even become independent of the actual network size and thus remain very small even for huge networks.

In large asexual populations, clonal interference, whereby different beneficial mutations compete to fix in the population simultaneously, may be the norm. Results extrapolated from the spread of individual mutations in homogeneous backgrounds are found to be misleading in such situations: clonal interference severely inhibits the spread of beneficial mutations. In contrast with results gained in systems with just one mutation striving for fixation at any one time, the spatial structure of the population is found to be an important factor in determining the fixation probability when there are two beneficial mutations.