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.
"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.
http://newsdesk.umd.edu/bigissues/release....
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.
"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.
http://newsdesk.umd.edu/bigissues/release....
Clark, interesting that you have experience with this. The link, by the way came from the ACM. Though I'm not familiar with the detailed concepts, I do feel uneasy that this is being done. We are on social networks for an entirely different reason than what these people are looking for. And to think I might be tagged as some kind of dissident by the government and targeted as part of a group of their own definition is disturbing to me. They speak of allowable information and what is that? Everything we are saying here!!!
And as another aspect of government monitoring, and though I know not many here are fond of Campaign for Liberty and would put them in the teabagger category. they are now under attack by the FEC, as shown in the following brief statement by Ron Paul. I will not go into details as they are about as well received as Harry's rantings. FEC, for the benefit of those like myself who are acronym challenged, is the Federal Election Commission.
Dear Liberty Activist,
The FEC has launched a pair of investigations on Campaign for Liberty.
Both are meritless, but could seriously disrupt our growing program.
Please read Campaign for Liberty President John Tate's letter below and stand with us.
This is exactly the type of government action to quell liberty that I have spent my life opposing.
Sincerely,
Congressman Ron Paul