Network growth for enhanced natural selection

Natural selection and random drift are competing phenomena for explaining the evolution of populations. Combining a highly fit mutant with a population structure that improves the odds that the mutation spreads through the whole population tips the balance in favor of natural selection. The probability that the spread occurs, known as the fixation probability, depends heavily on how the population is structured. Certain topologies, albeit highly artificially contrived, have been shown to exist that favor fixation. We present a randomized mechanism for network growth that is loosely inspired in some of these topologies’ key properties and demonstrate, through simulations, that it is capable of giving rise to structured populations for which the fixation probability significantly surpasses that of an unstructured population. This discovery provides important support to the notion that natural selection can be enhanced over random drift in naturally occurring population structures.

Figure 1

The 3-funnel for $b=3$. Edges connect back to the nodes in layer 2 from the single node in layer 0.

Figure 2

$D_t$ is the graph comprising all nodes but $i$ and all solid-line edges. Adding node $i$ to layer 1 and the edges shown as dotted lines yields $D_{t+1}$. Edges connect back to the nodes in layer 2 from the single node in layer 0.

Figure 3

(Color online) Simulation results for $K=5$. Each graph $D$ for which $C\left(X,Y\right)>0.9$ is represented by its fixation probability and by the slope $S\left(X,Y\right)$. For each combination of $n$ and $r$, 500 graphs are shown, corresponding roughly to 12% of the number of graphs that were grown. Dashed lines mark ${\rho }_1$ through ${\rho }_3$ for $r=1.1$, ${\rho }_1$ for $r=2.0$.

Figure 4

(Color online) Simulation results for the 3-funnel. Dashed lines mark the values of ${\rho }_3$.

Figure 5

(Color online) Simulation results for $K=10$, $n=10000$, and $r=1.1$. Each graph $D$ having $C\left(X,Y\right)>0.9$ is represented by its fixation probability and by the slope $S\left(X,Y\right)$. There are 100 graphs, corresponding roughly to 0.04% of the graphs that were grown. Dashed lines mark ${\rho }_1$ through ${\rho }_3$.