Maximizing the Probability of Fixation in the Positional Voter Model

Petros Petsinis, Andreas Pavlogiannis, Panagiotis Karras

Abstract

The Voter model is a well-studied stochastic process that models the invasion of a novel trait $A$ (e.g., a new opinion, social meme, genetic mutation, magnetic spin) in a network of individuals carrying an existing resident trait $B$. Individuals change traits by occasionally sampling the trait of a neighbor, while an invasion bias $\delta\geq 0$ expresses the stochastic preference to adopt the novel trait $A$ over the resident trait $B$. The strength of an invasion is measured by the probability that eventually the whole population adopts trait $A$, i.e., the fixation probability. In more realistic settings, however, the invasion bias is not ubiquitous, but rather manifested only in parts of the network. In this paper, we generalize the standard biased Voter model to the positional Voter model, in which the invasion bias is effectuated only on an arbitrary subset of the network nodes, called biased nodes. We study the ensuing optimization problem, which is, given a budget $k$, to choose $k$ biased nodes so as to maximize the fixation probability of a randomly occurring invasion. We show that the problem is NP-hard both for finite $\delta$ and when $\delta \rightarrow \infty$ (strong bias), while the objective function is not submodular in either setting. On the other hand, we show that, when $\delta\rightarrow 0$ (weak bias), we can obtain a tight approximation in $O(n^{2\omega})$ time. We complement our theoretical results with an experimental evaluation of some proposed heuristics.

Introduction: The Positional Voter Model

The classic Voter model describes how opinions or genetic mutations spread through a population. In its standard form, a new trait $A$ has a global advantage over the resident trait $B$. However, real-world scenarios often involve localized advantages—such as targeted marketing incentives or niche environmental benefits.

The Positional Voter Model (PVM) addresses this by restricting the invasion bias $\delta$ to a specific subset of nodes, $S$. In this model, an agent at a biased node is more likely to adopt trait $A$ from a neighbor than trait $B$. The central question is: given a budget $k$, which nodes should be selected for $S$ to maximize the fixation probability—the likelihood that trait $A$ eventually replaces trait $B$ entirely across the network?

Figure 1: Illustration of the Voter model dynamics. Traits are adopted through neighbor sampling, with biased nodes (highlighted) showing a higher propensity to adopt the invading trait.

Computational Complexity and Theoretical Bounds

The optimization of fixation probability in the PVM is computationally challenging. The authors demonstrate that the problem is NP-hard for both finite bias and the "strong bias" limit ($\delta \to \infty$). Furthermore, the objective function is generally not submodular, which precludes the use of standard greedy algorithms with guaranteed approximation ratios in the general case.

However, specific conditions offer tractability:

  • Weak Bias ($\delta \to 0$): When the advantage of the new trait is marginal, the problem can be solved exactly in $O(n^{2\omega})$ time using linear algebra.
  • Strong Bias with Self-Loops: If the graph includes self-loops (representing an agent's tendency to maintain their current trait), the objective function becomes submodular as $\delta \to \infty$. This allows a greedy algorithm to achieve a $(1 - 1/e)$ approximation guarantee.

Experimental Evaluation of Heuristics

To bridge the gap between theoretical hardness and practical application, the researchers evaluated several centrality-based heuristics against a Greedy approach and a Vertex Cover-based strategy. The experiments utilized 100 strongly connected components from real-world social networks (sizes 20–130 nodes) sourced from the Netzschleuder catalogue.

Figure 6: Performance comparison of various node selection heuristics. Vertex Cover and Degree-based selection consistently outperform standard centrality measures like Closeness or Betweenness.

The results indicate that Vertex Cover and Degree are robust proxies for maximizing fixation probability under strong bias. In contrast, standard measures like Betweenness or Closeness centrality often fail to capture the "coverage" necessary to ensure trait fixation. Random selection performs significantly worse, particularly when the budget $k$ is small (e.g., 10% of the network), emphasizing the importance of strategic node placement.

Key Insights

  • The Role of Self-Loops: Self-loops act as a regularizer, making the optimization landscape more manageable (submodular) in the strong-bias limit.
  • Vertex Cover as Strategy: In regular graphs with self-loops, the optimal strategy under strong bias is equivalent to finding a minimum Vertex Cover, suggesting that "covering" the edges of the network is critical.
  • Non-Progressive Dynamics: Unlike simpler cascade models where trait changes are permanent, the Voter model allows traits to be lost and regained. This stochastic "back-and-forth" necessitates a more nuanced optimization approach than simple reachability.

Conclusion and Future Directions

The Positional Voter Model provides a realistic framework for targeted interventions in networked populations. While the general problem is hard, the identification of tractable regimes (weak bias) and effective heuristics (Vertex Cover) provides a roadmap for practical applications. Future work may extend these findings to directed, non-symmetric graphs and seek tighter approximation bounds for the finite-bias regime.

Summary updated

Abstract

The Voter model is a well-studied stochastic process that models the invasion of a novel trait $A$ (e.g., a new opinion, social meme, genetic mutation, magnetic spin) in a network of individuals (agents, people, genes, particles) carrying an existing resident trait $B$. Individuals change traits by occasionally sampling the trait of a neighbor, while an invasion bias $\delta\geq 0$ expresses the stochastic preference to adopt the novel trait $A$ over the resident trait $B$. The strength of an invasion is measured by the probability that eventually the whole population adopts trait $A$, i.e., the fixation probability. In more realistic settings, however, the invasion bias is not ubiquitous, but rather manifested only in parts of the network. For instance, when modeling the spread of a social trait, the invasion bias represents localized incentives. In this paper, we generalize the standard biased Voter model to the positional Voter model, in which the invasion bias is effectuated only on an arbitrary subset of the network nodes, called biased nodes. We study the ensuing optimization problem, which is, given a budget $k$, to choose $k$ biased nodes so as to maximize the fixation probability of a randomly occurring invasion. We show that the problem is NP-hard both for finite $\delta$ and when $\delta \rightarrow \infty$ (strong bias), while the objective function is not submodular in either setting, indicating strong computational hardness. On the other hand, we show that, when $\delta\rightarrow 0$ (weak bias), we can obtain a tight approximation in $O(n^{2\omega})$ time, where $\omega$ is the matrix-multiplication exponent. We complement our theoretical results with an experimental evaluation of some proposed heuristics.
BibTeX
@inproceedings{petsinis2023maximizing,
  author = {Petros Petsinis and Andreas Pavlogiannis and Panagiotis Karras},
  title = {{Maximizing the Probability of Fixation in the Positional Voter Model}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=qPaAt6ihHVT},
}
Figure