Directionality of contact networks suppresses selection pressure in evolutionary dynamics

Fixation probability in evolutionary dynamics on switching temporal networks

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.

Fixation dynamics on hypergraphs

Hypergraphs have been a useful tool for analyzing population dynamics such as opinion formation and the public goods game occurring in overlapping groups of individuals. In the present study, we propose and analyze evolutionary dynamics on hypergraphs, in which each node takes one of the two types of different but constant fitness values. For the corresponding dynamics on conventional networks, under the birth-death process and uniform initial conditions, most networks are known to be amplifiers of natural selection; amplifiers by definition enhance the difference in the strength of the two competing types in terms of the probability that the mutant type fixates in the population. In contrast, we provide strong computational evidence that a majority of hypergraphs are suppressors of selection under the same conditions by combining theoretical and numerical analyses. We also show that this suppressing effect is not explained by one-mode projection, which is a standard method for expressing hypergraph data as a conventional network. Our results suggest that the modeling framework for structured populations in addition to the specific network structure is an important determinant of evolutionary dynamics, paving a way to studying fixation dynamics on higher-order networks including hypergraphs.

Network topology and movement cost, not updating mechanism, determine the evolution of cooperation in mobile structured populations

Evolutionary models are used to study the self-organisation of collective action, often incorporating population structure due to its ubiquitous presence and long-known impact on emerging phenomena. We investigate the evolution of multiplayer cooperation in mobile structured populations, where individuals move strategically on networks and interact with those they meet in groups of variable size. We find that the evolution of multiplayer cooperation primarily depends on the network topology and movement cost while using different stochastic update rules seldom influences evolutionary outcomes. Cooperation robustly co-evolves with movement on complete networks and structure has a partially detrimental effect on it. These findings contrast an established principle from evolutionary graph theory that cooperation can only emerge under some update rules and if the average degree is lower than the reward-to-cost ratio and the network far from complete. We find that group-dependent movement erases the locality of interactions, suppresses the impact of evolutionary structural viscosity on the fitness of individuals, and leads to assortative behaviour that is much more powerful than viscosity in promoting cooperation. We analyse the differences remaining between update rules through a comparison of evolutionary outcomes and fixation probabilities.

Lost in translation? - Caveat to the application of the voter model in ecology and evolutionary biology

The voter model is a paradigmatic model of competition between alternative states within groups. Its properties have been intensively studied in statistical physics. Due to its generality, the model lends itself to various applications in ecology and evolutionary biology. I briefly review these opportunities, but call attention to a frequently occurring misinterpretation: it is often assumed that the agents in the model represent individual organisms. I argue that this assumption only holds under very specific conditions, and thus the meaning of the agents is often 'lost in translation' between physics and biology. Instead of an individual-based view, I propose that an alternative, site-based approach is more plausible. I suggest that the biological applicability of the model could further be broadened by considering the transitional states of the agents (sites) explicitly and letting the network evolve according to the agents' states.

Categorizing update mechanisms for graph-structured metapopulations

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.

The Evolution of Cooperation in Two-Dimensional Mobile Populations with Random and Strategic Dispersal

We investigate the effect of the environment dimensionality and different dispersal strategies on the evolution of cooperation in a finite structured population of mobile individuals. We consider a population consisting of cooperators and free-riders residing on a two-dimensional lattice with periodic boundaries. Individuals explore the environment according to one of the four dispersal strategies and interact with each other via a public goods game. The population evolves according to a birth–death–birth process with the fitness of the individuals deriving from the game-induced payouts. We found that the outcomes of the strategic dispersal strategies in the two-dimensional setting are identical to the outcomes in the one-dimensional setting. The random dispersal strategy, not surprisingly, resulted in the worst outcome for cooperators.

Agent-based neutral competition in two-community networks

Competition between alternative states is an essential process in social and biological networks. Neutral competition can be represented by an unbiased random drift process in which the states of vertices (e.g., opinions, genotypes, or species) in a network are updated by repeatedly selecting two connected vertices. One of these vertices copies the state of the selected neighbor. Such updates are repeated until all vertices are in the same "consensus" state. There is no unique rule for selecting the vertex pair to be updated. Real-world processes comprise three limiting factors that can influence the selected edge and the direction of spread: (1) the rate at which a vertex sends a state to its neighbors, (2) the rate at which a state is received by a neighbor, and (3) the rate at which a state can be exchanged through a connecting edge. We investigate how these three limitations influence neutral competition in networks with two communities generated by a stochastic block model. By using Monte Carlo simulations, we show how the community structure and update rule determine the states' success probabilities and the time until a consensus is reached. We present a heterogeneous mean-field theory that agrees well with the Monte Carlo simulations. The effectiveness of the heterogeneous mean-field theory implies that quantitative predictions about the consensus are possible even if empirical data (e.g., from ecological fieldwork or observations of social interactions) do not allow a complete reconstruction of all edges in the network.

Cooperative success in epithelial public goods games

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.

Evolutionary bet-hedging in structured populations

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.

Two-strategy games with time constraints on regular graphs

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.

The effect of network topology on optimal exploration strategies and the evolution of cooperation in a mobile population

We model a mobile population interacting over an underlying spatial structure using a Markov movement model. Interactions take the form of public goods games, and can feature an arbitrary group size. Individuals choose strategically to remain at their current location or to move to a neighbouring location, depending upon their exploration strategy and the current composition of their group. This builds upon previous work where the underlying structure was a complete graph (i.e. there was effectively no structure). Here, we consider alternative network structures and a wider variety of, mainly larger, populations. Previously, we had found when cooperation could evolve, depending upon the values of a range of population parameters. In our current work, we see that the complete graph considered before promotes stability, with populations of cooperators or defectors being relatively hard to replace. By contrast, the star graph promotes instability, and often neither type of population can resist replacement. We discuss potential reasons for this in terms of network topology.

Methods for approximating stochastic evolutionary dynamics on graphs

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.

Three faces of node importance in network epidemiology: Exact results for small graphs

We investigate three aspects of the importance of nodes with respect to susceptible-infectious-removed (SIR) disease dynamics: influence maximization (the expected outbreak size given a set of seed nodes), the effect of vaccination (how much deleting nodes would reduce the expected outbreak size), and sentinel surveillance (how early an outbreak could be detected with sensors at a set of nodes). We calculate the exact expressions of these quantities, as functions of the SIR parameters, for all connected graphs of three to seven nodes. We obtain the smallest graphs where the optimal node sets are not overlapping. We find that (i) node separation is more important than centrality for more than one active node, (ii) vaccination and influence maximization are the most different aspects of importance, and (iii) the three aspects are more similar when the infection rate is low.

Evolutionary dynamics and the evolution of multiplayer cooperation in a subdivided population

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.

Evolutionary graph theory revisited: when is an evolutionary process equivalent to the Moran process?

Evolution in finite populations is often modelled using the classical Moran process. Over the last 10 years, this methodology has been extended to structured populations using evolutionary graph theory. An important question in any such population is whether a rare mutant has a higher or lower chance of fixating (the fixation probability) than the Moran probability, i.e. that from the original Moran model, which represents an unstructured population. As evolutionary graph theory has developed, different ways of considering the interactions between individuals through a graph and an associated matrix of weights have been considered, as have a number of important dynamics. In this paper, we revisit the original paper on evolutionary graph theory in light of these extensions to consider these developments in an integrated way. In particular, we find general criteria for when an evolutionary graph with general weights satisfies the Moran probability for the set of six common evolutionary dynamics.

Fixation probabilities for simple digraphs

The problem of finding birth–death fixation probabilities for configurations of normal and mutants on an N -vertex graph is formulated in terms of a Markov process on the 2 N -dimensional state space of possible configurations. Upper and lower bounds on the fixation probability after any given number of iterations of the birth–death process are derived in terms of the transition matrix of this process. Consideration is then specialized to a family of graphs called circular flows, and we present a summation formula for the complete bipartite graph, giving the fixation probability for an arbitrary configuration of mutants in terms of a weighted sum of the single-vertex fixation probabilities. This also yields a closed-form solution for the fixation probability of bipartite graphs. Three entropy measures are introduced, providing information about graph structure. Finally, a number of examples are presented, illustrating cases of graphs that enhance or suppress fixation probability for fitness r >1 as well as graphs that enhance fixation probability for only a limited range of fitness. Results are compared with recent results reported in the literature, where a positive correlation is observed between vertex degree variance and fixation probability for undirected graphs. We show a similar correlation for directed graphs, with correlation not directly to fixation probability but to the difference between fixation probability for a given graph and a complete graph.

Collective opinion formation model under Bayesian updating and confirmation bias

We propose a collective opinion formation model with a so-called confirmation bias. The confirmation bias is a psychological effect with which, in the context of opinion formation, an individual in favor of an opinion is prone to misperceive new incoming information as supporting the current belief of the individual. Our model modifies a Bayesian decision-making model for single individuals [M. Rabin and J. L. Schrag, Q. J. Econ. 114, 37 (1999)] for the case of a well-mixed population of interacting individuals in the absence of the external input. We numerically simulate the model to show that all the agents eventually agree on one of the two opinions only when the confirmation bias is weak. Otherwise, the stochastic population dynamics ends up creating a disagreement configuration (also called polarization), particularly for large system sizes. A strong confirmation bias allows various final disagreement configurations with different fractions of the individuals in favor of the opposite opinions.

A review of evolutionary graph theory with applications to game theory

Evolutionary graph theory (EGT), studies the ability of a mutant gene to overtake a finite structured population. In this review, we describe the original framework for EGT and the major work that has followed it. This review looks at the calculation of the "fixation probability" - the probability of a mutant taking over a population and focuses on game-theoretic applications. We look at varying topics such as alternate evolutionary dynamics, time to fixation, special topological cases, and game theoretic results. Throughout the review, we examine several interesting open problems that warrant further research.

Early appraisal of the fixation probability in directed networks

In evolutionary dynamics, the probability that a mutation spreads through the whole population, having arisen from a single individual, is known as the fixation probability. In general, it is not possible to find the fixation probability analytically given the mutant's fitness and the topological constraints that govern the spread of the mutation, so one resorts to simulations instead. Depending on the topology in use, a great number of evolutionary steps may be needed in each of the simulation events, particularly in those that end with the population containing mutants only. We introduce two techniques to accelerate the determination of the fixation probability. The first one skips all evolutionary steps in which the number of mutants does not change and thereby reduces the number of steps per simulation event considerably. This technique is computationally advantageous for some of the so-called layered networks. The second technique, which is not restricted to layered networks, consists of aborting any simulation event in which the number of mutants has grown beyond a certain threshold value and counting that event as having led to a total spread of the mutation. For advantageous mutations in large populations and regardless of the network's topology, we demonstrate, both analytically and by means of simulations, that using a threshold of about [N/(r-1)](1/4) mutants, where N is the number of simulation events and r is the ratio of the mutants' fitness to that of the remainder of the population, leads to an estimate of the fixation probability that deviates in no significant way from that obtained from the full-fledged simulations. We have observed speedups of two orders of magnitude for layered networks with 10,000 nodes.