Good Connections Are Everything

July 12th, 2005

Max Planck Scientists discover unusual dynamic properties of activity patterns on scale-free networks

The biosphere contains many scale-free networks. Prominent examples are provided by the functional networks within the human brain. Scientists at the Max Planck Institute of Colloids and Interfaces have discovered that activity patterns in such biomimetic networks have unusual dynamic properties, which are controlled by a few, highly connected nodes.

Image: Three subsequent snapshots of the activity pattern on a rather small scale-free network with 31 nodes and 50 connections. The active and inactive nodes are white and black, respectively. For the initial pattern on the left, about half of the nodes are inactive (black); for the final pattern on the right, almost all nodes are active (white). Each node of the network has a certain degree which is equal to the number of connections attached to it; this number is explicitly given for some nodes on the left. The node with the largest degree is located in the middle of the network and has 21 connections. Image: Max Planck Institute of Colloids and Interfaces

As a result, ordered activity patterns are very robust against random perturbations but rather sensitive to selective perturbations. Disordered patterns, on the other hand, decay very fast and relax towards an ordered pattern even if the network becomes infinitely large. In addition, these scale-free networks can also be used to store and retrieve a large number of fixed patterns (PNAS, Advanced Online Publication, 8 July 2005).

The human brain consists of about 100 billion nerve cells or neurons that are interconnected to form a huge network. Each neuron can be active by producing an action potential. If we were able to make a snapshot of the whole neural network, we would see, at any moment in time, a certain pattern of active and inactive neurons. If we combined many such snapshots into a movie, we would find that this activity pattern changes continuously with time, (see Image). This pattern evolution represents the global dynamics of the neural network. At present, one cannot observe such activity patterns on the level of single neurons, but modern imaging techniques enable us to monitor coarse-grained patterns with a reduced spatial resolution. Using functional magnetic resonance imaging, for example, scientists can obtain activity patterns of about 100,000 neuron clusters, each of which contains about one million neurons.

The neuron clusters form another, coarse-grained network. Each cluster corresponds to a node of this network, and each node can be characterized by its degree, i.e., by the number of connections to other nodes, see Image. This degree varies from node to node. We may then count the number of nodes within the network that have a certain degree. In this way, we obtain a histogram or distribution for the degree of the nodes; this distribution determines the probability P(k) that a randomly selected node has k connections attached it. It has been recently found from magnetic resonance imaging that the functional networks of neuron clusters in the human brain are characterized by a degree distribution P(k) that is scale-free.

In order to understand the meaning of the term ‚scale-free’, let us consider the probabilities P(10), P(100), P(1000), and P(10000) to find a node with 10, 100, 1000, and 10000 connections, respectively. A scale-free network has the property that the probability ratio P(100)/P(10) is equal to the ratio P(1000)/P(100) which is equal to the ratio P(10000)/P(1000) etc. The logarithm of this constant ratio defines the decay exponent 'gamma'. For the functional networks of the human brain, the decay exponent was found to be approximately equal to 2.1.

Scientists at the Max Planck Institute of Colloids and Interfaces have now discovered that activity patterns on such scale-free networks exhibit unusual dynamic properties as described in the recent PNAS study. First, if one starts from an ordered network pattern, one finds that this ordered pattern is very robust with respect to perturbations of randomly chosen nodes but rather sensitive with respect to selective perturbations of the highly connected nodes. In fact, the relative fraction of highly connected nodes that one has to perturb in order to transform one ordered pattern into another one goes to zero as the decay exponent approaches the value of 2. Second, if one starts with a disordered pattern, this initial pattern transforms into an ordered one on a very short time scale, a property which applies even to an infinite network. In both cases, the tiny fraction of highly connected nodes is sufficient to spread the relevant information over the whole network.

Such networks may also be used in order to store and retrieve a certain number of fixed patterns. The new PNAS study shows that scale-free networks with a decay exponent which is larger than 2 but smaller than 2.5, can store a huge number of patterns which increases continuously with the size of the network. As the decay exponent approaches the value of 2, the storage capacity of the network becomes proportional to the network size. In contrast, if the decay exponent exceeds the value of 2.5, the number of stored patterns remains small even for an infinite network. Thus, scale-free biomimetic networks where the decay exponent is larger than 2 but smaller than 2.5 could provide possible designs for associative memories and pattern recognition.

The dynamic properties just described are not restricted to neural networks. Indeed, the biosphere contains a whole hierarchy of scale-free networks which typically exhibit a decay exponent in the range larger than 2 but smaller than 2.5. Additional examples are provided by the metabolic networks within biological cells which have been studied for 43 different organisms representing all three kingdoms of life. On a much larger scale, social networks, which are based on different social activities such as the collaboration of movie actors, the co-authorship of scientists, or frequent phone conversations, have the same property. Finally, the same scale-free structure is also found for networks of internet routers and for the networks of links on the world wide web. All of these networks have the property that their activity patterns are primarily controlled by the tiny fraction of highly connected nodes.

Original work:

Haijun Zhou and Reinhard Lipowsky
Dynamic pattern evolution on scale-free networks
PNAS, Advanced Online Publication, 8 July 2005

Source: Max Planck Institute