| Abstract | Reasoning about social networks (labeled, directed, weighted graphs) is be-coming 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.
|
