Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor
Strong bounds for evolution in networks
Mertzios, G.B.; Spirakis, P.G.
Authors
P.G. Spirakis
Abstract
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.
Citation
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 | Mar 28, 2024 |
Journal | Journal of Computer and System Sciences |
Print ISSN | 0022-0000 |
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. |
Files
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/
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