Explaining snapshots of network diffusions: Structural and hardness results

Georgios Askalidis*, Randall A. Berry, Vijay G. Subramanian

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

Much research has been done on studying the diffusion of ideas or technologies on social networks including the Influence Maximization problem and many of its variations. Here, we investigate a type of inverse problem. Given a snapshot of the diffusion process, we seek to understand if the snapshot is feasible for a given dynamic, i.e., whether there is a limited number of nodes whose initial adoption can result in the snapshot in finite time. While similar questions have been considered for epidemic dynamics, here, we consider this problem for variations of the deterministic Linear Threshold Model, which is more appropriate for modeling strategic agents. Specifically, we consider both sequential and simultaneous dynamics when deactivations are allowed and when they are not. Even though we show hardness results for all variations we consider, we show that the case of sequential dynamics with deactivations allowed is significantly harder than all others. In contrast, sequential dynamics make the problem trivial on cliques even though it's complexity for simultaneous dynamics is unknown. We complement our hardness results with structural insights that can lead to better understanding of diffusions on social networks under various dynamics.

Original languageEnglish (US)
Title of host publicationComputing and Combinatorics - 20th International Conference, COCOON 2014, Proceedings
PublisherSpringer Verlag
Pages616-625
Number of pages10
ISBN (Print)9783319087825
DOIs
StatePublished - 2014
Event20th International Computing and Combinatorics Conference, COCOON 2014 - Atlanta, GA, United States
Duration: Aug 4 2014Aug 6 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8591 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other20th International Computing and Combinatorics Conference, COCOON 2014
Country/TerritoryUnited States
CityAtlanta, GA
Period8/4/148/6/14

Keywords

  • NP-hardness
  • linear threshold model
  • social influence

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Explaining snapshots of network diffusions: Structural and hardness results'. Together they form a unique fingerprint.

Cite this