We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is a model of an evolving population on a graph where certain individuals, called "mutants" have fitness r and other individuals, called "non-mutants" have fitness 1. We focus on the situation where the mutation is advantageous, in the sense that r > 1. A family of directed graphs is said to be strongly amplifying if the extinction probability tends to 0 when the Moran process is run on graphs in this family. The most-amplifying known family of directed graphs is the family of megastars of We show that this family is optimal, up to logarithmic factors, since every strongly-connected n-vertex digraph has extinction probability Omega(n^(-1 2)). Next, we show that there is an infinite family of undirected graphs, called dense incubators, whose extinction probability is O(n^(-1 3)). We show that this is optimal, up to constant factors. Finally, we introduce sparse incubators, for varying edge density, and show that the extinction probability of these graphs is O(n m), where m is the number of edges. Again, we show that this is optimal, up to constant factors.
Our paper is otherwise incomparable to @cite_7 . We give a lower bound on the extinction probability of amplifying (Theorem ) but @cite_7 does not consider digraphs. We also construct sparse families of incubators (Theorem ) which go all the way down to constant density and are optimally-amplifying up to constant factors (Theorem ) but @cite_7 does not consider sparse graphs. On the other hand, [Theorem 3] George constructs a family of with extinction probability at least @math , which is something that we do not study here. Finally, @cite_4 have introduced a variant of the model in which the fitness of a mutant is taken to be a function of the number of vertices of the underlying digraph (so as the number of vertices in the digraph grows, the fitness of each individual mutant decreases). The results of @cite_7 extend to this model where @math , as a function of @math . We are not aware of any applications of this model, and we don't consider it.
@cite_4 @cite_7
2011047110 1798337851
We study simple interacting particle systems on heterogeneous networks, including the voter model and the invasion process. These are both two-state models in which in an update event an individual changes state to agree with a neighbor. For the voter model, an individual imports'' its state from a randomly chosen neighbor. Here the average time @math to reach consensus for a network of @math nodes with an uncorrelated degree distribution scales as @math , where @math is the @math moment of the degree distribution. Quick consensus thus arises on networks with broad degree distributions. We also identify the conservation law that characterizes the route by which consensus is reached. Parallel results are derived for the invasion process, in which the state of an agent is exported'' to a random neighbor. We further generalize to biased dynamics in which one state is favored. The probability for a single fitter mutant located at a node of degree @math to overspread the population the fixation probability is proportional to @math for the voter model and to @math for the invasion process. Let λλ be the second largest eigenvalue in absolute value of a uniform random dd-regular graph on nn vertices. It was famously conjectured by Alon and proved by Friedman that if dd is fixed independent of nn, then λ=2d−1−−−−√+o(1)λ=2d−1+o(1) with high probability. In the present work, we show that λ=O(d−−√)λ=O(d) continues to hold with high probability as long as d=O(n2 3)d=O(n2 3), making progress toward a conjecture of Vu that the bound holds for all 1≤d≤n 21≤d≤n 2. Prior to this work the best result was obtained by Broder, Frieze, Suen and Upfal (1999) using the configuration model, which hits a barrier at d=o(n1 2)d=o(n1 2). We are able to go beyond this barrier by proving concentration of measure results directly for the uniform distribution on dd-regular graphs. These come as consequences of advances we make in the theory of concentration by size biased couplings. Specifically, we obtain Bennett-type tail estimates for random variables admitting certain unbounded size biased couplings.