  The Moran process, as studied by Lieberman, Hauert and Nowak, is a randomised
algorithm modelling the spread of genetic mutations in populations. The
algorithm runs on an underlying graph where individuals correspond to vertices.
Initially, one vertex (chosen u.a.r.) possesses a mutation, with fitness r>1.
All other individuals have fitness 1. During each step of the algorithm, an
individual is chosen with probability proportional to its fitness, and its
state (mutant or non-mutant) is passed on to an out-neighbour which is chosen
u.a.r. If the underlying graph is strongly connected then the algorithm will
eventually reach fixation, in which all individuals are mutants, or extinction,
in which no individuals are mutants. An infinite family of directed graphs is
said to be strongly amplifying if, for every r>1, the extinction probability
tends to 0 as the number of vertices increases. Lieberman et al. proposed two
potentially strongly-amplifying families - superstars and metafunnels.
Heuristic arguments have been published, arguing that there are infinite
families of superstars that are strongly amplifying. The same has been claimed
for metafunnels. In this paper, we give the first rigorous proof that there is
an infinite family of directed graphs that is strongly amplifying. We call the
graphs in the family "megastars". When the algorithm is run on an n-vertex
graph in this family, starting with a uniformly-chosen mutant, the extinction
probability is roughly $n^{-1/2}$ (up to logarithmic factors). We prove that
all infinite families of superstars and metafunnels have larger extinction
probabilities (as a function of n). Finally, we prove that our analysis of
megastars is fairly tight - there is no infinite family of megastars such that
the Moran algorithm gives a smaller extinction probability (up to logarithmic
factors).
