Using Generalized Annotated Programs to Solve Social Network Diffusion Optimization Problems
MILITARY ACADEMY WEST POINT NY DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE
Pagination or Media Count:
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.
- Information Science
- Operations Research