Fixation Maximization in the Positional Moran Process

Joachim Brendborg, Panagiotis Karras, Andreas Pavlogiannis, Asger Ullersted Rasmussen, Josef Tkadlec

Abstract

The Moran process is a classic stochastic process that models invasion dynamics on graphs. A single mutant invades a population of residents spread over the nodes of a graph. The mutant fitness advantage $\delta \ge 0$ determines how aggressively mutants propagate to their neighbors. The quantity of interest is the fixation probability—the probability that the initial mutant eventually takes over the whole population. However, in realistic settings, the invading mutant has an advantage only in certain locations. We introduce the positional Moran process, a natural generalization in which the mutant fitness advantage is only realized on specific nodes called active nodes, and study the problem of fixation maximization: given a budget $k$, choose a set of $k$ active nodes that maximize the fixation probability of the invading mutant. We show that the problem is NP-hard and the optimization function is not submodular. We provide efficient algorithms for the limits of strong selection ($\delta \to \infty$) and weak selection ($\delta \to 0$).

Introduction: The Positional Moran Process

In evolutionary graph theory, the Moran process traditionally assumes a uniform fitness advantage for mutants across an entire network. However, real-world traits often provide advantages only in specific environments—for instance, a bacterial strain might only thrive where a particular nutrient is present.

The Moran process: a mutant (blue) replaces a resident (red) on a graph. In the positional variant, fitness is boosted only on active nodes.

This paper introduces the Positional Moran Process, where mutants receive a fitness boost $1+\delta$ only when occupying a node in a pre-selected "active set" $S$. The Fixation Maximization (FM) problem asks: given a budget $k$, which $k$ nodes should be activated to maximize the probability that a single mutant eventually replaces all residents?

Computational Complexity and Optimization Regimes

The authors demonstrate that FM is generally NP-hard and lacks submodularity for finite $\delta$. Submodularity is a "diminishing returns" property that typically allows greedy algorithms to perform well. Its absence indicates significant computational hardness. To address this, the research focuses on two critical limits:

  1. Strong Selection ($\delta \to \infty$): As the fitness advantage becomes infinite, mutants on active nodes become nearly impossible to displace. While the problem remains NP-hard, the optimization function becomes submodular in this regime. This allows for a Lazy Greedy algorithm that achieves a $(1 - 1/e)$ approximation.
  2. Weak Selection ($\delta \to 0$): When the advantage is marginal, the contribution of each node to the fixation probability becomes additive. The authors developed a Weak Selector algorithm that finds the optimal set in $O(n^{2\omega})$ time by calculating individual "impact scores" for each node.

Key Insights: The Guard Effect and Submodularity Shift

A central theoretical finding is the emergence of submodularity at the limit of strong selection. This is driven by the "Guard" effect: on undirected graphs, an active node with infinite fitness acts as a fortress. Once a mutant occupies it, it reproduces so rapidly that its neighbors are almost always mutants, effectively shielding the active node from resident re-invasion.

Fixation probability difference between spaced and contiguous active nodes on a ring graph. For high $\delta$, spacing nodes is superior.

The spatial arrangement of these "guards" is crucial. As shown in the figure above, for high $\delta$, a "Spaced" configuration of active nodes leads to a higher fixation probability than a "Contiguous" one. This is because spaced guards can protect larger portions of the network more effectively.

Experimental Results

The algorithms were tested on 110 subgraphs from the SNAP social network datasets. Key findings include:

  • Superiority of Targeted Activation: The proposed Lazy Greedy and Weak Selector algorithms consistently outperformed standard network heuristics like High Degree, Betweenness Centrality, and Temperature.
  • Vertex Cover Heuristic: Under strong selection, a heuristic based on the Vertex Cover problem performed remarkably well, supporting the intuition that "covering" edges with protected mutant zones is an optimal strategy.
  • Random Baseline: Randomly selecting active nodes resulted in significantly lower fixation probabilities, proving that the specific placement of environmental advantages is a primary driver of evolutionary success.

Conclusion and Future Work

This work provides a rigorous framework for understanding how localized advantages influence global invasion dynamics. While the extremes of selection strength are now computationally tractable, the "middle ground" of finite $\delta$ remains an open challenge due to the lack of submodularity. Future research may explore directed graphs—where "evolutionary traps" can complicate dynamics—and identify specific graph classes where the general FM problem might be solvable.

Summary updated

Abstract

The Moran process is a classic stochastic process that models invasion dynamics on graphs. A single mutant (e.g., a new opinion, strain, social trait etc.) invades a population of residents spread over the nodes of a graph. The mutant fitness advantage δ>=0 determines how aggressively mutants propagate to their neighbors. The quantity of interest is the fixation probability, i.e., the probability that the initial mutant eventually takes over the whole population. However, in realistic settings, the invading mutant has an advantage only in certain locations. E.g., the ability to metabolize a certain sugar is an advantageous trait to bacteria only when the sugar is actually present in their surroundings. In this paper we introduce the positional Moran process, a natural generalization in which the mutant fitness advantage is only realized on specific nodes called active nodes, and study the problem of fixation maximization: given a budget k, choose a set of k active nodes that maximize the fixation probability of the invading mutant. We show that the problem is NP-hard, while the optimization function is not submodular, thus indicating strong computational hardness. We focus on two natural limits. In the limit of δ to infinity (strong selection), although the problem remains NP-hard, the optimization function becomes submodular and thus admits a constant-factor approximation using a simple greedy algorithm. In the limit of δ to 0 (weak selection), we show that we can obtain a tight approximation in O(n^{2×ω}) time, where ω is the matrix-multiplication exponent. An experimental evaluation of the new algorithms along with some proposed heuristics corroborates our results.
BibTeX
@inproceedings{brendborg2022fixation,
  author = {Joachim Brendborg and Panagiotis Karras and Andreas Pavlogiannis and Asger Ullersted Rasmussen and Josef Tkadlec},
  title = {{Fixation Maximization in the Positional Moran Process}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=URDpkrEs7q},
}
Figure