Amplifiers for the Moran process

DOI10.4230/LIPICS.ICALP.2016.62zbMATH Open1388.68296arXiv1512.05632MaRDI QIDQ4598201FDOQ4598201

Andreas Galanis, David Richerby, John Lapinskas, Andreas Göbel, Leslie Ann Goldberg

Publication date: 19 December 2017

Abstract: The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen u.a.r.) possesses a mutation, with fitness r>1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or non-mutant) is passed on to an out-neighbour which is chosen u.a.r. If the underlying graph is strongly connected then the algorithm will eventually reach fixation, in which all individuals are mutants, or extinction, in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r>1, the extinction probability tends to 0 as the number of vertices increases. Lieberman et al. proposed two potentially strongly-amplifying families - superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this paper, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family "megastars". When the algorithm is run on an n-vertex graph in this family, starting with a uniformly-chosen mutant, the extinction probability is roughly $n^{-1/2}$ (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n). Finally, we prove that our analysis of megastars is fairly tight - there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors).

Full work available at URL: https://arxiv.org/abs/1512.05632

Recommendations

• Amplifiers for the Moran process
• Asymptotically optimal amplifiers for the Moran process
• Strong bounds for evolution in networks
• On the fixation probability of superstars
• Strong bounds for evolution in networks

zbMATH Keywords

evolutionary dynamicsMoran processrandomised algorithm on graphs

Mathematics Subject Classification ID

Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cited In (3)

• Asymptotically optimal amplifiers for the Moran process
• Spectral dynamics of guided edge removals and identifying transient amplifiers for death-birth updating
• Title not available (Why is that?)

This page was built for publication: Amplifiers for the Moran process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598201)