2013 | OriginalPaper | Buchkapitel
Strong Bounds for Evolution in Networks
verfasst von : George B. Mertzios, Paul G. Spirakis
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This work extends what is known so far for a basic model of evolutionary antagonism in undirected networks (graphs). More specifically, 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 individual that was residing there. The main quantity of interest is the
fixation probability
, i.e. the probability that eventually the whole graph is occupied by descendants of the mutant. In this work we concentrate on the fixation probability when the mutant is initially on a specific vertex
v
, thus refining the older notion of Lieberman et al. which studied the fixation 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 notion of
selective amplifiers
(resp.
selective suppressors
) of evolution. We prove the existence of
strong
selective amplifiers (i.e. for
h
(
n
) = Θ(
n
) vertices
v
the fixation probability of
v
is at least
$1-\frac{c(r)}{n}$
for a function
c
(
r
) that depends only on
r
), and the existence of quite strong selective suppressors. Regarding the traditional notion of fixation probability from a random start, we provide 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 probability at least
$(r-1) / (r+\frac{\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 fixation probability. Our proof techniques are original and are based on new domination arguments which may be of general interest in Markov Processes that are of the general birth-death type.