Geographical effects on cascading breakdowns of scale-free networks

Emergence of Scale-Free Blackout Sizes in Power Grids

We model power grids as graphs with heavy-tailed sinks, which represent demand from cities, and study cascading failures on such graphs. Our analysis links the scale-free nature of blackout sizes to the scale-free nature of city sizes, contrasting previous studies suggesting that this nature is governed by self-organized criticality. Our results are based on a new mathematical framework combining the physics of power flow with rare event analysis for heavy-tailed distributions, and are validated using various synthetic networks and the German transmission grid.

Asymmetry in interdependence makes a multilayer system more robust against cascading failures

Multilayer networked systems are ubiquitous in nature and engineering, and the robustness of these systems against failures is of great interest. A main line of theoretical pursuit has been percolation-induced cascading failures, where interdependence between network layers is conveniently and tacitly assumed to be symmetric. In the real world, interdependent interactions are generally asymmetric. To uncover and quantify the impact of asymmetry in interdependence on network robustness, we focus on percolation dynamics in double-layer systems and implement the following failure mechanism: Once a node in a network layer fails, the damage it can cause depends not only on its position in the layer but also on the position of its counterpart neighbor in the other layer. We find that the characteristics of the percolation transition depend on the degree of asymmetry, where the striking phenomenon of a switch in the nature of the phase transition from first to second order arises. We derive a theory to calculate the percolation transition points in both network layers, as well as the transition switching point, with strong numerical support from synthetic and empirical networks. Not only does our work shed light on the factors that determine the robustness of multilayer networks against cascading failures, but it also provides a scenario by which the system can be designed or controlled to reach a desirable level of resilience.

General methodology for inferring failure-spreading dynamics in networks

A generic modeling framework to infer the failure-spreading process based on failure times of individual nodes is proposed and tested in four simulation studies: one for cascading failures in interdependent power and transportation networks, one for influenza epidemics, one benchmark test case for congestion cascade in a transportation network, and one benchmark test case for cascading power outages. Four general failure-spreading mechanisms-external, temporal, spatial, and functional-are quantified to capture what drives the spreading of failures. With the failure time of each node given, the proposed methodology demonstrates remarkable capability of inferring the underlying general failure-spreading mechanisms and accurately reconstructing the failure-spreading process in all four simulation studies. The analysis of the two benchmark test cases also reveals the robustness of the proposed methodology: It is shown that a failure-spreading process embedded by specific failure-spreading mechanisms such as flow redistribution can be captured with low uncertainty by our model. The proposed methodology thereby presents a promising channel for providing a generally applicable framework for modeling, understanding, and controlling failure spreading in a variety of systems.

Growth, collapse, and self-organized criticality in complex networks

Network growth is ubiquitous in nature (e.g., biological networks) and technological systems (e.g., modern infrastructures). To understand how certain dynamical behaviors can or cannot persist as the underlying network grows is a problem of increasing importance in complex dynamical systems as well as sustainability science and engineering. We address the question of whether a complex network of nonlinear oscillators can maintain its synchronization stability as it expands. We find that a large scale avalanche over the entire network can be triggered in the sense that the individual nodal dynamics diverges from the synchronous state in a cascading manner within a relatively short time period. In particular, after an initial stage of linear growth, the network typically evolves into a critical state where the addition of a single new node can cause a group of nodes to lose synchronization, leading to synchronization collapse for the entire network. A statistical analysis reveals that the collapse size is approximately algebraically distributed, indicating the emergence of self-organized criticality. We demonstrate the generality of the phenomenon of synchronization collapse using a variety of complex network models, and uncover the underlying dynamical mechanism through an eigenvector analysis.

Epidemic variability in hierarchical geographical networks with human activity patterns

Recently, some studies have revealed that non-Poissonian statistics of human behaviors stem from the hierarchical geographical network structure. On this view, we focus on epidemic spreading in the hierarchical geographical networks and study how two distinct contact patterns (i.e., homogeneous time delay (HOTD) and heterogeneous time delay (HETD) associated with geographical distance) influence the spreading speed and the variability of outbreaks. We find that, compared with HOTD and null model, correlations between time delay and network hierarchy in HETD remarkably slow down epidemic spreading and result in an upward cascading multi-modal phenomenon. Proportionately, the variability of outbreaks in HETD has the lower value, but several comparable peaks for a long time, which makes the long-term prediction of epidemic spreading hard. When a seed (i.e., the initial infected node) is from the high layers of networks, epidemic spreading is remarkably promoted. Interestingly, distinct trends of variabilities in two contact patterns emerge: high-layer seeds in HOTD result in the lower variabilities, the case of HETD is opposite. More importantly, the variabilities of high-layer seeds in HETD are much greater than that in HOTD, which implies the unpredictability of epidemic spreading in hierarchical geographical networks.

Cascading dynamics on random networks: crossover in phase transition

In a complex network, random initial attacks or failures can trigger subsequent failures in a cascading manner, which is effectively a phase transition. Recent works have demonstrated that in networks with interdependent links so that the failure of one node causes the immediate failures of all nodes connected to it by such links, both first- and second-order phase transitions can arise. Moreover, there is a crossover between the two types of transitions at a critical system-parameter value. We demonstrate that these phenomena can occur in the more general setting where no interdependent links are present. A heuristic theory is derived to estimate the crossover and phase-transition points, and a remarkable agreement with numerics is obtained.

Cascading dynamics in complex quantum networks

Recently, small-scale quantum communication has been realized by transporting entangled photons, rendering potentially feasible quantum networks on large scales. We propose a class of quantum networks comprising quantum repeaters for long-distance information transport and local networks of fibers and switches. As the transmitting capability is limited by the node bandwidth, photon loss can occur through the dynamical process of cascading when the network is under external perturbations. We obtain results that can be used to guide quantum network design to minimize the photon loss.

Abnormal cascading on complex networks

In the study of cascading failures on complex networks, a key issue is to define capacities of edges and nodes as realistically as possible. This leads to the consideration of intrinsic edge capacity associated with laws governing flows on networks, which goes beyond the existing definitions of capacity based on the initial load as quantified by the betweenness centrality. Limited edge capacity (or bandwidth) and high flux or attack can trigger cascading processes, which we find as characteristically different from those reported in the literature. In particular, there can be an abnormal parameter regime where incrementally augmenting the edge capacity can counterintuitively increase the severeness of the cascading process. Another striking finding is that heterogeneous flow distribution tends to suppress the cascading process, in contrast to the current understanding that heterogeneity can make the network more vulnerable to cascading. We provide numerical computations and analysis to substantiate these findings.

Understanding and preventing cascading breakdown in complex clustered networks

Complex clustered networks are ubiquitous in natural and technological systems. Understanding the physics of the security of such networks in response to attacks is of significant value. We develop a model, based on physical analysis and numerical computations, for the key ingredients of load dynamics in typical clustered networks. With this understanding, an effective strategy is proposed for preventing cascading breakdown, one of the most disastrous events that can happen to a complex networked system.

Transient dynamics increasing network vulnerability to cascading failures

We study cascading failures in networks using a dynamical flow model based on simple conservation and distribution laws. It is found that considering the flow dynamics may imply reduced network robustness compared to previous static overload failure models. This is due to the transient oscillations or overshooting in the loads, when the flow dynamics adjusts to the new (remaining) network structure. The robustness of networks showing cascading failures is generally given by a complex interplay between the network topology and flow dynamics.

Universal robustness characteristic of weighted networks against cascading failure

We investigate the cascading failure on weighted complex networks by adopting a local weighted flow redistribution rule, where the weight of an edge is (k(i)k(j))theta with k(i) and k(j) being the degrees of the nodes connected by the edge. Assume that a failed edge leads only to a redistribution of the flow passing through it to its neighboring edges. We found that the weighted complex network reaches the strongest robustness level when the weight parameter theta=1, where the robustness is quantified by a transition from normal state to collapse. We determined that this is a universal phenomenon for all typical network models, such as small-world and scale-free networks. We then confirm by theoretical predictions this universal robustness characteristic observed in simulations. We furthermore explore the statistical characteristics of the avalanche size of a network, thus obtaining a power-law avalanche size distribution together with a tunable exponent by varying theta. Our findings have great generality for characterizing cascading-failure-induced disasters in nature.

Geographical effect on small-world network synchronization

We investigate the geographical effect on the synchronization of small-world oscillator networks. We construct small-world geographical networks by randomly adding links to one- and two-dimensional regular lattices, and we find that the synchronizability is a nonmonotonic function of both the coupling strength and the geographical distance of randomly added shortcuts. Our findings demonstrate that the geographical effect plays an important role in network synchronization, which may shed some light on the study of collective dynamics of complex networks.

Enhancing robustness and immunization in geographical networks

We find that different geographical structures of networks lead to varied percolation thresholds, although these networks may have similar abstract topological structures. Thus, strategies for enhancing robustness and immunization of a geographical network are proposed. Using the generating function formalism, we obtain an explicit form of the percolation threshold qc for networks containing arbitrary order cycles. For three-cycles, the dependence of qc on the clustering coefficients is ascertained. The analysis substantiates the validity of the strategies with analytical evidence.

Geographical networks evolving with an optimal policy

In this article we propose a growing network model based on an optimal policy involving both topological and geographical measures. In this model, at each time step, a node, having randomly assigned coordinates in a 1x1 square, is added and connected to a previously existing node i, which minimizes the quantity ri2/kialpha, where ri is the geographical distance, ki the degree, and alpha a free parameter. The degree distribution obeys a power-law form when alpha=1, and an exponential form when alpha=0. When alpha is in the interval (0, 1), the network exhibits a stretched exponential distribution. We prove that the average topological distance increases in a logarithmic scale of the network size, indicating the existence of the small-world property. Furthermore, we obtain the geographical edge length distribution, the total geographical length of all edges, and the average geographical distance of the whole network. Interestingly, we found that the total edge length will sharply increase when alpha exceeds the critical value alphac=1, and the average geographical distance has an upper bound independent of the network size. All the results are obtained analytically with some reasonable approximations, which are well verified by simulations.

Traffic of particles in complex networks

The study of the information flow through communication networks, such as the Internet, is of great importance. In the Internet, information flows in discrete units ("packets"), and the capacity of storage and processing of information of computers is finite. Thus if there are many packets walking on the network at the same time, they will interfere with each other. To understand this, we propose an idealized model, in which many particles move randomly on the network, and the nodes support limited numbers of particles. The maximum number of packets supported by a node can be any positive integer, and can be different for each node. We analyze the statistical properties of this model, obtaining analytical expressions for the mean occupation of each node, for different network topologies. The analytical results are shown to be in agreement with numerical simulations.

Geographical effects on the path length and the robustness in complex networks

The short paths between any two nodes and the robustness of connectivity are advanced properties of scale-free (SF) networks; however, they may be affected by geographical constraints in realistic situations. We consider geographical networks with the SF structure based on planar triangulation for online routings, and suggest scaling relations between the average distance or number of hops on the optimal paths and the network size. We also show that the tolerance to random failures and attacks on hubs is weakened in geographical networks, and that even then it is possible for the extremely vulnerable ones to be improved by adding with the local exchange of links.