Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Sticky Seeding In Discrete-Time Reversible-Threshold Networks, Gwen Spencer
Sticky Seeding In Discrete-Time Reversible-Threshold Networks, Gwen Spencer
Mathematics Sciences: Faculty Publications
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 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 Ω(ln(OP T ))-hard to approximate and that maximizing conversion subject to a budget is …