Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Natural models for evolution on networks.

Mertzios, G.B. and Nikoletseas, S. and Raptopoulos, C. and Spirakis, P.G. (2011) 'Natural models for evolution on networks.', in Internet and Network Economics : 7th International Workshop, WINE 2011, 11-14 December 2011. Berlin: Springer, pp. 290-301. Lecture notes in computer science. (7090).

Abstract

Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described by the Moran process [15]. Recently, this approach has been generalized in [13] 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 offsprings 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 [13]. In our new evolutionary model, all individuals interact simultaneously and the result is a compromise between aggressive and non-aggressive individuals. That is, the behavior of the individuals in our new model and in the model of [13] can be interpreted as an “aggregation” vs. an “all-or-nothing” strategy, respectively. 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.

Item Type:Book chapter
Additional Information:Event URL: http://web.spms.ntu.edu.sg/~wine11/accepted.html
Keywords:Evolutionary dynamics, Undirected graphs, Fixation probability, Potential function, Markov chain, Fitness, Population structure.
Full text:PDF - Accepted Version (158Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/978-3-642-25510-6_25
Publisher statement:The original publication is available at www.springerlink.com
Record Created:21 Feb 2012 12:50
Last Modified:06 Mar 2012 11:47

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library