SELF-ORGANIZED CRITICALITY

The emergence of algebraic scaling in the size distribution of network collapse is interesting from the viewpoint of SOC that occurs in many real-world complex systems. For a dynamical system subject to continuous external perturbations, during its evolution towards SOC, it can appear stable for a long period of time before a catastrophic event occurs and the probability for the catastrophe can be markedly larger than intuitively expected (algebraic versus exponential scaling)69,70.

In our case, there is a long time period of synchronization stability in spite of the small-size collapses, but catastrophic collapses that remove all or most of the nodes in the network can occur, albeit rarely. There are a variety of models for SOC, but the unique feature of our model is that it exploits network synchronization stability as a mechanism for catastrophic failures. Since synchronization is ubiquitous in natural and man-made complex systems, the finding of SOC in synchronization-stability-constrained network may have broad implications. For instance, synchronization is commonly regarded as the dynamical basis for normal functioning of the power grids71 and there is empirical evidence that the size of the blackouts follows roughly an algebraic distribution72.

Growth, or expansion, is a fundamental feature of complex networks in nature, society and technological systems. Growth, however, is often subject to constraints. Traditional models of complex networks contain certain growth mechanism, such as one based on the preferential attachment rule3, but impose no constraint. Apparently, when growth is constrained, typically the network cannot expand indefinitely, nor can its size be a monotonous function of time. As a result, during the growth process there must be times when the network size is reduced (collapse). But are there generic features of the collapse events? For example, statistically what is the distribution of the collapse size and are there universal characteristics in the distribution?

This paper addresses these intriguing questions using synchronization as a concrete type of constraint. In particular, taking into account the effects of desynchronization tolerance and synchronization speed, we propose and investigate growing complex networks subject to the constraint of synchronization stability. We find that, as new nodes are continuously added into the network, it can self-organize itself into a critical state where the addition of a single node can trigger a large scale collapse. Statistical analysis of the characteristics of the collapse events such as the degree distribution of the collapsed nodes, the collapse frequency and the collapse size distribution, indicates that constraint induced network collapse can be viewed as an evolutionary process towards self-organized criticality. The SOC feature is especially pronounced as the collapse size follows an algebraic scaling law. We develop an eigenvector analysis to understand the origin of the network collapse phenomenon and the associated scaling behaviors.

In a modern society, cities and infrastructures continue to expand. In social media, various groups (social networks) keep growing. When constraints are imposed, e.g., manifested as governmental policies or online security rules, how would the underlying network respond? Can constraints lead to large scale, catastrophic collapse of the entire network? These are difficult but highly pertinent questions. Our findings provide some hints about the dynamical features of the network collapse phenomenon, but much further efforts are needed in this direction of complex systems research.