Summary

As social networks such as Facebook, Twitter, Myspace, LinkedIn, LiveJournal and others get increasingly larger, a whole plethora of new applications are now possible. For example:

• Public health professionals using a disease spread model may want to know how best to distribute a limited supply of vaccines or medications so that the expected spread of the disease can be minimized, or
• Marketers for a given product may want to determine which individuals in a social network should be influenced (e.g. via a limited supply of free product samples) to maximize the expected number of people who might recommend the product

Numerous diffusion models have been developed in the sociology, medical, business, and technology communities, to understand how certain phenomena spread through a network. Most existing work assumes the network is just a graph, which is unrealistic. In fact, diffusions are influenced not only by the structure of the graph, but also by the properties of the nodes (e.g. male vs. female, under 20 vs. 20-30 vs. 30-40, vs. 40+ age groups, etc) and the properties of the edges (e.g. spouse vs. work-colleague). We start with a definition of a social network rich enough to take node and edge properties into account and show how a variant of Generalized Annotated (logic) Programs (or GAPs, due to Kifer and Subrahmanian) can be used to capture many existing diffusion models.

Informally speaking, a social network optimization problem takes (i) a social network, (ii) a diffusion model expressed as a GAP, (iii) a set of resources, and (iv) an objective function. It tries to determine where in the network to place the resources so that diffusion model (with this placement of resources) optimizes the objective function.

We develop a theoretical framework and algorithms to express and solve social network optimization problems – an improved version of our first algorithm for solving the social network optimization problems is currently being implemented.

For additional information, please contact Prof. V.S. Subrahmanian.

Last updated: June 2010 by Paulo Shakarian.

Research and implementation of this project is performed jointly by members of the University of Maryland and the Università di Torino.

Project Contributors

Publications

This page will be updated as our work enters print. For information about receiving draft publications, technical reports, and conference presentations, please do not hesitate to contact team members.

Coming Soon!

The following sections may include links to restricted access material. Please do not hesitate to contact a group member for instructions regarding how to obtain a username and password.

For access to any software, please contact Prof. V.S. Subrahmanian.