Sticky Seeding in Discrete-Time Reversible-Threshold Networks
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2016-03-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/1241/pdf |
| _version_ | 1811153598758780928 |
|---|---|
| author | Gwen Spencer |
| author_facet | Gwen Spencer |
| author_sort | Gwen Spencer |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:59:07Z |
| format | Article |
| id | doaj.art-fa4988f54fdf4e1f8f339b996c4b373c |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:59:07Z |
| publishDate | 2016-03-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-fa4988f54fdf4e1f8f339b996c4b373c2024-03-07T15:31:26ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502016-03-01Vol. 18 no. 3Distributed Computing and...10.46298/dmtcs.12411241Sticky Seeding in Discrete-Time Reversible-Threshold NetworksGwen SpencerWhen 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.https://dmtcs.episciences.org/1241/pdfcomputer science - social and information networks |
| spellingShingle | Gwen Spencer Sticky Seeding in Discrete-Time Reversible-Threshold Networks Discrete Mathematics & Theoretical Computer Science computer science - social and information networks |
| title | Sticky Seeding in Discrete-Time Reversible-Threshold Networks |
| title_full | Sticky Seeding in Discrete-Time Reversible-Threshold Networks |
| title_fullStr | Sticky Seeding in Discrete-Time Reversible-Threshold Networks |
| title_full_unstemmed | Sticky Seeding in Discrete-Time Reversible-Threshold Networks |
| title_short | Sticky Seeding in Discrete-Time Reversible-Threshold Networks |
| title_sort | sticky seeding in discrete time reversible threshold networks |
| topic | computer science - social and information networks |
| url | https://dmtcs.episciences.org/1241/pdf |
| work_keys_str_mv | AT gwenspencer stickyseedingindiscretetimereversiblethresholdnetworks |