Date:
Maryland Scientists Develop World's Fastest Program to Find Patterns in Social Networks
COLLEGE PARK, Md. - As social networks like Facebook, Flickr, Youtube and Twitter increasingly make it possible to access appropriate information within their networks, a whole host of new applications become possible. For individuals, search engines could better differentiate "friends" and suggest groups with more closely matched interests or concerns. Businesses could search allowed information to offer products or services better matched to customers. And national security and counter-terror analysts, with appropriate court authorization, could look for "groups of people within social networks that match certain characteristics.
However, a technical obstacle to all of these is the difficulty inherent in being able to find all parts of the social network that match a given query network pattern. This essential first step (called the "subgraph matching" step by computer scientists) is often succeeded by many other application-specific steps. The subgraph matching problem is enormously challenging and has long been known to be computationally very difficult, rising exponentially in complexity with the size of the network increases.
University of Maryland grad student Matthias Broecheler working with Computer Science Professor V.S. Subrahmanian and University of Calabria (Italy) Professor Andrea Pugliese have recently unveiled a new mathematically-based computer program, or algorithm, called COSI (short for "Cloud Oriented Subgraph Identification") that will support subgraph pattern matching in very large social networks containing hundreds of millions, even billions, of links.
In a paper that has been accepted for presentation at the 2010 Advances in Social Network Analysis and Mining conference to be held in Denmark in August, Broecheler, Pugliese and Subrahmanian leveraged a key insight - it is possible to split the social network into a set of almost independent, relatively small sub-networks, each of which is stored on a computer in a cloud computing cluster in such a way that the probability that a query pattern will need to access two nodes is kept as small as possible. Using knowledge of past queries and a complex set of calculations to compute these probabilities, their paper reports algorithms and experiments to answer social network subgraph pattern matching queries on real-world social network data with 778 million edges (which may denote relationships or connections between individuals) in less than one second. More recent results not contained in the paper are able to efficiently answer queries to social network databases containing over a billion edges.
Read more.