License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICLP.2010.182
URN: urn:nbn:de:0030-drops-25964
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2596/
Go to the corresponding LIPIcs Volume Portal

Shakarian, Paulo ; Subrahmanian, V.S. ; Sapino, Maria Luisa

Using Generalized Annotated Programs to Solve Social Network Optimization Problems

pdf-format:
10003.ShakaranPaulo.2596.pdf (0.6 MB)

Abstract

Reasoning about social networks (labeled, directed, weighted graphs) is becoming increasingly important and there are now models of how certain phenomena (e.g. adoption of products/services by consumers, spread of a given disease) "diffuse" through the network. Some of these diffusion models can be expressed via generalized annotated programs (GAPs). In this paper, we consider the following problem: suppose we have a given goal to achieve (e.g. maximize the expected number of adoptees of a product or minimize the spread of a disease) and suppose we have limited resources to use in trying to achieve the goal (e.g. give out a few free plans, provide medication to key people in the SN) - how should these resources be used so that we optimize a given objective function related to the goal? We define a class of social network optimization problems (SNOPs) that supports this type of reasoning. We formalize and study the complexity of SNOPs and show how they can be used in conjunction with existing economic and disease diffusion models.

BibTeX - Entry

@InProceedings{shakarian_et_al:LIPIcs:2010:2596,
  author =	{Paulo Shakarian and V.S. Subrahmanian and Maria Luisa Sapino},
  title =	{{Using Generalized Annotated Programs to Solve Social Network Optimization Problems}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{182--191},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Manuel Hermenegildo and Torsten Schaub},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2596},
  URN =		{urn:nbn:de:0030-drops-25964},
  doi =		{10.4230/LIPIcs.ICLP.2010.182},
  annote =	{Keywords: Annotated logic programming, optimization queries, social networks}
}

Keywords: Annotated logic programming, optimization queries, social networks
Collection: Technical Communications of the 26th International Conference on Logic Programming
Issue Date: 2010
Date of publication: 25.06.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI