Critical phenomena in complex networks
February 10, 2011 3 Comments
Critical phenomena in complex networks at arXiv is a 2007 review of activity mediated by complex networks, including the co-evolution of activity and networks.
The combination of the compactness of networks, featuring small diameters, and their complex architectures results in a variety of critical effects dramatically different from those in cooperative systems on lattices. In the last few years, important steps have been made toward understanding the qualitatively new critical phenomena in complex networks. The results, concepts, and methods of this rapidly developing field are reviewed. Two closely related classes of these critical phenomena are considered, namely, structural phase transitions in the network architectures and transitions in cooperative models on networks as substrates. Systems where a network and interacting agents on it influence each other are also discussed. [i.e. co-evolution] A wide range of critical phenomena in equilibrium and growing networks including the birth of the giant connected component, percolation, k-core percolation, phenomena near epidemic thresholds, condensation transitions, critical phenomena in spin models placed on networks, synchronization, and self-organized criticality effects in interacting systems on networks are mentioned. Strong finite-size effects in these systems and open problems and perspectives are also discussed.
The summary notes:
Real-life networks are finite, loopy (clustered) and correlated. Most of them are out of equilibrium. A solid theory of correlation phenomena in complex networks must take into account finite-size effects, loops, degree correlations, and other structural peculiarities. We described two successful analytical approaches to cooperative phenomena in infinite networks. The first was based on the tree ansatz, and the second was the generalization of the Landau theory of phase transitions. What is beyond these approaches?
Thus we can distinguish between:
- very complex: where the existing analytic approaches do not work.
- moderately complex: where the analytic approaches do work pragmatically, at least in the short-term, even though their assumptions aren’t strictly true.
- not very complex: where analytic approaches work in theory and practice. Complicated?
This blog is focussed on the very complex. The paper notes that in these cases:
- evolution is more than just a continuous change in a parameter of some over-arching model.
- fluctuations are typically scale-free (and in particular non-Guassian, taking one outside the realm assumed by elementary statistics).
- the scale-free exponent is small.
The latter implies that:
- many familiar statistics are undefined.
- the influence of network heterogeneity is ‘dramatic’.
- mean-field notions, essential to classical Physics, are not valid.
- notions such as ‘prior probability’ and ‘information’ are poorly defined, or perhaps none-sense.
- synchronization across the network is robust but not optimisable.
- one gets an infinite series of nested k-cores. (Thus while one lacks classical structure, there is something there which is analogous to the ‘structure’ of water: hard to comprehend.)
Such complex activity is inherently robust and (according to Cybernetic theory) cannot be controlled. The other regions are not robust and can be controlled (and hence subverted). From an evolutionary perspective, then, if this theory is an adequate representation of real systems, we should expect that in the long term real networks will tend to end up as very complex rather than as one of the lesser complexities. It also suggests that we should try to learn to live with the complexity rather than ‘tame’ it. Attempts to over-organize would seem doomed.
Verifying the theory
(Opinion.) In so far as the theory leads to the conclusion that we need to understand and learn to live with full complexity, it seems to me that it only needs to be interpreted into domains such as epidemics, confrontation and conflict, economics and developement to be recognized as having a truth. But in so far as our experience is limited by the narrow range of approaches that we have tried to such problems, we must beware of the usual paradox: acting on the theory would violate the logical grounds for believing in it. More practically, we may note that the old approaches, in essence, assumed that the future would be like the past. Our new insights would allow us to transcend our current epoch and step into the next. But it may not be enough to take one such step at a time: we may need a more sustainable strategy. (Keynes, Whitehead, Smuts, Turing, …)
An appreciation of the truly complex might usefully inform strategies and collaborations of all kinds.
I will separate out some of this into more appropriate places.