Abstract: We consider the Moran process, as generalized by Lieberman, Hauert and Nowak (Nature, 433:312--316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned 'fitness' value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r>0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r≥1) and of extinction (for all r>0).
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 fixationprobability 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 fixationprobability 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 fixationprobability 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 fixationprobability 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.
Abstract: The Moran process models the spread of genetic mutations through a population. A mutant with relative fitness r is introduced into a population and the system evolves, either reaching fixation (in which every individual is a mutant) or extinction (in which none is). In a widely cited paper (Nature, 2005), Lieberman, Hauert and Nowak generalize the model to populations on the vertices of graphs. They describe a class of graphs (called "superstars"), with a parameter k. Superstars are designed to have an increasing fixationprobability as k increases. They state that the probability of fixation tends to 1−r−k as graphs get larger but we show that this claim is untrue as stated. Specifically, for k=5, we show that the true fixationprobability (in the limit, as graphs get larger) is at most 1−1/j(r) where j(r)=Θ(r4), contrary to the claimed result. We do believe that the qualitative claim of Lieberman et al.\ --- that the fixationprobability of superstars tends to 1 as k increases --- is correct, and that it can probably be proved along the lines of their sketch. We were able to run larger computer simulations than the ones presented in their paper. However, simulations on graphs of around 40,000 vertices do not support their claim. Perhaps these graphs are too small to exhibit the limiting behaviour.
Abstract: This work extends what is known so far for a basic model of
evolutionary antagonis
m in undirected ne
tworks (graphs).
More specif-
ically, this work studies the generalized Moran process, as introduced
by Lieberman, Hauert, and Nowak [Nature, 433:312-316, 2005], where
the individuals of a population reside on the vertices of an undirected
connected graph. The initial population has a single
mutant
of a
fitness
value
r
(typically
r>
1), residing at some vertex
v
of the graph, while
every other vertex is initially occupied by an individual of fitness 1. At
every step of this process, an individual (i.e. vertex) is randomly chosen
for reproduction with probability proportional to its fitness, and then it
places a copy of itself on a random neighbor, thus replacing the individ-
ual that was residing there. The main quantity of interest is the
fixationprobability
, i.e. the probability that eventually the whole graph is occu-
pied by descendants of the mutant. In this work we concentrate on the
fixationprobability when the mutant is initially on a specific vertex
v
,
thus refining the older notion of Lieberman et al. which studied the fix-
ation probability when the initial mutant is placed at a random vertex.
We then aim at finding graphs that have many “strong starts” (or many
“weak starts”) for the mutant. Thus we introduce a parameterized no-
tion of
selective amplifiers
(resp.
selective suppressors
)ofevolution.We
prove the existence of
strong
selective amplifiers (i.e. for
h
(
n
)=
Θ
(
n
)
vertices
v
the fixationprobability of
v
is at least 1
−
c
(
r
)
n
for a func-
tion
c
(
r
) that depends only on
r
), and the existence of quite strong
selective suppressors. Regarding the traditional notion of fixation prob-
ability from a random start, we provi
de strong upper and lower bounds:
first we demonstrate the non-existence of “strong universal” amplifiers,
and second we prove the
Thermal Theorem
which states that for any
undirected graph, when the mutant starts at vertex
v
, the fixation prob-
ability at least (
r
−
1)
/
(
r
+
deg
v
deg
min
). This theorem (which extends the
“Isothermal Theorem” of Lieberman et al. for regular graphs) implies
an almost tight lower bound for the usual notion of fixationprobability.
Our proof techniques are original and are based on new domination ar-
guments which may be of general interest in Markov Processes that are
of the general birth-death type.
