Invasion Dynamics in the Biased Voter Process

Loke Durocher, Panagiotis Karras, Andreas Pavlogiannis, Josef Tkadlec

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 biased voter process: a node is selected to be replaced by a neighbor's trait. Mutants (blue) have bias $r$ while residents (red) have bias 1.

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.

Comparison of various heuristics across four real-world datasets. The Greedy algorithm (pink) consistently outperforms others, while High PageRank (gold) serves as a strong, efficient alternative.

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

Abstract

The voter process is a classic stochastic process that models the invasion of a mutant trait A (e.g., a new opinion, belief, legend, genetic mutation, magnetic spin) in a population of agents (e.g., people, genes, particles) who share a resident trait B, spread over the nodes of a graph. An agent may adopt the trait of one of its neighbors at any time, while the invasion bias r quantifies the stochastic preference towards (r>1) or against (r<1) adopting A over B. Success is measured in terms of the fixation probability, i.e., the probability that eventually all agents have adopted the mutant trait A. In this paper we study the problem of fixation probability maximization under this model: given a budget k, find a set of k agents to initiate the invasion that maximizes the fixation probability. We show that the problem is NP-hard for both regimes r>1 and r<1, while the latter case is also inapproximable within any multiplicative factor that is independent of r. On the positive side, we show that when r>1, the optimization function is submodular and thus can be greedily approximated within a factor 1-1/e. An experimental evaluation of some proposed heuristics corroborates our results.
BibTeX
@inproceedings{durocher2022invasion,
  author = {Loke Durocher and Panagiotis Karras and Andreas Pavlogiannis and Josef Tkadlec},
  title = {{Invasion Dynamics in the Biased Voter Process}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=lvu1nYdrvsI},
}
Figure