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 complex networks 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 growth mechanisms. 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 last week by the journal Nature Communications.

   

“Infectious
diseases 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 Complex Systems (NICO).

   

Complex
systems—such as the Internet, Facebook, the power grid, 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 skeleton 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.

   

Robust Classification of Salient Links in Complex Networks

Source: Northwestern University