Prev
New method tackles social networks, biological systems, air transportation and more
By Megan Fellman, Dec 7, 2009, Northwestern U.
EVANSTON, Ill. --- Facebook figures out that you know Holly, although you haven't seen her in 10 years, because you have four mutual friends -- a good predictor of direct friendship. But sometimes Facebook gets it wrong. "Hey, I don't know Harry!"
Roger Guimera and Marta Sales-Pardo, a husband-wife research team at Northwestern University, have developed a universal method that can accurately analyze a range of complex networks -- including social networks, protein-protein interactions and air transportation networks. Although the datasets they used were much smaller than Facebook's, the researchers demonstrated the great potential of their method.
A new universal method of network analysis can predict friendships in a social network and protein-protein interactions within a cell. The method also can separate spurious interactions from correct ones.
Guimera and Sales-Pardo had wondered if one technique, exploiting the fact that all networks have groups in them and those groups are connected in many different ways, could be used to predict both friendships in a social network and protein-protein interactions within a cell. They applied their mathematical and computational framework to five different networks, ranging from a group of dolphins to a network of neurons, and found one method indeed could reliably analyze all.
The central idea behind Guimera and Sales-Pardo's method is that,
even though each network has unique characteristics (depending on its functional needs and evolutionary history), all networks share a remarkable property: their nodes can be classified into groups with the nodes connecting to each other depending on their group membership.
In a social network, for example, people can be grouped by age, occupation, political orientation and so on. The method proceeds by averaging all possible groupings of the nodes, giving each grouping a weight that reflects its explanatory power.
The details of their algorithm are in the paper
Missing and spurious interactions and the reconstruction of complex networks,
Guimera, R, Sales-Pardo, M., PNAS (2009)
Read full story.