  The Moran process is a classic stochastic process that models invasion
dynamics on graphs. A single "mutant" (e.g., a new opinion, strain, social
trait etc.) invades a population of residents spread over the nodes of a graph.
The mutant fitness advantage $\delta\geq 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., a bacterial mutation allowing
for lactose metabolism only confers an advantage on places where dairy products
are present. 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. The associated optimization problem is
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, thus
indicating strong computational hardness. Then we focus on two natural limits.
In the limit of $\delta\to\infty$ (strong selection), although the problem
remains NP-hard, the optimization function becomes submodular and thus admits a
constant-factor approximation using a simple greedy algorithm. In the limit of
$\delta\to 0$ (weak selection), we show that in $O(m^\omega)$ time we can
obtain a tight approximation, where $m$ is the number of edges and $\omega$ is
the matrix-multiplication exponent. Finally, we present an experimental
evaluation of the new algorithms together with some proposed heuristics.
