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$ in a population of agents sharing a resident trait $B$. 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—the probability that eventually all agents adopt the mutant trait $A$. We study the problem of fixation probability maximization: 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 $r>1$ and $r<1$, with the latter being inapproximable. For $r>1$, the optimization function is submodular, allowing for a greedy approximation within a factor $1-1/e$.

Introduction

The Biased Voter Process (BVP) serves as a fundamental model for understanding how innovations, opinions, or genetic mutations spread through a networked population. In this model, nodes represent agents and edges represent their interactions. Each node holds one of two traits: mutant ($A$) or resident ($B$). The dynamics are driven by nodes adopting the traits of their neighbors, influenced by a bias parameter $r$. When $r > 1$, the mutant trait is advantageous; when $r < 1$, it is disadvantageous.

The Biased Voter Process: nodes transition between states based on neighbor traits and bias $r$.

The central challenge is the Fixation Probability Maximization problem: selecting an initial set of $k$ "seed" nodes to maximize the likelihood that trait $A$ eventually replaces trait $B$ entirely across the network. While the neutral case ($r=1$) is well-understood and solvable by selecting high-degree nodes, the introduction of bias significantly complicates the optimization landscape.

Theoretical Complexity and Submodularity

The researchers established that for any $r \neq 1$, the maximization problem is NP-hard. This was proven through reductions from classic hard problems like vertex cover and minimum bisection.

A critical breakthrough involves the case of advantageous traits ($r > 1$). Unlike many non-progressive models where nodes can flip states indefinitely, the authors proved that the fixation probability in the BVP is both monotone and submodular. They achieved this by introducing a "node duplication" coupling technique. Submodularity is a powerful property in optimization; it ensures that a simple Greedy Algorithm—which iteratively selects the node providing the largest marginal gain in fixation probability—is guaranteed to achieve at least $(1 - 1/e) \approx 63\%$ of the optimal solution's performance.

Conversely, for disadvantageous traits ($r < 1$), the problem is far more restrictive. The authors proved that as $r$ approaches zero, the problem becomes inapproximable within any multiplicative factor, essentially requiring the seed set to form a vertex cover of the graph to ensure any significant chance of fixation.

Experimental Evaluation

The theoretical findings were validated using four real-world networks: Wiki (editor interactions), Polblogs (political blog links), Twitter (social followers), and Elegans (neural connections). In each case, the budget $k$ was set to 5% of the total nodes.

Performance of the Greedy algorithm compared to standard centrality heuristics across different network topologies.

The experiments demonstrated that while simple heuristics like High Degree or PageRank perform adequately on "easier" graphs like Wiki or Polblogs, they falter on more complex structures. On the C. elegans neural network, the Greedy algorithm significantly outperformed all other heuristics, confirming the practical utility of the submodular optimization approach for advantageous traits.

Conclusion

This work provides a comprehensive analysis of the Biased Voter Process, bridging the gap between theoretical complexity and practical algorithmic solutions. By proving submodularity for $r > 1$, the authors provide a robust framework for seeding networks with advantageous traits. Future research may focus on extending the efficient probability estimation (FPRAS) to directed graphs and developing faster heuristics that maintain the performance of the greedy approach.

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\in(0,\infty)$ 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 $r>1$ and $r<1$, while the latter case is also inapproximable within any multiplicative factor. 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