Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
This work studies the generalized Moran process, as introduced by Lieberman et al. [Nature, 433:312-316, 2005]. We introduce the parameterized notions of selective amplifiers and selective suppressors of evolution, i.e. of networks (graphs) with many “strong starts” and many “weak starts” for the mutant, respectively. We first prove the existence of strong selective amplifiers and of (quite) strong selective suppressors. Furthermore we provide strong upper bounds and almost tight lower bounds (by proving the “Thermal Theorem”) for the traditional notion of fixation probability of Lieberman et al., i.e. assuming a random initial placement of the mutant.
Mertzios, G., & Spirakis, P. (2018). Strong bounds for evolution in networks. Journal of Computer and System Sciences, 97, 60-82. https://doi.org/10.1016/j.jcss.2018.04.004
Journal Article Type | Article |
---|---|
Acceptance Date | Apr 27, 2018 |
Online Publication Date | May 8, 2018 |
Publication Date | Nov 1, 2018 |
Deposit Date | Apr 27, 2018 |
Publicly Available Date | May 8, 2019 |
Journal | Journal of Computer and System Sciences |
Print ISSN | 0022-0000 |
Electronic ISSN | 1090-2724 |
Publisher | Elsevier |
Peer Reviewed | Peer Reviewed |
Volume | 97 |
Pages | 60-82 |
DOI | https://doi.org/10.1016/j.jcss.2018.04.004 |
Keywords | Evolutionary dynamics, Undirected graphs, Fixation probability, Lower bound, Markov chain. |
Public URL | https://durham-repository.worktribe.com/output/1327990 |
Accepted Journal Article
(549 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by-nc-nd/4.0/
Copyright Statement
© 2018 This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/
The complexity of computing optimum labelings for temporal connectivity
(2022)
Presentation / Conference Contribution
The complexity of temporal vertex cover in small-degree graphs
(2022)
Presentation / Conference Contribution
The complexity of transitively orienting temporal graphs
(2021)
Presentation / Conference Contribution
Equitable scheduling on a single machine
(2021)
Presentation / Conference Contribution
Exact and approximate algorithms for computing a second Hamiltonian cycle
(2020)
Presentation / Conference Contribution
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
Apache License Version 2.0 (http://www.apache.org/licenses/)
Apache License Version 2.0 (http://www.apache.org/licenses/)
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