How can we make sense of the behaviour of complicated structures with many interacting parts? The recent paper Structural reducibility of multilayer networks, by Manlio De Domenico, Vincenzo Nicosia, Alex Arenas, and Vito Latora lies in the discipline of complex systems, dedicated to answering questions such as this. Intriguingly, a key tool in this paper comes from an entirely different branch of mathematics, demonstrating the power of an inter-disciplinary approach.
In a complex system, there are many entities that interact with each other in lots of different ways. Some examples are social networks, the economy, the transport system, and biological systems such as the ensemble of enzymes in a cell. Modelling these systems effectively is a fundamental prerequisite for dealing with them in the real world.
Figure 1: Two layers of the transport system of North America. In blue, links in the road network; in salmon, airline routes.
If you're trying to understand a complex system, it helps to minimise the number of parts in your description. This can reveal new structural patterns in the system that weren't obvious at first. For example, cocoa and coffee grow in the same parts of the world, and similar countries import both of them too, so it makes sense to lump them together if you want the big picture of world food trade.
In an elaborate system, how do you go about picking out which aspects to lump together? Suppose each kind of interaction—each “layer” of the system—can be represented as a graph, with vertices for the participants and edges for their relationships. Then the question is: when are two graphs similar enough to be consolidated? Inspiration comes, surprisingly, from quantum physics.
Figure 2: A schematic of the layers and graphs in a complex system. (Credit: Gómez-Gardeñes et al, Scientific Reports, 2010.)
You've probably heard of the thought experiment of Schrödinger's cat. This is a cat in a box which is somehow “both alive and dead, simultaneously” until you open the box and look at it: then it will either be alive or dead (and stay that way). This illustrates two significant quantum phenomena, superposition and its collapse under observation. A superposition is the kind of state the cat is in before opening the box; it's not merely a statistical average of alive and dead but a so-called pure state distinct from either. If you collapsed the state but didn't look then the cat would change from this pure state into a mixed state, which is a simple probabilistic combination of alive and dead.
In quantum mechanics, the sort of randomness in mixed states is described by certain matrices of complex numbers, known as density matrices. There is a function called the Von Neumann entropy which tells you just how mixed a density matrix is: for pure states the entropy is zero, while it increases for more extreme mixtures. If two mixed states are averaged into one, the Von Neumann entropy increases if they are different to each other and decreases if they are similar.
The authors apply this idea to complex systems by treating the graphs of layers as density matrices. They give the following efficient algorithm for producing a simple description of a complex system. Find two layers so that combining them would reduce the Von Neumann entropy as much as possible; then combine them, and repeat. When there is no pair of layers left that would reduce the entropy, stop.
The paper's conclusion is that even this simple algorithm is powerful enough to uncover a big qualitative difference between two types of complex system. In some systems, different layers frequently reinforce each other; in other systems, different layers tend to stay dissimilar to each other and find their own structural niches. For example, social networks are of the first kind: you're likelier to make friends with someone if you already have another social connection with them, like going to the same school, so those layers are similar. Transport networks, on the other hand, are of the second kind, consolidating very little: having two different train lines that link very similar sets of destinations would be pointless.
An algorithm which can classify even very large systems this way will surely be a valuable tool in understanding the various huge complex systems in the world around us.
Structural reducibility of multilayer networks appeared on 23rd April 2015 in Nature. Nicosia and Latora are Queen Mary University of London staff.
Did you read this article? Could you help us provide you with tailored content? Tell us what you think.