George Mertzios
Durham

Natural Models for Evolution on Networks

Evolutionary dynamics have been traditionally studied in the context of
homogeneous populations, mainly described by the Moran process
\cite{Moran58}. Recently, this approach has been generalized in
\cite{Lieberman-Hauert-Nowak05} 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 \cite{Lieberman-Hauert-Nowak05}. 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 \cite{Lieberman-Hauert-Nowak05} 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.