
arXiv: 1804.02293
The Moran process is a random process that models the spread of genetic mutations through graphs. On connected graphs, the process eventually reaches “fixation,” where all vertices are mutants, or “extinction,” where none are. Our main result is an almost‐tight upper bound on expected absorption time. For all ϵ>0, we show that the expected absorption time on an n‐vertex graph is o(n3+ϵ). Specifically, it is at most , and there is a family of graphs where it is Ω(n3). In proving this, we establish a phase transition in the probability of fixation, depending on the mutants' fitness r. We show that no similar phase transition occurs for digraphs, where it is already known that the expected absorption time can be exponential. Finally, we give an improved fully polynomial randomized approximation scheme (FPRAS) for approximating the probability of fixation. On degree‐bounded graphs where some basic properties are given, its running time is independent of the number of vertices.
Social and Information Networks (cs.SI), FOS: Computer and information sciences, name=Algorithms and Complexity, absorption time, Discrete Mathematics (cs.DM), Probability (math.PR), Populations and Evolution (q-bio.PE), Computer Science - Social and Information Networks, /dk/atira/pure/core/keywords/algorithms_and_complexity, 004, 510, fixation probability, Problems related to evolution, Stochastic processes, FOS: Biological sciences, Moran process, FOS: Mathematics, evolutionary dynamics, Mathematics - Combinatorics, Combinatorics (math.CO), Quantitative Biology - Populations and Evolution, Mathematics - Probability, Computer Science - Discrete Mathematics
Social and Information Networks (cs.SI), FOS: Computer and information sciences, name=Algorithms and Complexity, absorption time, Discrete Mathematics (cs.DM), Probability (math.PR), Populations and Evolution (q-bio.PE), Computer Science - Social and Information Networks, /dk/atira/pure/core/keywords/algorithms_and_complexity, 004, 510, fixation probability, Problems related to evolution, Stochastic processes, FOS: Biological sciences, Moran process, FOS: Mathematics, evolutionary dynamics, Mathematics - Combinatorics, Combinatorics (math.CO), Quantitative Biology - Populations and Evolution, 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). | 8 | |
| 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. | Average |
