Asymptotically optimal amplifiers for the Moran process

DOI10.1016/J.TCS.2018.08.005MaRDI QIDQ1755587zbMATH OpenOpenAlexWikidataFDO

Authors Leslie Ann Goldberg, John Lapinskas, Johannes Lengler, Florian Meier, Pascal Pfister, Konstantinos Panagiotou

Publication date 10 January 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.04209, https://research-information.bris.ac.uk/en/publications/asymptotically-optimal-amplifiers-for-the-moran-process(13f48a6d-3777-45a3-a656-726b99f0e2e7).html

zbMATH Keywords

Markov chainsextremal graph theoryMoran processfixation probabilitystrong amplifiers

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Randomized algorithms (68W20)

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 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.

Recommendations

• Amplifiers for the Moran process
• Amplifiers for the Moran process
• Strong bounds for evolution in networks
• Approximating fixation probabilities in the generalized Moran process
• Approximating fixation probabilities in the generalized Moran process

Cites work

• scientific article; zbMATH DE number 3148873 (Why is no real title available?)
• scientific article; zbMATH DE number 1350307 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• A proof of alon's second eigenvalue conjecture
• Absorption time of the Moran process
• Amplifiers for the Moran process
• Approximating fixation probabilities in the generalized Moran process
• Evolutionary dynamics. Exploring the equations of life.
• Fixation probabilities on superstars, revisited and revised
• Fixation results for threshold voter systems
• Gossip algorithms
• Natural models for evolution on networks
• On the fixation probability of superstars
• Strong bounds for evolution in networks
• The critical contact process dies out

Cited in

(8)

• Fixation dynamics on multilayer networks
• Amplifiers for the Moran process
• A survey of the modified Moran process and evolutionary graph theory
• Spectral analysis of transient amplifiers for death-birth updating constructed from regular graphs
• Spectral dynamics of guided edge removals and identifying transient amplifiers for death-birth updating
• Fixation probability in evolutionary dynamics on switching temporal networks
• Strong bounds for evolution in networks
• Amplifiers for the Moran process

This page was built for publication: Asymptotically optimal amplifiers for the Moran process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1755587)