Approximating fixation probabilities in the generalized Moran process

Josep Díaz, Leslie Ann Goldberg, George B. Mertzios, David Richerby, Maria J. Serna, Paul G. Spirakis

TL;DR

This paper tackles the computationally challenging problem of predicting how likely a new "mutant" trait is to take over a population structured on a graph, or conversely, to die out. The authors develop novel approximation algorithms that can efficiently estimate these probabilities, making previously intractable problems solvable.

What Problem Does This Paper Address?

Imagine a population living on a network (like a social network or a grid). Individuals have different "fitnesses," and at each step, a fitter individual is more likely to reproduce and spread its trait. This is the generalized Moran process. A key question in evolutionary biology and game theory is: what's the probability that a single "mutant" individual (with a different fitness) will eventually spread its trait to the entire population (fixation), or conversely, disappear (extinction)?

The challenge is that calculating these probabilities exactly involves solving massive systems of equations that grow exponentially with the population size (number of vertices in the graph). This makes exact computation infeasible for anything but the smallest networks. Researchers have thus focused on specific graph structures or small populations. This paper aims to bridge this gap by providing efficient approximation algorithms that work for general graphs.

Methods

The core of the paper's contribution lies in developing Fully Polynomial Randomized Approximation Schemes (FPRAS) for both fixation and extinction probabilities.

Here's a breakdown of their approach:

  • Absorption Time Bounds: A crucial step is to show that the Moran process, regardless of the graph structure, will reach either fixation or extinction within a polynomial number of steps. They achieve this by analyzing the "potential function" of the system and proving that its expected change is bounded. This is a significant theoretical result, as it guarantees that simulations won't run indefinitely.
  • Monte Carlo Simulation: Once they establish polynomial absorption time bounds, they leverage this to design Monte Carlo algorithms. The idea is to simulate the process many times. If the absorption time is bounded by a polynomial (say, $O(n^k)$), then running the simulation for a sufficiently large number of steps (e.g., $N \cdot n^k$) will capture the outcome with high probability.
  • FPRAS Construction: For fixation (when the mutant fitness $r \ge 1$), they use these simulations to estimate the fixation probability. For extinction (for any $r > 0$), they do the same. The algorithms are designed to provide an answer within a $(1 \pm \varepsilon)$ factor of the true probability, with high confidence, and in time polynomial in the input size (graph size $n$ and fitness $r$, encoded appropriately).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development for a general Moran process on arbitrary graphs, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Universality of Polynomial Absorption Time: The most striking insight is that for any connected, undirected graph, the Moran process is guaranteed to reach fixation or extinction in a polynomial number of steps. This is a powerful result that underpins the feasibility of their approximation algorithms.
  • Bridging Theory and Practice: The paper effectively bridges a theoretical gap. While exact calculations are intractable, their work shows that efficient approximations are possible for a wide range of scenarios, making the study of evolutionary dynamics on networks more practical.
  • Distinction for $r=1$: The case where the mutant and non-mutant have equal fitness ($r=1$) is mathematically distinct. The paper shows that for $r=1$, the fixation probability is simply $1/n$ (where $n$ is the number of vertices), independent of the graph structure. This is a neat result that simplifies analysis for this specific scenario.
  • FPRAS for Extinction: The ability to provide an FPRAS for extinction probability for all fitness values $r > 0$ is a significant achievement, as it covers scenarios where mutants are disadvantageous ($r < 1$) and their fixation probability might be exponentially small, making direct simulation unreliable.

Key Results

  • Polynomial Absorption Time: The Moran process on an $n$-vertex undirected graph reaches absorption (fixation or extinction) within $O(n^4)$ steps with high probability.
  • FPRAS for Fixation ($r \ge 1$): An algorithm is presented that computes the fixation probability within a $(1 \pm \varepsilon)$ factor with high probability, running in time polynomial in $n$ and $1/\varepsilon$.
  • FPRAS for Extinction ($r > 0$): An algorithm is presented that computes the extinction probability within a $(1 \pm \varepsilon)$ factor with high probability, running in time polynomial in $n$, $r$, and $1/\varepsilon$.
  • Fixation Probability for $r=1$: For $r=1$, the fixation probability is $1/n$ for any connected undirected graph.

Limitations and Future Work

  • FPRAS for Fixation ($r < 1$): The paper notes that their FPRAS for fixation does not directly apply when $r < 1$ because there isn't a guaranteed polynomial lower bound on the fixation probability. This means an exponential number of simulations might be needed to achieve the desired accuracy. The authors leave it as an open question whether other techniques could lead to an FPRAS for this case.
  • Tightness of Bounds: The authors suggest that the $O(n^4)$ bound on absorption time might not be the tightest possible and could potentially be improved with more careful analysis. They also mention that simulations suggest $O(n^3)$ might be more typical.
  • Directed Graphs: The primary focus is on undirected graphs. While the generalized Moran process is defined for directed graphs, the approximation schemes and some theoretical bounds are more directly derived for the undirected case.

Summary updated

Abstract

We consider the Moran process, as generalized by Lieberman et al. (Nature 433:312–316, 2005). A population resides on the vertices of a finite, connected, undirected graph and, at each time step, an individual is chosen at random with probability proportional to its assigned “fitness” value. It reproduces, placing a copy of itself on a neighbouring vertex chosen uniformly at random, replacing the individual that was there. The initial population consists of a single mutant of fitness r>0 placed uniformly at random, with every other vertex occupied by an individual of fitness 1. The main quantities of interest are the probabilities that the descendants of the initial mutant come to occupy the whole graph (fixation) and that they die out (extinction); almost surely, these are the only possibilities. In general, exact computation of these quantities by standard Markov chain techniques requires solving a system of linear equations of size exponential in the order of the graph so is not feasible. We show that, with high probability, the number of steps needed to reach fixation or extinction is bounded by a polynomial in the number of vertices in the graph. This bound allows us to construct fully polynomial randomized approximation schemes (FPRAS) for the probability of fixation (when r≥1) and of extinction (for all r>0).
BibTeX
@inproceedings{diaz2012approximating,
  author = {Josep Díaz and Leslie Ann Goldberg and George B. Mertzios and David Richerby and Maria J. Serna and Paul G. Spirakis},
  title = {{Approximating fixation probabilities in the generalized Moran process}},
  booktitle = {SODA},
  year = {2012},
  doi = {10.1137/1.9781611973099.76},
}

Loading related content...

Figure