CDP
Competitive Diffusion Problems
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, a political candidate may wish to determine how support for him is spreading in the presence of competing messages from his opponent.
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.
The goal of competitive diffusion problems is to understand how the diffusion process is eventually resolved (e.g., is there more expected support for candidate A or candidate B?) We have developed efficient algorithms to solve competitive diffusion problems in the presence of any diffusion models (for the competing processes) that are expressible as Generalized Annotated (logic) Programs.
We have tested out our competitive diffusion models on social network data gleaned from several different social networks. We show experimentally that we can solve such general competitive diffusion problems in a few hours on social networks containing approximately 2 million nodes and 8 million edges.
We are now in the process of adapting these algorithms to also scalably solve Social Network Optimization Problems.
For additional information, please contact Dr. V.S. Subrahmanian.
Last updated: June 2010 by John Dickerson
Research and implementation of this project is performed by members of the University of Maryland.
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.
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.