Using generalized annotated programs to solve social network diffusion optimization problems

Paulo Shakarian, Matthias Broecheler, V. S. Subrahmanian, Cristian Molinaro

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


There has been extensive work in many different fields on how phenomena of interest (e.g., diseases, innovation, product adoption) "diffuse" through a social network. As social networks increasingly become a fabric of society, there is a need to make "optimal" decisions with respect to an observed model of diffusion. For example, in epidemiology, officials want to find a set of k individuals in a social network which, if treated, would minimize spread of a disease. In marketing, campaign managers try to identify a set of k customers that, if given a free sample, would generate maximal "buzz" about the product. In this article, we first show that the well-known Generalized Annotated Program (GAP) paradigm can be used to express many existing diffusion models. We then define a class of problems called Social Network Diffusion Optimization Problems (SNDOPs). SNDOPs have four parts: (i) a diffusion model expressed as a GAP, (ii) an objective function we want to optimize with respect to a given diffusion model, (iii) an integer k > 0 describing resources (e.g., medication) that can be placed at nodes, (iv) a logical condition VC that governs which nodes can have a resource (e.g., only children above the age of 5 can be treated with a given medication). We study the computational complexity of SNDOPs and show both NP-completeness results as well as results on complexity of approximation. We then develop an exact and a heuristic algorithm to solve a large class of SNDOPproblems and show that our GREEDY-SNDOP algorithm achieves the best possible approximation ratio that a polynomial algorithm can achieve (unless P = NP). We conclude with a prototype experimental implementation to solve SNDOPs that looks at a real-world Wikipedia dataset consisting of over 103,000 edges.

Original languageEnglish (US)
Article number10
JournalACM Transactions on Computational Logic
Issue number2
StatePublished - Jun 2013
Externally publishedYes


  • Approximation algorithms
  • Generalized annotated programs
  • Social network

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)
  • Logic
  • Computational Mathematics


Dive into the research topics of 'Using generalized annotated programs to solve social network diffusion optimization problems'. Together they form a unique fingerprint.

Cite this