
arXiv: 1611.04209
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 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.
FOS: Computer and information sciences, name=Algorithms and Complexity, Discrete Mathematics (cs.DM), extremal graph theory, Directed graphs (digraphs), tournaments, strong amplifiers, fixation probability, FOS: Mathematics, Mathematics - Combinatorics, Quantitative Biology - Populations and Evolution, Social and Information Networks (cs.SI), Markov chains, Randomized algorithms, Probability (math.PR), Populations and Evolution (q-bio.PE), Computer Science - Social and Information Networks, /dk/atira/pure/core/keywords/algorithms_and_complexity, Markov chains (discrete-time Markov processes on discrete state spaces), FOS: Biological sciences, Moran process, Combinatorics (math.CO), Mathematics - Probability, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, name=Algorithms and Complexity, Discrete Mathematics (cs.DM), extremal graph theory, Directed graphs (digraphs), tournaments, strong amplifiers, fixation probability, FOS: Mathematics, Mathematics - Combinatorics, Quantitative Biology - Populations and Evolution, Social and Information Networks (cs.SI), Markov chains, Randomized algorithms, Probability (math.PR), Populations and Evolution (q-bio.PE), Computer Science - Social and Information Networks, /dk/atira/pure/core/keywords/algorithms_and_complexity, Markov chains (discrete-time Markov processes on discrete state spaces), FOS: Biological sciences, Moran process, Combinatorics (math.CO), Mathematics - Probability, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 16 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
