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