The network's skeleton
(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 mathematical description 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 hubs", 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 complex networks 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.
More information: Daniel Grady, et al. Robust classification of salient links in complex networks, Nature communications, 29 May 2012; doi:10.1038/ncomms1847
Journal information: Nature Communications
Provided by Max Planck Society