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.
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:
- 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.
- 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.
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