Evolutionary Dynamics in Undirected Networks

26^th February 2013, 16:00 G12
Dr George Mertzios
School of Engineering and Computing Sciences
Durham University

Abstract

Evolutionary dynamics have been traditionally studied in the context of homogeneous populations, mainly described by the Moran Process. Recently, this approach has been generalized by Lieberman, Hauert and Nowak [Nature, 2005], by arranging individuals on the nodes of a connected directed network. Our work focuses on evolutionary models for undirected networks which seem to have a smoother behaviour. We present the first class of undirected graphs which act as suppressors of selection (i.e. have smaller fixation probability than the clique), as well as several upper/lower bounds on the fixation probability of an arbitrary graph. Furthermore we introduce the notion of “selective amplifiers” and “selective suppressors” of selection, where we take into account the number of strong starts (leading to fixation) or weak starts (leading to extinction). We also show how to compute fixation probabilities in any undirected graph via a fully polynomial randomized approximation scheme. In addition we present a new alternative evolutionary model in which all individuals act simultaneously and the result is a compromise between aggressive and non-aggressive individuals. So, we consider also aggregation as opposed to “all or nothing” strategy implied by the generalized Moran process. These results are recent joint work with (a) S. Nikoletseas, Ch. Raptopoulos, and P. Spirakis [WINE 2011], (b) with J. Diaz, L.A. Goldberg, D. Richerby, M. Serna, and P. Spirakis [SODA 2012], and (c) with P. Spirakis [arXiv, 2012].