J. Díaz
On the fixation probability of superstars
Díaz, J.; Goldberg, L.A.; Mertzios, G.B.; Richerby, D.; Serna, M.; Spirakis, P.G.
Authors
L.A. Goldberg
Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
D. Richerby
M. Serna
P.G. Spirakis
Abstract
The Moran process models the spread of genetic mutations through populations. A mutant with relative fitness r is introduced and the system evolves, either reaching fixation (an all-mutant population) or extinction (no mutants). In a widely cited paper, Lieberman et al. (2005 Evolutionary dynamics on graphs. Nature 433, 312–316) generalize the model to populations on the vertices of graphs. They describe a class of graphs (‘superstars’), with a parameter k and state that the fixation probability tends to 1−r−k as the graphs get larger: we show that this is untrue as stated. Specifically, for k=5, we show that the fixation probability (in the limit, as graphs get larger) cannot exceed 1−1/j(r), where j(r)=Θ(r4), contrary to the claimed result. Our proof is fully rigorous, though we use a computer algebra package to invert a 31×31 symbolic matrix. We do believe the qualitative claim of Lieberman et al.—that superstar fixation probability tends to 1 as k increases—and that it can probably be proved similarly to their sketch. We were able to run larger simulations than the ones they presented. Simulations on graphs of around 40 000 vertices do not support their claim but these graphs might be too small to exhibit the limiting behaviour.
Citation
Díaz, J., Goldberg, L., Mertzios, G., Richerby, D., Serna, M., & Spirakis, P. (2013). On the fixation probability of superstars. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2156), https://doi.org/10.1098/rspa.2013.0193
Journal Article Type | Article |
---|---|
Publication Date | Aug 8, 2013 |
Deposit Date | Sep 5, 2014 |
Journal | Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences |
Print ISSN | 1364-5021 |
Electronic ISSN | 1471-2946 |
Publisher | The Royal Society |
Peer Reviewed | Peer Reviewed |
Volume | 469 |
Issue | 2156 |
DOI | https://doi.org/10.1098/rspa.2013.0193 |
Keywords | Evolutionary dynamics, Moran process, Fixation probability. |
You might also like
Graphs with minimum fractional domatic number
(2023)
Journal Article
Approximate and Randomized algorithms for Computing a Second Hamiltonian Cycle
(2023)
Journal Article
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs
(2023)
Conference Proceeding
Fast parameterized preprocessing for polynomial-time solvable graph problems
(2023)
Journal Article
The complexity of computing optimum labelings for temporal connectivity
(2022)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search