Asymptotically optimal amplifiers for the Moran process

Autor: Leslie Ann Goldberg, John Lapinskas, Pascal Pfister, Florian Meier, Konstantinos Panagiotou, Johannes Lengler
Rok vydání: 2019
Předmět:
FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
General Computer Science
Logarithm
Extinction probability
Population
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Combinatorics
FOS: Mathematics
0202 electrical engineering
electronic engineering
information engineering
Moran process
Mathematics - Combinatorics
Quantitative Biology::Populations and Evolution
Quantitative Biology - Populations and Evolution
education
Mathematics
Social and Information Networks (cs.SI)
education.field_of_study
Markov chain
Probability (math.PR)
Populations and Evolution (q-bio.PE)
Computer Science - Social and Information Networks
Digraph
Extremal graph theory
Asymptotically optimal algorithm
010201 computation theory & mathematics
FOS: Biological sciences
020201 artificial intelligence & image processing
Combinatorics (math.CO)
Mathematics - Probability
Computer Science - Discrete Mathematics
Zdroj: Theoretical Computer Science. 758:73-93
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2018.08.005
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: