Scientists Develop World's Fastest Program to Find Patterns in Social Networks

Jun 29, 2010
Scientists Develop World's Fastest Program to Find Patterns in Social Networks

(PhysOrg.com) -- 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 ) 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 , or , called COSI (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 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.

"These new algorithms for subgraph matching make it practical for the first time to implement many desirable functionalities previously only practical for small networks," said Anil Nerode, who is Goldwin-Smith professor of mathematics and computer science and former director of the Mathematical Sciences Institute at Cornell University. "We can expect a profound influence of these algorithms on extending the capabilities of social networks," said Nerode, who is not involved in the work.

Professor Subrahmanian, one of the inventors, said: "An innovative mix of cloud computing and smart thinking, COSI shows how exact social network pattern matching on complex query patterns can be efficiently implemented. It is a significant advance, not only in answering complex queries over large social networks, but also for answering queries over the Semantic Web. This advance could have a significant impact for individual users of social networks as well as for the national security and business communities and is yet another innovative mix of cloud computing and smart thinking.

"The next challenge for COSI will be to perform matching of similar, but not exact, patterns," he said.

Explore further: Google's Street View address reading software also able to decipher CAPTCHAs

Related Stories

Using networks to map the social lives of animals

Sep 02, 2008

Dr Dick James from the University's Department of Physics has released a practical guide for biologists explaining how social network analysis, a method used widely in the social sciences to study interactions among people, ...

Recommended for you

Ant colonies help evacuees in disaster zones

Apr 16, 2014

An escape route mapping system based on the behavior of ant colonies could give evacuees a better chance of reaching safe harbor after a natural disaster or terrorist attack by building a map of showing the shortest routes ...

User comments : 0

More news stories

Hackathon team's GoogolPlex gives Siri extra powers

(Phys.org) —Four freshmen at the University of Pennsylvania have taken Apple's personal assistant Siri to behave as a graduate-level executive assistant which, when asked, is capable of adjusting the temperature ...

Better thermal-imaging lens from waste sulfur

Sulfur left over from refining fossil fuels can be transformed into cheap, lightweight, plastic lenses for infrared devices, including night-vision goggles, a University of Arizona-led international team ...

Chronic inflammation linked to 'high-grade' prostate cancer

Men who show signs of chronic inflammation in non-cancerous prostate tissue may have nearly twice the risk of actually having prostate cancer than those with no inflammation, according to results of a new study led by researchers ...