Phase transitions of the Moran process and algorithmic consequences

The Moran process is a random process that models the spread of genetic mutations through graphs. On connected graphs, the process eventually reaches “fixation”, where all vertices are mutants, or “extinction”, where none are. Our main result is an almost-tight upper bound on expected absorption time. For all ε > 0, we show that the expected absorption time on an n-vertex graph is o(n3+ε). Specifically, it is at most n3eO((log log n)3), and there is a family of graphs where it is Ω(n3). In proving this, we establish a phase transition in the probability of fixation, depending on mutants’ fitness r. We show that no similar phase transition occurs for digraphs, where it is already known that the expected absorption time can be exponential. Finally, we give an improved FPRAS for approximating the probability of fixation. On degree-bounded graphs where some basic properties are given, its running time is independent of the number of vertices.