2023/08/05 by David A. Brewster, Martin A. Nowak, Brewster, David A. +3 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Graph Theory Research #Complex Network Analysis Techniques
paper · pdf · doi:10.48550/arxiv.2308.02762
Computing the rate of evolution in spatially structured populations is difficult. A key quantity is the fixation time of a single mutant with relative reproduction rate r which invades a population of residents. We say that the fixation time is "fast" if it is at most a polynomial function in terms of the population size N. Here we study fixation times of advantageous mutants (r>1) and neutral mutants (r=1) on directed graphs, which are those graphs that have at least some one-way connections. We obtain three main results. First, we prove that for any directed graph the fixation time is fast, provided that r is sufficiently large. Second, we construct an efficient algorithm that gives an upper bound for the fixation time for any graph and any r≥ 1. Third, we identify a broad class of directed graphs with fast fixation times for any r≥ 1. This class includes previously studied amplifiers of selection, such as Superstars and Metafunnels. We also show that on some graphs the fixation time is not a monotonically declining function of r; in particular, neutral fixation can occur faster than fixation for small selective advantages.