Galanis, Andreas ;
Göbel, Andreas ;
Goldberg, Leslie Ann ;
Lapinskas, John ;
Richerby, David
Amplifiers for the Moran Process
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 uniformly at random) 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 nonmutant) is passed on to an outneighbour which is chosen uniformly at random. 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. Strong amplification is a rather surprising property  it means that in such graphs, the fixation probability of a uniformlyplaced initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of r > 1 (independently of n). The name "strongly amplifying" comes from the fact that this selective advantage is "amplified". Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially stronglyamplifying 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. 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 nvertex graph in this family, starting with a uniformlychosen 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). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al. A full version [Galanis/Göbel/Goldberg/Lapinskas/Richerby, Preprint] containing detailed proofs is available at http://arxiv.org/abs/1512.05632. Theoremnumbering here matches the full version.
BibTeX  Entry
@InProceedings{galanis_et_al:LIPIcs:2016:6222,
author = {Andreas Galanis and Andreas G{\"o}bel and Leslie Ann Goldberg and John Lapinskas and David Richerby},
title = {{Amplifiers for the Moran Process}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {62:162:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6222},
URN = {urn:nbn:de:0030drops62227},
doi = {10.4230/LIPIcs.ICALP.2016.62},
annote = {Keywords: Moran process, randomised algorithm on graphs, evolutionary dynamics}
}
2016
Keywords: 

Moran process, randomised algorithm on graphs, evolutionary dynamics 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

2016 