Research Article: Structural instability of large-scale functional networks

Date Published: July 20, 2017

Publisher: Public Library of Science

Author(s): Shogo Mizutaka, Kousuke Yakubo, Renaud Lambiotte.


We study how large functional networks can grow stably under possible cascading overload failures and evaluated the maximum stable network size above which even a small-scale failure would cause a fatal breakdown of the network. Employing a model of cascading failures induced by temporally fluctuating loads, the maximum stable size nmax has been calculated as a function of the load reduction parameter r that characterizes how quickly the total load is reduced during the cascade. If we reduce the total load sufficiently fast (r ≥ rc), the network can grow infinitely. Otherwise, nmax is finite and increases with r. For a fixed r(< rc), nmax for a scale-free network is larger than that for an exponential network with the same average degree. We also discuss how one detects and avoids the crisis of a fatal breakdown of the network from the relation between the sizes of the initial network and the largest component after an ordinarily occurring cascading failure.

Partial Text

Numerous complex systems in nature and society can be simplified and abstracted by describing them as networks, in which nodes and edges represent constituent elements and their interactions, respectively. Extensive studies [1–3] have revealed common statistical features of real-world complex networks, such as the small-world property [4], the scale-free property [5], community structures [6], and degree-degree correlations [7]. In order to clarify the origin of these features and/or properties of various dynamics on such networks, so many network models have been proposed so far. In most of previous network models, the number of nodes N, namely the network size, is treated as an a priori given parameter. The network size can then take any value, and, as is often the case, the limit of infinite N is taken in order to simplify the analysis. Thus, these models implicitly assumes that networks are stably present no matter how large networks grow. This assumption is, however, not always valid in real-world systems. In an ecological network representing a closed ecosystem, for example, too many species destabilize the ecosystem and the number of species (nodes in the ecological network) cannot increase unboundedly [8, 9]. Also in a trading network, too many firms make the network fragile because of unstable cartels [10], increase of financial complexity [11, 12], possible large-scale chain-bankruptcy, and other risks [13]. As in these examples, due to intrinsic instability of large-scale networks, some sort of networks have their own limit in sizes only below which they can be stable [14, 15].

First, we calculated nf for the Erdős-Rényi random graph (ERRG) as an initial network G0. In this case, the binomial degree distribution function for G0 is given by
where p = 〈k〉0/N. In this work, we fix the initial average degree as 〈k〉0 = 5.0. Although initial networks having this average degree are not completely connected with isolated nodes at a very low rate, this does not affect our conclusion. Fig 1 shows nf as a function of the initial network size N for various values of the load reduction parameter r. For these results, the node tolerance parameter m and the load carried by a single edge, a, are chosen as m = 4.0 and a = 2.0. The lines in Fig 1 represent nf calculated by Eq (9) and the symbols indicate the results obtained by numerical simulations performing faithfully the cascade process from (i) to (iv) described in the Model section. In the numerical simulation, the overload probability at cascade step τ is calculated under the condition that random walkers cannot jump to other components. Namely, instead of Eq (5), we adopt the overload probability of a node in the α-th component given by
where Mτα is the number of edges in the α-th component of Gτ and Wτα=(Mτα/Mτ)Wτ. The remarkable agreement between the symbols and the lines suggests that our approximation by Eq (5) is quite accurate.

We have studied how large a functional network exposed to cascading overload failures can grow stably and evaluated the maximum stable size nmax above which the network would face the crisis of a fatal breakdown. To this end, we employed the model of cascading overload failures triggered by fluctuating loads [22] which is described by random walkers moving on the network [25]. In this model, how quickly the total load is reduced during the cascade to prevent the fatal breakdown is quantified by the load reduction parameter r. The maximum stable size nmax was calculated by using the generating function technique and solving the master equation for the probability Πτ(k0, k) that a randomly chosen node has the degree k at cascade step τ and the initial degree k0. Our results show that nmax is an increasing function of r and diverges at a certain value rc. This implies that the faster the total load is reduced during the cascade, the larger the network can grow, and we can realize an arbitrarily large network if the total load is sufficiently quickly reduced (r ≥ rc). It has been also clarified that the degree inhomogeneity improves stability of the network. More precisely, for a given r(< rc), nmax for a scale-free network is larger than that for the Erdős-Rényi random graph with the same average degree. Furthermore, from the empirical relation between nmax and the network size Nc giving nmax, we argued how one detects and avoids the crisis of the network breakdown. The present results suggest that a certain relative size of the largest component after cascading failures could be a sign for the impending network collapse. For further stable growth of the network, a more rapid reduction of the total load is required during a cascade of overload failures.   Source:


0 0 vote
Article Rating
Notify of
Inline Feedbacks
View all comments