Sticky Seeding in Discrete-Time Reversible-Threshold Networks
Authors: Gwen Spencer
NULL
Gwen Spencer
When nodes can repeatedly update their behavior (as in agent-based models
from computational social science or repeated-game play settings) the problem
of optimal network seeding becomes very complex. For a popular
spreading-phenomena model of binary-behavior updating based on thresholds of
adoption among neighbors, we consider several planning problems in the design
of \textit{Sticky Interventions}: when adoption decisions are reversible, the
planner aims to find a Seed Set where temporary intervention leads to long-term
behavior change. We prove that completely converting a network at minimum cost
is $\Omega(\ln (OPT) )$-hard to approximate and that maximizing conversion
subject to a budget is $(1-\frac{1}{e})$-hard to approximate. Optimization
heuristics which rely on many objective function evaluations may still be
practical, particularly in relatively-sparse networks: we prove that the
long-term impact of a Seed Set can be evaluated in $O(|E|^2)$ operations. For a
more descriptive model variant in which some neighbors may be more influential
than others, we show that under integer edge weights from $\{0,1,2,...,k\}$
objective function evaluation requires only $O(k|E|^2)$ operations. These
operation bounds are based on improvements we give for bounds on
time-steps-to-convergence under discrete-time reversible-threshold updates in
networks.