Skip to main content

Research Repository

Advanced Search

Natural models for evolution on networks

Mertzios, G.B.; Nikoletseas, S.; Raptopoulos, C.; Spirakis, P.G.

Natural models for evolution on networks Thumbnail


Authors

S. Nikoletseas

C. Raptopoulos

P.G. Spirakis



Abstract

Evolutionary dynamics has been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [P. Moran, Random processes in genetics, Proceedings of the Cambridge Philosophical Society 54 (1) (1958) 60–71]. Recently, this approach has been generalized in [E. Lieberman, C. Hauert, M.A. Nowak, Evolutionary dynamics on graphs, Nature 433 (2005) 312–316] by arranging individuals on the nodes of a network (in general, directed). In this setting, the existence of directed arcs enables the simulation of extreme phenomena, where the fixation probability of a randomly placed mutant (i.e., the probability that the offspring of the mutant eventually spread over the whole population) is arbitrarily small or large. On the other hand, undirected networks (i.e., undirected graphs) seem to have a smoother behavior, and thus it is more challenging to find suppressors/amplifiers of selection, that is, graphs with smaller/greater fixation probability than the complete graph (i.e., the homogeneous population). In this paper we focus on undirected graphs. We present the first class of undirected graphs which act as suppressors of selection, by achieving a fixation probability that is at most one half of that of the complete graph, as the number of vertices increases. Moreover, we provide some generic upper and lower bounds for the fixation probability of general undirected graphs. As our main contribution, we introduce the natural alternative of the model proposed in [E. Lieberman, C. Hauert, M.A. Nowak, Evolutionary dynamics on graphs, Nature 433 (2005) 312–316]. In our new evolutionary model, all individuals interact simultaneously and the result is a compromise between aggressive and non-aggressive individuals. We prove that our new model of mutual influences admits a potential function, which guarantees the convergence of the system for any graph topology and any initial fitness vector of the individuals. Furthermore, we prove fast convergence to the stable state for the case of the complete graph, as well as we provide almost tight bounds on the limit fitness of the individuals. Apart from being important on its own, this new evolutionary model appears to be useful also in the abstract modeling of control mechanisms over invading populations in networks. We demonstrate this by introducing and analyzing two alternative control approaches, for which we bound the time needed to stabilize to the “healthy” state of the system.

Citation

Mertzios, G., Nikoletseas, S., Raptopoulos, C., & Spirakis, P. (2013). Natural models for evolution on networks. Theoretical Computer Science, 477, 76-95. https://doi.org/10.1016/j.tcs.2012.11.032

Journal Article Type Article
Publication Date Mar 18, 2013
Deposit Date Sep 5, 2014
Publicly Available Date Mar 29, 2024
Journal Theoretical Computer Science
Print ISSN 0304-3975
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 477
Pages 76-95
DOI https://doi.org/10.1016/j.tcs.2012.11.032
Keywords Evolutionary dynamics, Undirected graphs, Fixation probability, Potential function, Markov chain, Fitness, Population structure.
Related Public URLs http://www.sciencedirect.com/science/article/pii/S0304397512010754

Files

Accepted Journal Article (500 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical Computer Science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical Computer Science, 477, 2013, 10.1016/j.tcs.2012.11.032.





You might also like



Downloadable Citations