Goldberg, Leslie Ann; Lapinskas, John; Lengler, Johannes; Meier, Florian; Panagiotou, Konstantinos; Pfister, Pascal
(2019):
Asymptotically optimal amplifiers for the Moran process.
In: Theoretical Computer Science, Vol. 758: pp. 7393

Full text not available from 'Open Access LMU'.
Abstract
We study the Moran process as adapted by Lieberman. Hauert and Nowak. This is a model of an evolving population on a graph or digraph where certain individuals, called "mutants" have fitness r and other individuals, called "nonmutants" have fitness 1. We focus on the situation where the mutation is advantageous, in the sense that r > 1. A family of digraphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on digraphs in this family. The mostamplifying known family of digraphs is the family of megastars of Galanis et al. We show that this family is optimal, up to logarithmic factors, since every stronglyconnected nvertex digraph has extinction probability Omega(n(1/2)). Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O(n(1/3)). We show that this is optimal, up to constant factors. Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O(n/m), where m is the number of edges. Again, we show that this is optimal, up to constant factors. (C) 2018 Elsevier B.V. All rights reserved.