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 model for invasion dynamics on graphs, where a single "mutant" (e.g., a new opinion or social trait) spreads through a population of residents. Traditionally, a mutant's fitness advantage $\delta \geq 0$ is assumed to be uniform across the network. In this paper, we introduce the positional Moran process, a generalization where the mutant fitness advantage is realized only on specific "active nodes." We address the Fixation Maximization (FM) problem: given a budget $k$, which nodes should be activated to maximize the probability that the mutant eventually takes over the entire population? We prove that while the general problem is NP-hard and non-submodular, it becomes computationally tractable in the limits of strong selection ($\delta \to \infty$) and weak selection ($\delta \to 0$).

Introduction: The Positional Twist

In realistic settings, a mutant's advantage is often context-dependent. For instance, a bacterial mutation for lactose metabolism only confers an advantage in environments where dairy products are present. Similarly, a political viewpoint might only gain traction in specific neighborhoods. The positional Moran process models these scenarios by designating a subset of nodes as active.

The Moran process involves birth-death dynamics where nodes are replaced based on relative fitness.

In this model, the fixation probability depends heavily on the placement of these active nodes. The FM problem seeks the optimal configuration of $k$ active nodes to maximize the mutant's chance of survival and eventual dominance.

Computational Complexity and Methods

The authors analyze the FM problem across different fitness intensities:

  1. General Case: For finite $\delta$, the problem is NP-hard and the optimization function is not submodular. This lack of submodularity means that a simple greedy approach—picking the best node one by one—is not guaranteed to be effective, as the marginal benefit of adding an active node can actually increase with the total number of active nodes.
  2. Strong Selection ($\delta \to \infty$): In this limit, mutants are vastly superior on active nodes. While the problem remains NP-hard, the optimization function becomes submodular. This allows for a greedy algorithm that provides a $(1 - 1/e)$ approximation of the optimal solution.
  3. Weak Selection ($\delta \to 0$): When the advantage is infinitesimal, the problem can be solved exactly in $O(m^\omega)$ time using matrix multiplication techniques, where $m$ is the number of edges and $\omega$ is the matrix-multiplication exponent.

Key Insights: The Weak vs. Strong Divide

A critical finding of the research is that the optimal strategy for node activation changes fundamentally based on the intensity of selection.

The difference in fixation probability between 'Spaced' and 'Contiguous' node configurations flips as selection intensity (δ) changes.

As shown in the figure above, for strong selection (high $\delta$), a "Spaced" configuration—where active nodes are distributed throughout the network—tends to be superior. Conversely, under weak selection (low $\delta$), a "Contiguous" configuration—where active nodes are clustered together—often performs better. This suggests that there is no single "best" set of nodes; the optimal locations depend entirely on how much of an advantage the new trait provides.

Experimental Results

The researchers evaluated their algorithms on 110 connected subgraphs from the Stanford Network Analysis Project (SNAP). Key findings include:

  • Lazy Greedy Performance: The algorithm designed for strong selection consistently outperformed common network heuristics (like degree or centrality) for small budgets.
  • Vertex Cover Connection: Under strong selection, activating nodes that form a "Vertex Cover" proved highly effective. By covering many edges, these nodes effectively "guard" mutants from being replaced by residents.
  • Heuristic Limitations: Strategies that work well for weak selection perform poorly under strong selection, reinforcing the need for selection-aware optimization.

Conclusion

By introducing the positional Moran process, this work bridges the gap between abstract evolutionary models and spatially-constrained optimization problems. While the general problem remains computationally challenging, the identification of submodularity in the strong selection limit and exact solutions for weak selection provides a robust toolkit for managing the spread of traits or ideas in complex networks.

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 $\delta\geq 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., a bacterial mutation allowing for lactose metabolism only confers an advantage on places where dairy products are present. 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. The associated optimization problem is 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. Then we focus on two natural limits. In the limit of $\delta\to\infty$ (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 $\delta\to 0$ (weak selection), we show that in $O(m^\omega)$ time we can obtain a tight approximation, where $m$ is the number of edges and $\omega$ is the matrix-multiplication exponent. Finally, we present an experimental evaluation of the new algorithms together with some proposed heuristics.
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