Name
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 “non-mutants” 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 most-amplifying 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 strongly-connected n-vertex digraph has extinction probability Ω(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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2018.08.005 | Theoretical Computer Science |
Keywords | DocType | Volume |
Strong amplifiers,Moran process,Fixation probability,Extremal graph theory,Markov chains | Journal | 758 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
0 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| leslie ann goldberg | 1 | 1411 | 125.20 |
| John Lapinskas | 2 | 13 | 4.25 |
| Johannes Lengler | 3 | 70 | 14.94 |
| Florian Meier | 4 | 22 | 3.73 |
| Konstantinos Panagiotou | 5 | 290 | 27.80 |
| pascal pfister | 6 | 1 | 1.13 |