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 https://github.com/hindersin/efficientFixation. 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.

References in corpus (5)

• Evolutionary dynamics on degree-heterogeneous graphs
• Most undirected random graphs are amplifiers of selection for Birth-death dynamics, but suppressors of selection for death-Birth dynamics
• Deterministic evolutionary game dynamics in finite populations
• Exact numerical calculation of fixation probability and time on graphs
• Fast and asymptotic computation of the fixation probability for Moran processes on graphs

Cited by in corpus (15)

• Fixation probabilities in evolutionary dynamics under weak selection
• Exact numerical calculation of fixation probability and time on graphs
• Transient amplifiers of selection and reducers of fixation for death-Birth updating on graphs
• Takeover times for a simple model of network infection
• Methods for approximating stochastic evolutionary dynamics on graphs
• Motion, fixation probability and the choice of an evolutionary process
• Fixation probability in evolutionary dynamics on switching temporal networks
• More can be better: An analysis of single-mutant fixation probability functions under $2\times 2$ games
• Fixation probability and fixation time in structured populations
• Constant-selection evolutionary dynamics on weighted networks
• Natural selection of mutants that modify population structure
• Fixation probabilities for any configuration of two strategies on regular graphs
• Evolution of Cooperation for Multiple Mutant Configurations on All Regular Graphs with $N\le 14$ players
• Constructing transient amplifiers for death-Birth updating: A case study of cubic and quartic regular graphs
• Exact fixation probabilities for the Birth-Death and Death-Birth frequency-dependent Moran processes on the star graph