Using Generalized Annotated Programs to Solve Social Network Diffusion Optimization Problems

Abstract

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 paper, 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 SNDOP problems 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 data set consisting of over 103,000 edges.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2013
Accession Number
ADA591807

Entities

People

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

Organizations

  • United States Military Academy

Tags

Communities of Interest

  • Biomedical

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computer Programming
  • Computer Programs
  • Computer Science
  • Computers
  • Data Sets
  • Electronic Messaging
  • Mobile Phones
  • Network Science
  • Optimization
  • Social Media
  • Social Networks
  • Social Sciences
  • Sociology
  • Trees (Data Structures)
  • United States Military Academy

Fields of Study

  • Computer science

Readers

  • Defense Technology Research and Development.
  • Graph Algorithms and Convex Optimization.
  • Neural Network Machine Learning.