title: Exact numerical calculation of fixation probability and time on graphs.
abstract: The Moran process on graphs is a popular model to study the dynamics of evolution in a spatially structured population. Exact analytical solutions for the fixation probability and time of a new mutant have been found for only a few classes of graphs so far. Simulations are time-expensive and many realizations are necessary, as the variance of the fixation times is high. We present an algorithm that numerically computes these quantities for arbitrary small graphs by an approach based on the transition matrix. The advantage over simulations is that the calculation has to be executed only once. Building the transition matrix is automated by our algorithm. This enables a fast and interactive study of different graph structures and their effect on fixation probability and time. We provide a fast implementation in C with this note (Hindersin et al., 2016). Our code is very flexible, as it can handle two different update mechanisms (Birth-death or death-Birth), as well as arbitrary directed or undirected graphs.
authors.affiliation: Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, D-24306 Plön, Germany.
authors.forename: Laura
authors.initials: L
authors.lastname: Hindersin
authors.affiliation: Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, D-24306 Plön, Germany; Institute of Mathematics, University of Lübeck, D-23562 Lübeck, Germany.
authors.forename: Marius
authors.initials: M
authors.lastname: Möller
authors.affiliation: Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, D-24306 Plön, Germany.
authors.forename: Arne
authors.initials: A
authors.lastname: Traulsen
authors.affiliation: Department of Evolutionary Theory, Max Planck Institute for Evolutionary Biology, D-24306 Plön, Germany; Evotec AG, D-22419 Hamburg, Germany. Electronic address: bauer@evolbio.mpg.de.
authors.forename: Benedikt
authors.initials: B
authors.lastname: Bauer
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D003198:Computer Simulation; D005828:Genetics, Population / Q000379:methods; D006801:Humans; D011336:Probability; D013997:Time Factors
keywords: Evolutionary graph theory; Fixation probability; Fixation time; Moran process; Static networks