The network's skeleton

Jun 20, 2012
In large scale networks, only a small number of connections are essential. Consequently, the number of flight paths that are important to all airports is reduced to a relatively manageable number. These form the skeleton of the international flight network (represented in red). The spread of pandemics and the main relationships in ecosystems can be simplified in a similar way. Credit: Research on Complex Systems Group, Northwestern University

(Phys.org) -- Sometimes the distinctive character of a whole resides in just a few of its parts, for example in particular forms and colours of a painting, in the most important ingredients of a dish, or in individual melodies of a symphony. This basic concept is also true of complex networks. Frequently, it takes only a few components to reflect the most important properties of the network. Now, for the first time, an international research team including the Max Planck Institute for Dynamics and Self-Organisation has developed a reliable method for simplifying complex networks in this way. The results will make it much easier to predict the course of global epidemics such as flu, SARS or EHEC, thereby creating conditions for mitigating their spread. This is attributed to the fact that the research team has shown how the new method allows them to reduce the network of all possible disease propagation paths to just the most important routes.

To describe networks like the German road network or international trade relations as "complex" is a charming understatement. Real, large scale complex networks frequently consist of thousands of nodes or hubs that are joined to each other by millions of links. The spreading patterns of modern diseases, across the globe, generated by infected travellers that fly from A to B is also distinctly complex, given the enormous number of international flight connections. As a result, it is virtually impossible to provide an exact or prediction of their behaviour: there are just too many nodes and too many connections.

The scientists working with Dirk Brockmann, who conducts research at Northwestern University in the US and at the Max Planck Institute for Dynamics and Self-Organisation in Göttingen, have now developed a method for reducing every network to a type of skeleton network. Under its funding initiative "New conceptual approaches for the modelling and simulation of complex systems", the Volkswagen Foundation is supporting Brockmann's research to the tune of about €500,000. The skeleton network, which is significantly smaller than the original, reproduces all the important properties of the whole. It contains, so to speak, the essence of the network. But which parts of the network are essential? Which nodes and which links can be left out without having a significant impact on the fundamental behaviour of the network?

Only a small number of links are significant

"Let's take the example of the German road network. At first glance, it seems quite legitimate to hide the nodes that represent tiny villages and connecting lines that denote country lanes", begins Brockmann. This is not likely to have a major impact on the behaviour of the whole network. "But where do you draw the line?" the scientist muses, pinpointing the issue. How many inhabitants must a city have, or how much traffic must use a road for it to be considered an important hub or connector, so that it is not left out of the skeleton? How should the threshold be determined? This question has no satisfactory answer, as past years have shown that a suitable threshold must be established separately for every network.

"Our new method, in contrast, applies across the board – and it thrives on different perspectives", explains Daniel Grady of Northwestern University. The scientists put themselves into each node in the network and determine which links they consider especially important. From the perspective of the city of Göttingen, for example, the Hamburg-Berlin highway is more important than the Dresden-Berlin one; country roads in North Rhine-Westphalia don't come into play at all. A different picture emerges in each case for the cities of Berlin, Dresden, Cologne and Munich. "Only a small number of connecting lines are significant for all ", explains Grady. Together, these main traffic arteries form the backbone of the network, its skeleton. This skeleton network displays all the main properties of the original network, but is much smaller.

"It is particularly striking just how small the skeleton network is", says Brockmann. In the case of the network of all international flight connections, the skeleton consists of just 6.76 per cent of the original network. A mere 2.39 per cent of connecting lines is sufficient to describe the main aspects of world trade relations, according to the team's calculations.

The skeleton network reveals which species are especially important for ecosystems

The skeleton network principle will make it much easier in future to describe the propagation routes of pandemics in mathematical terms. The scientists played through a number of different propagation scenarios on the computer, and noticed that the flight connections that frequently play an important role in infection are all contained in the skeleton network. "This means that in future we can run our calculations with the skeleton network alone", affirms Brockmann, "enabling us to predict the course of a pandemic much faster than before." This will also make it possible to do a better job of fighting the spread of disease.

A further application of skeleton networks is the description of complex ecosystems. Every species that occurs in a given ecosystem is represented by a node and every relationship of eating and being eaten, by a link. The links that form the skeleton network of such an ecosystem make an important contribution to the stability of the system, argue the scientists, thereby revealing which species should not be harmed if at all possible - for example, through the use of pesticides.

However, the scientists are not only concerned with making it easier to grasp in mathematical terms. "Skeleton networks also express something about the universal principles governing network structure", explains Brockmann, as it turns out that very different networks display very similar skeleton architecture. It seems that it hardly matters whether the original network consists of nodes with only a few close neighbors or is closely woven over long distances. "This discovery may help us understand how such very different networks form and develop", says Brockmann.

Explore further: Taking great ideas from the lab to the fab

More information: Daniel Grady, et al. Robust classification of salient links in complex networks, Nature communications, 29 May 2012; doi:10.1038/ncomms1847

Related Stories

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 ...

How quickly things spread

Feb 21, 2012

Understanding the spread of infectious diseases in populations is the key to controlling them. If we were facing a flu pandemic, how could we measure where the greatest spreading risk comes from? This information ...

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

Berkeley team explores sound for indoor localization

1 hour ago

The global positioning system, or GPS, has its limitations—namely, it cannot work indoors. Potential solutions for indoor positioning continue to fire up the imaginations of scientists. The latest news ...

Taking great ideas from the lab to the fab

13 hours ago

A "valley of death" is well-known to entrepreneurs—the lull between government funding for research and industry support for prototypes and products. To confront this problem, in 2013 the National Science ...

User comments : 0