January 10, 2011 –
Diagram depicts a web site network (image:M. Newman).
In a novel cross-disciplinary endeavor, a social scientist, an electrical engineer and a computer scientist with a bent for biology have entered into a collaboration that could open the door to novel advances in network analysis.
Project PI Athina Markopoulou and co-PIs Carter Butts and Natasa Przulj won a four-year, $2 million grant from the National Science Foundation’s Cyber-enabled Discovery and Innovation program to develop methods and software tools for analyzing network topology across diverse disciplines.
Social networks, computer networks and biological networks – the purview of the three researchers – would appear to have little in common, but they share certain features that allow them to be modeled and analyzed in similar ways, says Markopoulou, UC Irvine assistant professor of electrical engineering and computer science.
The basics
All networks of every type can be represented as mathematical objects called graphs, consisting of “nodes” and “edges.”
A node in any network is an individual unit. In a social network it might be a person; in a computer network it could be a PC; in a biological network it is often a protein. An edge connects those nodes – for example, a friendship or other relationship connects people in a social network, a physical cable or the Internet may connect PCs in a computer network, and a reaction of some kind bonds proteins in a biological network.
Researchers in all three fields who want to model these diverse networks use graphs, and in each case, they examine attributes (the nature of the nodes) and topology (the ways in which the nodes are connected).
Network of organizations responding to Hurricane Katrina disaster, as collected by Butts and colleagues. Each node represents a responding organization, and each tie represents a collaborative relationship. (image: V.Krebs)
Network of tuberculosis contagion (image: V.Krebs)
Markopoulou is working with Butts, a UCI sociology associate professor, and Przulj, a computer scientist currently at Imperial College London, to develop universal methods for analyzing graphs and properties in all types of networks. The three believe these tools can result in a ubiquitous approach that can solve problems in any sort of network.
Cross-disciplinary approaches to network analysis previously have been hindered by the many differences in disparate networks but these researchers are concentrating instead on the similarities.
“We all come from different places,” says Markopoulou, “but in all three contexts, when you try to model these networks, you use graphs, and you care about the topology of the graph and the properties of the nodes and edges. We deal with completely different application contexts but with similar underlying mathematical problems.”
Double the Impact
It’s common knowledge among researchers that individual units and the properties of those units are important. Just as significant, however, are the relationships among the units. “Which entities are related to which other entities, and in what way can be very important information – in some cases, more important than the individual units themselves and their properties,” Butts says.
He cites computer networks by way of explanation. “You can have the world’s fastest computer but if it’s locked behind a slow-bandwidth connection, you won’t be able to utilize its processing power.”
In a similar way, social networks also are affected by structure – who is connected to whom and how they are connected is key to understanding disease propagation, information dissemination and group behavior, for example. The same principles apply to biological networks.
But researchers have learned that unlocking a network’s secrets involves more than simply comprehending the behavior of these two aspects. “Understanding the sum of those two things – the properties of an individual unit and how they’re connected – is greater than what you’d learn from each one separately,” Butts states.
The core of the project, he continues, is developing new tools and methods to better analyze the synergy created when those two network properties act in tandem.
Endless Possibilities
The team is using simulations and real data sets from different disciplines to develop general formulations of network structures, and is developing computational algorithms to sample and extract network properties from that data.
By examining the properties and relationships they see in their sampled data, researchers can identify patterns and the mechanisms that create them. Are the patterns created by chance or in some other way? If it’s not chance, what other mechanism might be responsible?
“These networks have very different characteristics but by thinking in a mathematical, computational way we can recognize problems… that might look on the surface very different but have a common underlying structure,” Butts says. “It’s taking core ideas and insights and computational methods that are discovered in one arena and figuring out how we can use those to expand our knowledge in another.”
These insights take on more importance as networks continue to evolve and become more ingrained in our daily lives. “The Internet invented in the late ‘60s-early ‘70s was first used for exchanging data. Then it was used for voice and multimedia and most recently for online social interaction, even computation on the cloud,” says Markopoulou. “So research about computer networks is increasingly important compared to some time ago.”
Possible applications include improving network security, identifying the signature of diseases and drug reactions, and better understanding online social environments.
“My predication is that when we really start to get a handle on how form and function fit together it’s going to open new windows,” says Butts. “We’re going to have new questions to ask and new ways to look at things.”
— Anna Lynn Spitzer
