---
res:
bibo_abstract:
- 'Evolutionary graph theory studies the evolutionary dynamics in a population structure
given as a connected graph. Each node of the graph represents an individual of
the population, and edges determine how offspring are placed. We consider the
classical birth-death Moran process where there are two types of individuals,
namely, the residents with fitness 1 and mutants with fitness r. The fitness indicates
the reproductive strength. The evolutionary dynamics happens as follows: in the
initial step, in a population of all resident individuals a mutant is introduced,
and then at each step, an individual is chosen proportional to the fitness of
its type to reproduce, and the offspring replaces a neighbor uniformly at random.
The process stops when all individuals are either residents or mutants. The probability
that all individuals in the end are mutants is called the fixation probability,
which is a key factor in the rate of evolution. We consider the problem of approximating
the fixation probability. The class of algorithms that is extremely relevant for
approximation of the fixation probabilities is the Monte-Carlo simulation of the
process. Previous results present a polynomial-time Monte-Carlo algorithm for
undirected graphs when r is given in unary. First, we present a simple modification:
instead of simulating each step, we discard ineffective steps, where no node changes
type (i.e., either residents replace residents, or mutants replace mutants). Using
the above simple modification and our result that the number of effective steps
is concentrated around the expected number of effective steps, we present faster
polynomial-time Monte-Carlo algorithms for undirected graphs. Our algorithms are
always at least a factor O(n2/ log n) faster as compared to the previous algorithms,
where n is the number of nodes, and is polynomial even if r is given in binary.
We also present lower bounds showing that the upper bound on the expected number
of effective steps we present is asymptotically tight for undirected graphs. @eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Rasmus
foaf_name: Ibsen-Jensen, Rasmus
foaf_surname: Ibsen-Jensen
foaf_workInfoHomepage: http://www.librecat.org/personId=3B699956-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Martin
foaf_name: Nowak, Martin
foaf_surname: Nowak
bibo_doi: 10.4230/LIPIcs.MFCS.2017.61
bibo_volume: 83
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-395977046-0
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Faster Monte Carlo algorithms for fixation probability of the Moran process
on undirected graphs@
...