  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.

Populations and Evolution;Computational Complexity;Computer Science and Game Theory;Social and Information Networks