On the fixation probability of superstars

The Moran process models the spread of genetic mutations through a population. A mutant with relative fitness r is introduced into a popu-lation and the system evolves, either reaching fixation (in which every individual is a mutant) or extinction (in which none is). In a widely cited paper (Nature, 2005), Lieberman, Hauert and Nowak generalize the model to populations on the vertices of graphs. They describe a class of graphs (called “superstars”), with a parameter k. Superstars are designed to have an increasing fixation probability as k increases. They state that the probability of fixation tends to 1 − r−k as graphs get larger but we show that this claim is untrue as stated. Specifically, for k = 5, we show that the true fixation probability (in the limit, as graphs get larger) is at most 1 − 1/j(r) where j(r) = Θ(r4), con-trary to the claimed result. We do believe that the qualitative claim of Lieberman et al. — that the fixation probability of superstars tends to 1 as k increases — is correct, and that it can probably be proved along the lines of their sketch. We were able to run larger computer simulations than the ones presented in their paper. However, simula-tions on graphs of around 40, 000 vertices do not support their claim. Perhaps these graphs are too small to exhibit the limiting behaviour. Key words: evolutionary dynamics, Moran process, fixation probability