Abstract
This paper explores evolutionary dynamics on graph-structured populations, introducing a novel "aggregation" model and identifying the first known class of undirected graphs that significantly suppress natural selection. Unlike traditional binary replacement models, the aggregation model allows for continuous fitness influence, which we prove always converges to a stable state. Furthermore, we demonstrate that "clique-wheel" topologies act as powerful suppressors of selection, effectively halving the fixation probability of beneficial mutants compared to well-mixed populations.
Introduction
The study of how traits spread through populations—evolutionary dynamics—has traditionally relied on the assumption of a "well-mixed" population where every individual interacts with every other. The Moran process generalized this to networks, where edges define reproductive opportunities. However, existing models often struggle with two issues: the "all-or-nothing" nature of fixation and the extreme difficulty of identifying undirected graph structures that suppress, rather than amplify, natural selection.
The Moran Process and the Search for Suppressors
In the standard Moran process, a mutant with fitness $r$ is introduced into a population of residents with fitness 1. The process ends when the mutant either takes over the entire network (fixation) or goes extinct.
While "amplifiers of selection" (graphs that increase fixation probability) are well-documented, "suppressors of selection" (graphs that decrease it) are rare, especially in undirected networks. Finding such structures is critical for understanding how certain social or biological architectures might resist the spread of invasive traits.
The Aggregation Model: Evolution as Influence
To address the limitations of binary replacement, we propose the Aggregation Model. In this framework, every individual $u$ maintains a continuous fitness value $r_u$. Instead of one individual replacing another, fitness updates occur through mutual influence. At each discrete time step, an individual's fitness is updated as a weighted average of their neighbors' fitnesses, where the weights are determined by the neighbors' own current fitness levels.
This model captures "aggregation" scenarios, such as the blending of cultural traits or the gradual shift in social opinions, rather than the discrete replacement seen in the Moran process. Using a potential function approach, we prove that for any connected undirected graph, this non-linear dynamical system is guaranteed to converge to a homogeneous state where all individuals share the same fitness value.
Structural Analysis of the Clique-Wheel
A major contribution of this work is the identification of the clique-wheel graph, $G_n$, as a significant suppressor of selection. A clique-wheel consists of a central $n$-clique where every node is connected to a corresponding node on an outer cycle via a perfect matching.
The suppression effect arises from the graph's compartmentalization. A mutant starting in the central clique finds it difficult to "invade" the outer cycle, while a mutant starting in the cycle struggles to dominate the highly connected clique. This structural tension creates a barrier to fixation that is absent in complete graphs.
Key Results and Convergence
Our analysis yields several landmark results:
- Suppression Bounds: For the clique-wheel $G_n$, the fixation probability is bounded by $\frac{1}{2}(1 - 1/r)$ as $n \to \infty$. This confirms $G_n$ as a robust suppressor in the undirected regime.
- Convergence Rates: In well-mixed populations (complete graphs), the aggregation model reaches stability rapidly, specifically in $O(n \ln(r/\epsilon))$ iterations for an $\epsilon$-stable state.
- Limit Fitness: We provide tight bounds on the final population fitness. For a single mutant with fitness $r$, the final stable fitness $r_0$ is approximately $1 + \frac{r-1}{n}$.
- Invasion Control: The model allows for the design of "control strategies." By periodically introducing "stabilizers" (residents with fitness 1), we show that a network can be "cleaned" of high-fitness mutants in a number of phases logarithmic to the initial mutant fitness.
Conclusion and Future Directions
The aggregation model provides a smoother, more realistic framework for studying influence and trait spread on networks. The discovery of the clique-wheel as a suppressor opens new avenues in structural graph theory and evolutionary biology. Future work will extend these models to directed graphs, where influence is asymmetric, and explore the dynamics of multiple competing mutant types on complex, real-world topologies like scale-free networks.
Summary updated