TY - GEN

T1 - Maximizing the Probability of Fixation in the Positional Voter Model

AU - Petsinis, Petros

AU - Pavlogiannis, Andreas

AU - Karras, Panagiotis

N1 - Publisher Copyright:
Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

PY - 2023/6/27

Y1 - 2023/6/27

N2 - 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 δ ≥ 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 δ and when δ → ∞ (strong bias), while the objective function is not submodular in either setting, indicating strong computational hardness. On the other hand, we show that, when δ → 0 (weak bias), we can obtain a tight approximation in O(n2ω) time, where ω is the matrix-multiplication exponent. We complement our theoretical results with an experimental evaluation of some proposed heuristics.

AB - 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 δ ≥ 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 δ and when δ → ∞ (strong bias), while the objective function is not submodular in either setting, indicating strong computational hardness. On the other hand, we show that, when δ → 0 (weak bias), we can obtain a tight approximation in O(n2ω) time, where ω is the matrix-multiplication exponent. We complement our theoretical results with an experimental evaluation of some proposed heuristics.

UR - http://www.scopus.com/inward/record.url?scp=85168245962&partnerID=8YFLogxK

M3 - Article in proceedings

AN - SCOPUS:85168245962

T3 - Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023

SP - 12269

EP - 12277

BT - AAAI-23 Technical Tracks 10

A2 - Williams, Brian

A2 - Chen, Yiling

A2 - Neville, Jennifer

PB - AAAI Press

T2 - 37th AAAI Conference on Artificial Intelligence, AAAI 2023

Y2 - 7 February 2023 through 14 February 2023

ER -