Network growth for enhanced natural selection

On the fixation probability of superstars

The Moran process models the spread of genetic mutations through populations. A mutant with relative fitness r is introduced and the system evolves, either reaching fixation (an all-mutant population) or extinction (no mutants). In a widely cited paper, Lieberman et al. (2005 Evolutionary dynamics on graphs. Nature 433 , 312–316) generalize the model to populations on the vertices of graphs. They describe a class of graphs (‘superstars’), with a parameter k and state that the fixation probability tends to 1− r − k as the graphs get larger: we show that this is untrue as stated. Specifically, for k =5, we show that the fixation probability (in the limit, as graphs get larger) cannot exceed 1−1/ j ( r ), where j ( r )= Θ ( r 4 ), contrary to the claimed result. Our proof is fully rigorous, though we use a computer algebra package to invert a 31×31 symbolic matrix. We do believe the qualitative claim of Lieberman et al. —that superstar fixation probability tends to 1 as k increases—and that it can probably be proved similarly to their sketch. We were able to run larger simulations than the ones they presented. Simulations on graphs of around 40 000 vertices do not support their claim but these graphs might be too small to exhibit the limiting behaviour.

Fixation probabilities for simple digraphs

The problem of finding birth–death fixation probabilities for configurations of normal and mutants on an N -vertex graph is formulated in terms of a Markov process on the 2 N -dimensional state space of possible configurations. Upper and lower bounds on the fixation probability after any given number of iterations of the birth–death process are derived in terms of the transition matrix of this process. Consideration is then specialized to a family of graphs called circular flows, and we present a summation formula for the complete bipartite graph, giving the fixation probability for an arbitrary configuration of mutants in terms of a weighted sum of the single-vertex fixation probabilities. This also yields a closed-form solution for the fixation probability of bipartite graphs. Three entropy measures are introduced, providing information about graph structure. Finally, a number of examples are presented, illustrating cases of graphs that enhance or suppress fixation probability for fitness r >1 as well as graphs that enhance fixation probability for only a limited range of fitness. Results are compared with recent results reported in the literature, where a positive correlation is observed between vertex degree variance and fixation probability for undirected graphs. We show a similar correlation for directed graphs, with correlation not directly to fixation probability but to the difference between fixation probability for a given graph and a complete graph.

A review of evolutionary graph theory with applications to game theory

Evolutionary graph theory (EGT), studies the ability of a mutant gene to overtake a finite structured population. In this review, we describe the original framework for EGT and the major work that has followed it. This review looks at the calculation of the "fixation probability" - the probability of a mutant taking over a population and focuses on game-theoretic applications. We look at varying topics such as alternate evolutionary dynamics, time to fixation, special topological cases, and game theoretic results. Throughout the review, we examine several interesting open problems that warrant further research.

Early appraisal of the fixation probability in directed networks

In evolutionary dynamics, the probability that a mutation spreads through the whole population, having arisen from a single individual, is known as the fixation probability. In general, it is not possible to find the fixation probability analytically given the mutant's fitness and the topological constraints that govern the spread of the mutation, so one resorts to simulations instead. Depending on the topology in use, a great number of evolutionary steps may be needed in each of the simulation events, particularly in those that end with the population containing mutants only. We introduce two techniques to accelerate the determination of the fixation probability. The first one skips all evolutionary steps in which the number of mutants does not change and thereby reduces the number of steps per simulation event considerably. This technique is computationally advantageous for some of the so-called layered networks. The second technique, which is not restricted to layered networks, consists of aborting any simulation event in which the number of mutants has grown beyond a certain threshold value and counting that event as having led to a total spread of the mutation. For advantageous mutations in large populations and regardless of the network's topology, we demonstrate, both analytically and by means of simulations, that using a threshold of about [N/(r-1)](1/4) mutants, where N is the number of simulation events and r is the ratio of the mutants' fitness to that of the remainder of the population, leads to an estimate of the fixation probability that deviates in no significant way from that obtained from the full-fledged simulations. We have observed speedups of two orders of magnitude for layered networks with 10,000 nodes.