Cascaded failures in weighted networks

Pertinence of contact duration as edge feature for epidemic spread analysis

Identifying superspreading nodes has attracted greater attention because of its wide practical significance in various applications. Existing studies consider the edges mostly equally while designing the algorithms for the unweighted contact networks, where each connection explicitly shows whether the individuals are in contact or not. It will not consider other relevant information in the context of epidemiology study or infectious disease spread, such as proximity or total time spent between the contact nodes. The recent studies focused on the weighted network, where most of the methods have computed the edge weights by utilizing degree and k-shell measure, which captures the topological structure of the network but not the interaction duration between pair of contacts. In this study, we mainly aim to generate weighted networks to model the pathogen spread by optimal calculation of the edge weight in terms of contact duration (time spent) between individual contacts. Leveraging this interaction duration as the edge weight, we further design a novel technique, namely Real Weighted Influence (RWInf), for identifying the superspreading nodes during an epidemic outbreak. The empirical study revealed that the proposed approach outperforms with an improvement of 0.146-0.473 kendall's score in comparison with baseline approaches.

Cascading failure dynamics on higher-order networks with load redistribution

The phenomenon of load redistribution in complex networks has garnered extensive attention due to its profound impact and widespread occurrence. In recent years, higher-order structures have offered new insights into understanding the structures and dynamic processes of complex networks. However, the influence of these higher-order structures on the dynamics of load redistribution, cascade failures, and recovery processes remains to be fully explored. In this study, we propose the load redistribution model with higher-order structures and recovery strategies of cascade failure based on functional upgrading and reconstruction mechanisms. In the cascading failure process with load redistribution and higher-order recovery strategies, we find that higher-order structures can induce a discontinuous phase transition at the low proportion of load redistribution, and the dynamic process displays a dual character of being robust yet fragile. These findings have been examined in both real and classical modeled networks. Interestingly, the largest connected component exhibits three distinct modes as the attack ratio increases at high densities of higher-order structures and recovery mechanisms.

Resilience of weighted networks with dynamical behavior against multi-node removal

In many real-world networks, interactions between nodes are weighted to reflect their strength, such as predator-prey interactions in the ecological network and passenger numbers in airline networks. These weighted networks are prone to cascading effects caused by minor perturbations, which can lead to catastrophic outcomes. This vulnerability highlights the importance of studying weighted network resilience to prevent system collapses. However, due to many variables and weight parameters coupled together, predicting the behavior of such a system governed by a multi-dimensional rate equation is challenging. To address this, we propose a dimension reduction technique that simplifies a multi-dimensional system into a one-dimensional state space. We applied this methodology to explore the impact of weights on the resilience of four dynamics whose weights are assigned by three weight assignment methods. The four dynamical systems are the biochemical dynamical system (B), the epidemic dynamical system (E), the regulatory dynamical system (R), and the birth-death dynamical system (BD). The results show that regardless of the weight distribution, for B, the weights are negatively correlated with the activities of the network, while for E, R, and BD, there is a positive correlation between the weights and the activities of the network. Interestingly, for B, R, and BD, the change in the weights of the system has little impact on the resilience of the system. However, for the E system, the greater the weights the more resilient the system. This study not only simplifies the complexity inherent in weighted networks but also enhances our understanding of their resilience and response to perturbations.

A model for cascading failures with the probability of failure described as a logistic function

In most cascading failure models in networks, overloaded nodes are assumed to fail and are removed from the network. However, this is not always the case due to network mitigation measures. Considering the effects of these mitigating measures, we propose a new cascading failure model that describes the probability that an overloaded node fails as a logistic function. By performing numerical simulations of cascading failures on Barabási and Albert (BA) scale-free networks and a real airport network, we compare the results of our model and the established model describing the probability of failure as a linear function. The simulation results show that the difference in the robustness of the two models depends on the initial load distribution and the redistribution of load. We further investigate the conditions of our new model under which the network exhibits the strongest robustness in terms of the load distribution and the network topology. We find the optimal value for the parameter of the load distribution and demonstrate that the robustness of the network improves as the average degree increases. The results regarding the optimal load distribution are verified by theoretical analysis. This work can be used to develop effective mitigation measures and design networks that are robust to cascading failure phenomena.

Improving robustness in interdependent networks under intentional attacks by optimizing intra-link allocation

The interdependent network is particularly vulnerable to attacks on high degree nodes; therefore, the improvement of its robustness under intentional attacks has become an important topic. In this paper, we put forward a new metric to quantify the robustness of interdependent networks against intentional attacks and develop an improved simulated annealing algorithm (ISAA) to maximize this metric by optimizing the allocation of intra-links in subnetworks. Based on the comparison between the ISAA and existing algorithms, it is found that the algorithm presented in this paper is more effective to enhance the robustness of an interdependent scale-free network (ISFN). By applying the ISAA to ISFNs with different coupling preferences, there is a key finding that the robustness of the optimized ISFN is significantly stronger than that of the original ISFN. In particular, for cases of disassortative and random couplings, no sudden collapse occurs in optimized ISFNs. According to the analysis of the degree and the clustering coefficient, we find that the subnetwork of the optimized ISFN exhibits an onion-like structure. In addition, the ISFN whose robustness is enhanced to resist the attacks on high degree nodes is still robust to the intentional attacks concerning the betweenness and PageRank.

Numerical analysis of first-passage processes in finite Markov chains exhibiting metastability

We describe state-reduction algorithms for the analysis of first-passage processes in discrete- and continuous-time finite Markov chains. We present a formulation of the graph transformation algorithm that allows for the evaluation of exact mean first-passage times, stationary probabilities, and committor probabilities for all nonabsorbing nodes of a Markov chain in a single computation. Calculation of the committor probabilities within the state-reduction formalism is readily generalizable to the first hitting problem for any number of alternative target states. We then show that a state-reduction algorithm can be formulated to compute the expected number of times that each node is visited along a first-passage path. Hence, all properties required to analyze the first-passage path ensemble (FPPE) at both a microscopic and macroscopic level of detail, including the mean and variance of the first-passage time distribution, can be computed using state-reduction methods. In particular, we derive expressions for the probability that a node is visited along a direct transition path, which proceeds without returning to the initial state, considering both the nonequilibrium and equilibrium (steady-state) FPPEs. The reactive visitation probability provides a rigorous metric to quantify the dynamical importance of a node for the productive transition between two endpoint states and thus allows the local states that facilitate the dominant transition mechanisms to be readily identified. The state-reduction procedures remain numerically stable even for Markov chains exhibiting metastability, which can be severely ill-conditioned. The rare event regime is frequently encountered in realistic models of dynamical processes, and our methodology therefore provides valuable tools for the analysis of Markov chains in practical applications. We illustrate our approach with numerical results for a kinetic network representing a structural transition in an atomic cluster.

Robustness of Air Transportation as Complex Networks:Systematic Review of 15 Years of Research and Outlook into the Future

Air transportation systems are an important part of the critical infrastructure in our connected world. Accordingly, a better understanding and improvements in the resilience of the overall air transportation system are essential to the well-functioning of our society and overall sustainability of human beings. In the literature, network science is increasingly used to better understand the resilience dynamics of air transportation. Given the wide application of tools for network science and the importance of designing resilient air transportation systems, a rich body of studies has emerged in recent years. This review paper synthesizes the related literature that has been published throughout the last 15 years regarding the robustness of air transportation systems. The contributions of this work consist of two major elements. The first part provides a comprehensive discussion and cross-comparison of the reported results. We cover several major topics, including node importance identification, failure versus attack profiles, recovery and improvement techniques, and networks of networks approaches. The second part of this paper complements the review of aggregated findings by elaborating on a future agenda for robust air transportation research. Our survey-style overview hopefully contributes toward a better understanding of the state of the art in this research area, and, in turn, to the improvement of future air transportation resilience and sustainability.

Percolation of heterogeneous flows uncovers the bottlenecks of infrastructure networks

Whether it be the passengers’ mobility demand in transportation systems, or the consumers’ energy demand in power grids, the primary purpose of many infrastructure networks is to best serve this flow demand. In reality, the volume of flow demand fluctuates unevenly across complex networks while simultaneously being hindered by some form of congestion or overload. Nevertheless, there is little known about how the heterogeneity of flow demand influences the network flow dynamics under congestion. To explore this, we introduce a percolation-based network analysis framework underpinned by flow heterogeneity. Thereby, we theoretically identify bottleneck links with guaranteed decisive impact on how flows are passed through the network. The effectiveness of the framework is demonstrated on large-scale real transportation networks, where mitigating the congestion on a small fraction of the links identified as bottlenecks results in a significant network improvement.

Infrastructure networks are characterized by fluctuations of flow demand between different points and temporal congestion or overload on flow pathways. Hamedmoghadam et al. identify congestion bottlenecks in networks relevant to communication, transportation, water supply, and power distribution.

Modelling cascading failures in networks with the harmonic closeness

Many studies on cascading failures adopt the degree or the betweenness of a node to define its load. From a novel perspective, we propose an approach to obtain initial loads considering the harmonic closeness and the impact of neighboring nodes. Based on simulation results for different adjustable parameter θ, local parameter δ and proportion of attacked nodes f, it is found that in scale-free networks (SF networks), small-world networks (SW networks) and Erdos-Renyi networks (ER networks), there exists a negative correlation between optimal θ and δ. By the removal of the low load node, cascading failures are more likely to occur in some cases. In addition, we find a valuable result that our method yields better performance compared with other methods in SF networks with an arbitrary f, SW and ER networks with large f. Moreover, the method concerning the harmonic closeness makes these three model networks more robust for different average degrees. Finally, we perform the simulations on twenty real networks, whose results verify that our method is also effective to distribute the initial load in different real networks.

Optimal control of aging in complex networks

Many complex systems experience damage accumulation, which leads to aging, manifest as an increasing probability of system collapse with time. This naturally raises the question of how to maximize health and longevity in an aging system at minimal cost of maintenance and intervention. Here, we pose this question in the context of a simple interdependent network model of aging in complex systems and show that it exhibits cascading failures. We then use both optimal control theory and reinforcement learning alongside a combination of analysis and simulation to determine optimal maintenance protocols. These protocols may motivate the rational design of strategies for promoting longevity in aging complex systems with potential applications in therapeutic schedules and engineered system maintenance.

Nonlinear model of cascade failure in weighted complex networks considering overloaded edges

Considering the elasticity of the real networks, the components in the network have a redundant capacity against the load, such as power grids, traffic networks and so on. Moreover, the interaction strength between nodes is often different. This paper proposes a novel nonlinear model of cascade failure in weighted complex networks considering overloaded edges to describe the redundant capacity for edges and capture the interaction strength of nodes. We fill this gap by studying a nonlinear weighted model of cascade failure with overloaded edges over synthetic and real weighted networks. The cascading failure model is constructed for the first time according to the overload coefficient, capacity parameter, weight coefficient, and distribution coefficient. Then through theoretical analysis, the conditions for stopping failure cascades are obtained, and the analysis shows the superiority of the constructed model. Finally, the cascading invulnerability is simulated in several typical network models and the US power grid. The results show that the model is a feasible and reasonable change of weight parameters, capacity coefficient, distribution coefficient, and overload coefficient can significantly improve the destructiveness of complex networks against cascade failure. Our methodology provides an efficacious reference for the control and prevention of cascading failures in many real networks.

Cascading Failures and Vulnerability Evolution in Bus⁻Metro Complex Bilayer Networks under Rainstorm Weather Conditions

In recent years, the frequent occurrence of rainstorms has seriously affected urban–public transport systems. In this study, we examined the impact of rainstorms on the vulnerability of urban–public transport systems consisting of both ground bus and metro systems, which was abstracted into an undirected weighted Bus–Metro complex bilayer network (Bus–Metro CBN) and the passenger volume was regarded as its weight. Through the changes in the node scale, network efficiency, and passenger volume in the maximal connected component of the Bus–Metro CBN, we constructed a vulnerability operator to quantitatively calculate the vulnerability of the Bus–Metro CBN. Then, the flow-based couple map lattices (CMLs) model was proposed to simulate cascading failure scenarios of the Bus–Metro CBN under rainstorm conditions, in which the rainstorm is introduced through a perturbation variable. The simulation results show that under the condition of passenger flow overload, the network may have a two-stage cascading failure process. The impact analysis shows that there is a rainstorm intensity threshold that causes the Bus–Metro CBN to collapse. Meanwhile, we obtained the optimal node and edge capacity through capacity analysis. In addition, our analysis implies that the vulnerability of the Bus–Metro CBN network in most scenarios is mainly caused by the degradation of network structure rather than the loss of passenger flow. The network coupling strength analysis results show that the node coupling strength has greater potential to reduce the vulnerability than edge coupling strength. This indicates that traffic managers should prioritize controlling the mutual influence between bus stops (or metro stations) to reduce the vulnerability of the Bus–Metro CBN more effectively.

Emergent Failures and Cascades in Power Grids: A Statistical Physics Perspective

We model power grids transporting electricity generated by intermittent renewable sources as complex networks, where line failures can emerge indirectly by noisy power input at the nodes. By combining concepts from statistical physics and the physics of power flows and taking weather correlations into account, we rank line failures according to their likelihood and establish the most likely way such failures occur and propagate. Our insights are mathematically rigorous in a small-noise limit and are validated with data from the German transmission grid.

Cascading failures in interdependent systems under a flow redistribution model

Robustness and cascading failures in interdependent systems has been an active research field in the past decade. However, most existing works use percolation-based models where only the largest component of each network remains functional throughout the cascade. Although suitable for communication networks, this assumption fails to capture the dependencies in systems carrying a flow (e.g., power systems, road transportation networks), where cascading failures are often triggered by redistribution of flows leading to overloading of lines. Here, we consider a model consisting of systems A and B with initial line loads and capacities given by {L_{A,i},C_{A,i}}_{i=1}^{n} and {L_{B,i},C_{B,i}}_{i=1}^{n}, respectively. When a line fails in system A, a fraction of its load is redistributed to alive lines in B, while remaining (1-a) fraction is redistributed equally among all functional lines in A; a line failure in B is treated similarly with b giving the fraction to be redistributed to A. We give a thorough analysis of cascading failures of this model initiated by a random attack targeting p_{1} fraction of lines in A and p_{2} fraction in B. We show that (i) the model captures the real-world phenomenon of unexpected large scale cascades and exhibits interesting transition behavior: the final collapse is always first order, but it can be preceded by a sequence of first- and second-order transitions; (ii) network robustness tightly depends on the coupling coefficients a and b, and robustness is maximized at non-trivial a,b values in general; (iii) unlike most existing models, interdependence has a multifaceted impact on system robustness in that interdependency can lead to an improved robustness for each individual network.

Optimizing the robustness of electrical power systems against cascading failures

Electrical power systems are one of the most important infrastructures that support our society. However, their vulnerabilities have raised great concern recently due to several large-scale blackouts around the world. In this paper, we investigate the robustness of power systems against cascading failures initiated by a random attack. This is done under a simple yet useful model based on global and equal redistribution of load upon failures. We provide a comprehensive understanding of system robustness under this model by (i) deriving an expression for the final system size as a function of the size of initial attacks; (ii) deriving the critical attack size after which system breaks down completely; (iii) showing that complete system breakdown takes place through a first-order (i.e., discontinuous) transition in terms of the attack size; and (iv) establishing the optimal load-capacity distribution that maximizes robustness. In particular, we show that robustness is maximized when the difference between the capacity and initial load is the same for all lines; i.e., when all lines have the same redundant space regardless of their initial load. This is in contrast with the intuitive and commonly used setting where capacity of a line is a fixed factor of its initial load.

Optimal Allocation of Node Capacity in Cascade-Robustness Networks

The robustness of large scale critical infrastructures, which can be modeled as complex networks, is of great significance. One of the most important means to enhance robustness is to optimize the allocation of resources. Traditional allocation of resources is mainly based on the topology information, which is neither realistic nor systematic. In this paper, we try to build a framework for searching for the most favorable pattern of node capacity allocation to reduce the vulnerability to cascading failures at a low cost. A nonlinear and multi-objective optimization model is proposed and tackled using a particle swarm optimization algorithm (PSO). It is found that the network becomes more robust and economical when less capacity is left on the heavily loaded nodes and the optimized network performs better resisting noise. Our work is helpful in designing a robust economical network.

Abnormal Behavior in Cascading Dynamics with Node Weight

Considering a preferential selection mechanism of load destination, we introduce a new method to quantify initial load distribution and subsequently construct a simple cascading model. By attacking the node with the highest load, we investigate the cascading dynamics in some synthetic networks. Surprisingly, we observe that for several networks of different structural patterns, a counterintuitive phenomenon emerges if the highest load attack is applied to the system, i.e., investing more resources to protect every node in a network inversely makes the whole network more vulnerable. We explain this ability paradox by analyzing the micro-structural components of the underlying network and therefore reveals how specific structural patterns may influence the cascading dynamics. We discover that the robustness of the network oscillates as the capacity of each node increases. The conclusion of the paper may shed lights on future investigations to avoid the demonstrated ability paradox and subsequent cascading failures in real-world networks.

Ability paradox of cascading model based on betweenness

Must Investing more resources to protect every node in a network improve the robustness of the whole network subject to target attacks? To answer this question, we investigate the cascading dynamics in some typical networks. In real networks, the load on a node is generally correlated with the betweenness. Considering the weight of a node, we give a new method to define the initial load on a node by the revised betweenness. Then we present a simple cascading model. We investigate the cascading dynamics by disabling a single key node with the highest load. We find that in BA scale-free networks, the bigger the capacity of every node, the stronger the robustness of the whole network. However, in WS networks and some random networks, when we increase the capacity of every node, instead, the robustness of the whole network is weaker. In US power grid and the China power grid, we also observe this counterintuitive phenomenon. We give a reasonable explanation by a simple illusion. By the analysis, we think that resurrections of some nodes in a ring network structure after removing a node may be the reason of this phenomenon.

Resiliency of EEG-Based Brain Functional Networks

Applying tools available in network science and graph theory to study brain networks has opened a new era in understanding brain mechanisms. Brain functional networks extracted from EEG time series have been frequently studied in health and diseases. In this manuscript, we studied failure resiliency of EEG-based brain functional networks. The network structures were extracted by analysing EEG time series obtained from 30 healthy subjects in resting state eyes-closed conditions. As the network structure was extracted, we measured a number of metrics related to their resiliency. In general, the brain networks showed worse resilient behaviour as compared to corresponding random networks with the same degree sequences. Brain networks had higher vulnerability than the random ones (P < 0.05), indicating that their global efficiency (i.e., communicability between the regions) is more affected by removing the important nodes. Furthermore, the breakdown happened as a result of cascaded failures in brain networks was severer (i.e., less nodes survived) as compared to randomized versions (P < 0.05). These results suggest that real EEG-based networks have not been evolved to possess optimal resiliency against failures.

Robustness of power systems under a democratic-fiber-bundle-like model

We consider a power system with N transmission lines whose initial loads (i.e., power flows) L(1),...,L(N) are independent and identically distributed with P(L)(x)=P[L≤x]. The capacity C(i) defines the maximum flow allowed on line i and is assumed to be given by C(i)=(1+α)L(i), with α>0. We study the robustness of this power system against random attacks (or failures) that target a p fraction of the lines, under a democratic fiber-bundle-like model. Namely, when a line fails, the load it was carrying is redistributed equally among the remaining lines. Our contributions are as follows. (i) We show analytically that the final breakdown of the system always takes place through a first-order transition at the critical attack size p(☆)=1-(E[L]/max(x)(P[L>x](αx+E[L|L>x])), where E[·] is the expectation operator; (ii) we derive conditions on the distribution P(L)(x) for which the first-order breakdown of the system occurs abruptly without any preceding diverging rate of failure; (iii) we provide a detailed analysis of the robustness of the system under three specific load distributions-uniform, Pareto, and Weibull-showing that with the minimum load L(min) and mean load E[L] fixed, Pareto distribution is the worst (in terms of robustness) among the three, whereas Weibull distribution is the best with shape parameter selected relatively large; (iv) we provide numerical results that confirm our mean-field analysis; and (v) we show that p(☆) is maximized when the load distribution is a Dirac delta function centered at E[L], i.e., when all lines carry the same load. This last finding is particularly surprising given that heterogeneity is known to lead to high robustness against random failures in many other systems.

Threshold cascades with response heterogeneity in multiplex networks

Threshold cascade models have been used to describe the spread of behavior in social networks and cascades of default in financial networks. In some cases, these networks may have multiple kinds of interactions, such as distinct types of social ties or distinct types of financial liabilities; furthermore, nodes may respond in different ways to influence from their neighbors of multiple types. To start to capture such settings in a stylized way, we generalize a threshold cascade model to a multiplex network in which nodes follow one of two response rules: some nodes activate when, in at least one layer, a large enough fraction of neighbors is active, while the other nodes activate when, in all layers, a large enough fraction of neighbors is active. Varying the fractions of nodes following either rule facilitates or inhibits cascades. Near the inhibition regime, global cascades appear discontinuously as the network density increases; however, the cascade grows more slowly over time. This behavior suggests a way in which various collective phenomena in the real world could appear abruptly yet slowly.

Random walks in weighted networks with a perfect trap: an application of Laplacian spectra

Trapping processes constitute a primary problem of random walks, which characterize various other dynamical processes taking place on networks. Most previous works focused on the case of binary networks, while there is much less related research about weighted networks. In this paper, we propose a general framework for the trapping problem on a weighted network with a perfect trap fixed at an arbitrary node. By utilizing the spectral graph theory, we provide an exact formula for mean first-passage time (MFPT) from one node to another, based on which we deduce an explicit expression for average trapping time (ATT) in terms of the eigenvalues and eigenvectors of the Laplacian matrix associated with the weighted graph, where ATT is the average of MFPTs to the trap over all source nodes. We then further derive a sharp lower bound for the ATT in terms of only the local information of the trap node, which can be obtained in some graphs. Moreover, we deduce the ATT when the trap is distributed uniformly in the whole network. Our results show that network weights play a significant role in the trapping process. To apply our framework, we use the obtained formulas to study random walks on two specific networks: trapping in weighted uncorrelated networks with a deep trap, the weights of which are characterized by a parameter, and Lévy random walks in a connected binary network with a trap distributed uniformly, which can be looked on as random walks on a weighted network. For weighted uncorrelated networks we show that the ATT to any target node depends on the weight parameter, that is, the ATT to any node can change drastically by modifying the parameter, a phenomenon that is in contrast to that for trapping in binary networks. For Lévy random walks in any connected network, by using their equivalence to random walks on a weighted complete network, we obtain the optimal exponent characterizing Lévy random walks, which have the minimal average of ATTs taken over all target nodes.

Epidemic spreading in weighted networks: an edge-based mean-field solution

Weight distribution greatly impacts the epidemic spreading taking place on top of networks. This paper presents a study of a susceptible-infected-susceptible model on regular random networks with different kinds of weight distributions. Simulation results show that the more homogeneous weight distribution leads to higher epidemic prevalence, which, unfortunately, could not be captured by the traditional mean-field approximation. This paper gives an edge-based mean-field solution for general weight distribution, which can quantitatively reproduce the simulation results. This method could be applied to characterize the nonequilibrium steady states of dynamical processes on weighted networks.