SNR
Social Networks Research
Facebook, MySpace, LiveJournal and LinkedIn are just a few examples of the rapid proliferation of social networks around the world. In addition, popular services like YouTube and Flickr offer a wide variety of social networking capabilities as do many commercial sites like Amazon and Shutterfly.
The ability to query social networking sites, understand how phenomena spread in a social network, and make intelligent decisions in social networks is key for many applications. Our lab focuses on developing theoretically well grounded algorithms that work on massive social networks consisting of millions to billions of edges. These applications include everything from marketing applications to political events to predicting and controlling the spread of diseases. Specific social networking projects in our group are listed below.
DOGMA (“Disk-Oriented Graph Matching Algorithm”): As social networks get increasingly larger, efficient indexes need to be developed in order to support very basic social network operations such as graph matching. The DOGMA system is the first disk-based index specialized for subgraph matching (with complex query subgraphs) against a database with tens of millions of edges. In a large experimental study it was shown that DOGMA outperforms other state of the art graph databases by orders of magnitude on complex subgraph matching queries, yielding answers to such queries over a graph with 15 million edges in milliseconds where other systems took seconds or even minutes to respond.
COSI (“Cloud Oriented Subgraph Identification”): COSI is the first algorithm to perform subgraph matching of complex query subgraphs against a social network database consisting of 778M edges in under a second. We have subsequently extended these results to social network databases with over a billion edges.
Social Network Optimization Problems: Consider a social network of people, some of who are known to have a given disease, and suppose a diffusion model exists in the epidemiology community for the spread of such diseases. Given a finite amount of medicine or vaccine, which nodes should receive the medicine so that the expected number of people infected (w.r.t. the diffusion model) is minimized. This is an example of a social network optimization problem. We formally define a syntax (based on Kifer and Subrahmanian's Generalized Annotated (logic) Program framework) within which to express diffusion models and social network optimization problems and provide general algorithms to solve them. Our framework is rich enough to express many existing social network diffusion models in epidemiology, marketing, and politics, and our algorithms can solve any social network optimization problem in this framework.
Competitive Diffusion Models: Suppose we have multiple diffusion models diffusing competing phenomena through a network (e.g. support for political candidate A vs. B) and we wish to determine what the most likely outcome of the competing diffusions might be (e.g. will A win the election or will B?). We have developed a mathematical theory for competitive diffusion, and developed algorithms to identify the result of the competitive diffusions in real world situations with social networks containing 2 million nodes.
For additional information, please contact Dr. V.S. Subrahmanian.
Last updated: June 2010 by John Dickerson
Research and implementation of this project is performed jointly by members of the University of Maryland, the Università di Torino, and the Universita della Calabria.
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 Dr. V.S. Subrahmanian.