Researchers develop method that shows diverse complex networks have similar skeletons

Jun 01, 2012
The worldwide air transportation network. Each grey link resembles traffic of passengers between more than 1,000 airports worldwide; the entire network has more than 35,000 links. The red lines represent the network’s skeleton, a tree-like structure of only 1,300 links that represents the core structure of the network. Links in the skeleton are the most important connections in the network.

Northwestern University researchers are the first to discover that very different complex networks -- ranging from global air traffic to neural networks -- share very similar backbones. By stripping each network down to its essential nodes and links, they found each network possesses a skeleton and these skeletons share common features, much like vertebrates do.

Mammals have evolved to look very different despite a common underlying structure (think of a human being and a bat), and now it appears real-world evolve in a similar way.

The researchers studied a variety of biological, technological and social networks and found that all these networks have evolved according to basic . The findings could be particularly useful in understanding how something -- a disease, a rumor or information -- spreads across a network.

This surprising discovery -- that networks all have skeletons and that they are similar -- was published this week by the Communications.

" such as H1N1 and SARS spread in a similar way, and it turns out the network's skeleton played an important role in shaping the global spread," said Dirk Brockmann, senior author of the paper. "Now, with this new understanding and by looking at the skeleton, we should be able to use this knowledge in the future to predict how a new outbreak might spread."

Brockmann is associate professor of engineering sciences and applied mathematics at the McCormick School of Engineering and Applied Science and a member of the Northwestern Institute on (NICO).

Complex systems -- such as the Internet, Facebook, the , human consciousness, even a termite colony -- generate complex behavior. A system's structure emerges locally; it is not designed or planned. Components of a network work together, interacting and influencing each other, driving the network's evolution.

For years, researchers have been trying to determine if different networks from different disciplines have hidden core structures -- backbones -- and, if so, what they look like. Extracting meaningful structural features from data is one of the most challenging tasks in network theory.

Brockmann and two of his graduate students, Christian Thiemann and first author Daniel Grady, developed a method to identify a network's hidden core structure and showed that the skeletons possess some underlying and universal features.

The networks they studied differed in size (from hundreds of nodes to thousands) and in connectivity (some were sparsely connected, others dense) but a simple and similar core skeleton was found in each one.

"The key to our approach was asking what network elements are important from each node's perspective," Brockmann said. "What links are most important to each node, and what is the consensus among nodes? Interestingly, we found that an unexpected degree of consensus exists among all nodes in a network. Nodes either agree that a link is important or they agree that it isn't. There is nearly no disagreement."

By computing this consensus -- the overall strength, or importance, of each link in the network -- the researchers were able to produce a for each network consisting of all those links that every node considers important. And these skeletons are similar across networks.

Because of this "consensus" property, the researchers' method does not have the drawbacks of other methods, which have degrees of arbitrariness in them and depend on parameters. The Northwestern approach is very robust and identifies essential hubs and links in a non-arbitrary universal way.

Explore further: Researchers developing algorithms to detect fake reviews

More information: The paper, titled "Robust Classification of Salient Links in Complex Networks," is available at www.nature.com/ncomms/journal/… full/ncomms1847.html .

Related Stories

Unraveling biological networks

Mar 05, 2012

A new approach to disentangling the complexities of biological networks, such as the way in which proteins interact in our body's cells has been developed by researchers in China. The team's algorithm could allow biologists ...

Game of go: A complex network

Apr 16, 2012

Could computers ever beat the best go players? Although unthinkable at this stage, this could soon become possible, thanks to CNRS theorists. For the first time, two scientists from the Theoretical Physics ...

Quantum Communication in Random Networks

May 26, 2010

Internet, networks of connections between Hollywood actors, etc, are examples of complex networks, whose properties have been intensively studied in recent times. The small-world property (that everyone has ...

Networks in motion

Apr 19, 2012

A new article by a Northwestern University complex networks expert discusses how networks governing processes in nature and society are becoming increasingly amenable to modeling, forecast and control.

What's the semantic organization of human language?

Aug 11, 2009

A Chinese semantic network with semantic (argument structure) annotation was built and investigated for finding its global statistical properties. The results show that semantic network is also small-world and scale-free ...

Recommended for you

Apple sees iCloud attacks; China hack reported

6 hours ago

Apple said Tuesday its iCloud server has been the target of "intermittent" attacks, hours after a security blog said Chinese authorities had been trying to hack into the system.

HP supercomputer at NREL garners top honor

8 hours ago

A supercomputer created by Hewlett-Packard (HP) and the Energy Department's National Renewable Energy Laboratory (NREL) that uses warm water to cool its servers, and then re-uses that water to heat its building, has been ...

User comments : 4

Adjust slider to filter visible comments by rank

Display comments: newest first

alfie_null
not rated yet Jun 02, 2012
So, if we can identify that "skeleton", we might be able to influence or disrupt the network?
To some degree, do all networks sustain some way of repairing damage? As did the Internet, as envisioned by DARPA (rich choice of alternate routes, it's devolved a bit since).
Eikka
not rated yet Jun 02, 2012
As did the Internet, as envisioned by DARPA (rich choice of alternate routes, it's devolved a bit since).


The internet doesn't really deal well with alternate routes. The choice for the way the internet routing works isn't inherently fault tolerant, because the original administrators kinda chose the worst routing system they had available. It was really designed for a relatively small network where everyone knows the whole structure to be able to route around faults, and can call someone to make sure there's no conflicts.

For example, if you want to have two routes to your server for redundancy, you get two IP adresses, which look like two separate machines to the network. Your client then has to know that these two adresses are the same to reach you via both. That's because the IP adress is not really an adress but an interface number.

A proper adress would be like "Big city, district four, street eight, house seven", and the network/client could pick a route.

gwrede
not rated yet Jun 02, 2012
Eikka, you might want to study Internet Routing to get a clearer picture.
Eikka
not rated yet Jun 02, 2012
Eikka, you might want to study http://en.wikiped...#Routing to get a clearer picture.


Clearer in regards to what?

The internet's physical structure resembles a scale free network, but the routing that happens within the network wasn't originally designed to be so. See: http://en.wikiped..._Routing

The original problem was that a network adress block was either very tiny, or very large, so you got lots of tiny networks that all needed a route. The number of entries in the global routing table grows faster than linearily as the number of routes increases, so at some point routers will simply run out of memory and processing power.

The solution reduces the number of routes in the routing table to a more manageable level by splitting the IP adress space more appropriate subnets, but doesn't remove the fundamental problem as the internet grows in size, and doesn't remove the need for a central authority to manage the whole thing.