Abstract
The voter process is a classic stochastic process that models the invasion of a mutant trait A (e.g., a new opinion, genetic mutation, or magnetic spin) in a population of agents sharing a resident trait B. The invasion bias $r$ quantifies the stochastic preference towards ($r > 1$) or against ($r < 1$) adopting A over B. Success is measured by the fixation probability—the chance that all agents eventually adopt the mutant trait. This paper investigates the problem of fixation probability maximization: given a budget $k$, which $k$ agents should initiate the invasion to maximize the fixation probability? We demonstrate that the problem is NP-hard for $r \neq 1$. However, for $r > 1$, the optimization function is submodular, allowing for a $(1 - 1/e)$-greedy approximation. An experimental evaluation of proposed heuristics corroborates these theoretical findings.
Introduction
The voter process serves as a fundamental model for the diffusion of opinions, genetic mutations, or technological adoption across a network. In this model, agents occupy nodes on a graph. At each discrete time step, a random agent is chosen to "die" and is replaced by a copy of one of its neighbors. The biased version of this process introduces a parameter $r$: if $r > 1$, the mutant trait is advantageous; if $r < 1$, it is at a disadvantage.
The central challenge addressed in this work is fixation maximization: identifying the optimal set of $k$ initial mutants to maximize the probability of a total population takeover. While the neutral case ($r=1$) is computationally simple, the introduction of bias significantly complicates the dynamics, making the selection of seed nodes non-trivial.
Theoretical Complexity and Submodularity
Our analysis reveals a significant "hardness gap" when moving from neutral to biased processes. We prove that fixation maximization is NP-hard for any $r \neq 1$. Specifically:
- For $r > 1$, the problem is reduced from the minimum bisection problem on regular graphs.
- For $r < 1$, the problem is reduced from the vertex cover problem and is shown to be inapproximable within any multiplicative factor independent of $r$.
Despite this hardness, we identify a critical property for the advantageous regime ($r > 1$): the fixation probability is a monotone submodular function. Proving this required a novel "node duplication" perspective to handle the non-progressive nature of the voter process, where mutants can be lost and regained. This submodularity ensures that a standard greedy selection strategy provides a $(1 - 1/e) \approx 63\%$ approximation of the optimal solution.
Experimental Evaluation
We evaluated the greedy algorithm and several common heuristics across four diverse real-world networks from the Netzschleuder database: Wikipedia users (Wiki), political blogs (Polblogs), Twitter sub-networks, and the C. elegans neural network. These represent a variety of structures, from social networks to biological systems.
The results demonstrate that the greedy algorithm consistently achieves the highest fixation probabilities across all tested networks. Interestingly, High PageRank emerged as a highly effective and computationally inexpensive heuristic, often closely matching the greedy algorithm's performance in social network contexts. In contrast, simpler heuristics like high-degree selection were less reliable, particularly on biological networks like C. elegans.
Conclusion
This work provides a comprehensive complexity landscape for the biased voter process. While the general optimization problem is NP-hard, the discovery of submodularity for $r > 1$ offers a robust path for approximation. Future research will focus on extending these results to directed graphs and exploring structural graph properties that might further optimize heuristic performance for large-scale networks.
Summary updated