TY - JOUR
T1 - Fixation Maximization in the Positional Moran Process
AU - Brendborg, Joachim
AU - Karras, Panagiotis
AU - Pavlogiannis, Andreas
AU - Rasmussen, Asger Ullersted
AU - Tkadlec, Josef
PY - 2022/6/30
Y1 - 2022/6/30
N2 - The Moran process is a classic stochastic process that models spread dynamics on graphs. A single "mutant"(e.g., a new opinion, strain, social trait etc.) invades a population of "residents" scatteredover the nodes of a graph. The mutant fitness advantage δ ≥ 0 determines how aggressively mutants propagate to their neighbors. The quantity of interest is the fixation probability, i.e., the probability that the initial mutant eventually takes over the whole population. However, in realistic settings, the invading mutant has an advantage only in certain locations. E.g., the ability to metabolize a certain sugar is an advantageous trait to bacteria only when the sugar is actually present in their surroundings. In this paper, we introduce the positional Moran process, a natural generalization in which the mutant fitness advantage is only realized on specific nodes called active nodes, and study the problem of fixation maximization: given a budget k, choose a set of k active nodes that maximize the fixation probability of the invading mutant. We show that the problem is NP-hard, while the optimization function is not submodular, indicating strong computational hardness. We then focus on two natural limits: at the limit of δ → 1 (strong selection), although the problem remains NP-hard, the optimization function becomes submodular and thus admits a constant-factor greedy approximation; at the limit of δ → 0 (weak selection), we show that we can obtain a tight approximation in O(n2ω) time, where ω is the matrix-multiplication exponent. An experimental evaluation of the new algorithms along with some proposed heuristics corroborates our results.
AB - The Moran process is a classic stochastic process that models spread dynamics on graphs. A single "mutant"(e.g., a new opinion, strain, social trait etc.) invades a population of "residents" scatteredover the nodes of a graph. The mutant fitness advantage δ ≥ 0 determines how aggressively mutants propagate to their neighbors. The quantity of interest is the fixation probability, i.e., the probability that the initial mutant eventually takes over the whole population. However, in realistic settings, the invading mutant has an advantage only in certain locations. E.g., the ability to metabolize a certain sugar is an advantageous trait to bacteria only when the sugar is actually present in their surroundings. In this paper, we introduce the positional Moran process, a natural generalization in which the mutant fitness advantage is only realized on specific nodes called active nodes, and study the problem of fixation maximization: given a budget k, choose a set of k active nodes that maximize the fixation probability of the invading mutant. We show that the problem is NP-hard, while the optimization function is not submodular, indicating strong computational hardness. We then focus on two natural limits: at the limit of δ → 1 (strong selection), although the problem remains NP-hard, the optimization function becomes submodular and thus admits a constant-factor greedy approximation; at the limit of δ → 0 (weak selection), we show that we can obtain a tight approximation in O(n2ω) time, where ω is the matrix-multiplication exponent. An experimental evaluation of the new algorithms along with some proposed heuristics corroborates our results.
UR - http://www.scopus.com/inward/record.url?scp=85143573955&partnerID=8YFLogxK
U2 - 10.1609/aaai.v36i9.21160
DO - 10.1609/aaai.v36i9.21160
M3 - Journal article
SN - 2374-3468
VL - 36
SP - 9304
EP - 9312
JO - Proceedings of the AAAI Conference on Artificial Intelligence
JF - Proceedings of the AAAI Conference on Artificial Intelligence
IS - 9, AAAI Technical Track on Multiagent Systems
ER -