The Moran process is a randomised algorithm that models the spread of genetic mutations through graphs. If the graph is connected, the process eventually reaches "fixation", where every vertex is a mutant, or "extinction", where no vertex is a mutant. Our main result is an almost-tight bound on the expected running time of the algorithm. For all epsilon > 0, we show that the expected running time on an n-vertex graph is o(n^(3+epsilon)). In fact, we show that it is at most n^3 * exp(O((log log n)^3)) and that there is a family of graphs where it is Omega(n^3). In the course of proving our main result, we also establish a phase transition in the probability of fixation, depending on the fitness parameter r of the mutation. We show that no similar phase transition occurs for digraphs, where it is already known that the expected running time can also be exponential. Finally, we give an improved FPRAS for approximating the probability of fixation. Its running time is independent of the size of the graph when the maximum degree is bounded.
@cite_21: The Moran process, as studied by [10], is a stochastic process modeling the spread of genetic mutations in populations. In this process, agents of a two-type population (i.e. mutants and residents) are associated with the vertices of a graph. Initially, only one vertex chosen uniformly at random (u.a.r.) is a mutant, with fitness (r > 0 ), while all other individuals are residents, with fitness 1. In every step, an individual is chosen with probability proportional to its fitness, and its state (mutant or resident) is passed on to a neighbor which is chosen u.a.r. In this paper, we introduce and study for the first time a generalization of the model of [10] by assuming that different types of individuals perceive the population through different graphs defined on the same vertex set, namely (G_R = (V, E_R) ) for residents and (G_M = (V, E_M) ) for mutants. In this model, we study the fixation probability, namely the probability that eventually only mutants remain in the population, for various pairs of graphs.
@cite_12: Evolutionary graph theory (EGT), studies the ability of a mutant gene to overtake a nite 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 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 xation, special topological cases, and game theoretic results. Throughout the review, we examine several interesting open problems that warrant further research.
@cite_17: Evolutionary dynamics have been traditionally studied in the context of homogeneous or spatially extended populations1,2,3,4. Here we generalize population structure by arranging individuals on a graph. Each vertex represents an individual. The weighted edges denote reproductive rates which govern how often individuals place offspring into adjacent vertices. The homogeneous population, described by the Moran process3, is the special case of a fully connected graph with evenly weighted edges. Spatial structures are described by graphs where vertices are connected with their nearest neighbours. We also explore evolution on random and scale-free networks5,6,7. We determine the fixation probability of mutants, and characterize those graphs for which fixation behaviour is identical to that of a homogeneous population7. Furthermore, some graphs act as suppressors and others as amplifiers of selection. It is even possible to find graphs that guarantee the fixation of any advantageous mutant. We also study frequency-dependent selection and show that the outcome of evolutionary games can depend entirely on the structure of the underlying graph. Evolutionary graph theory has many fascinating applications ranging from ecology to multi-cellular organization and economics.
Several generalisations of the Moran process are also studied @cite_17 @cite_12 . Some versions of the process allow edge weights, which is equivalent to allowing multiple edges in the graph, and others determine the fitness of a vertex partly or fully by game payoffs with its neighbours. More recently, a variant has been proposed @cite_21 in which the mutants and non-mutants interact along different graphs. In this paper, we consider the original graph Moran process.