Model for cascading failures with adaptive defense in complex networks

<正>This paper investigates cascading failures in networks by considering interplay between the flow dynamic and the network topology,where the fluxes exchanged between a pair of nodes can be adaptively adjusted depending on the changes of the shortest path lengths between them.The simulations on both an artificially created scale-free network and the real network structure of the power grid reveal that the adaptive adjustment of the fluxes can drastically enhance the robustness of complex networks against cascading failures.Particularly,there exists an optimal region where the propagation of the cascade is significantly suppressed and the fluxes supported by the network are maximal. With this understanding,a costless strategy of defense for preventing cascade breakdown is proposed.It is shown to be more effective for suppressing the propagation of the cascade than the recent proposed strategy of defense based on the intentional removal of nodes.     

基于超图的超网络相继故障分析

分析了快递超网络和电子元件超网络的相继故障扩散方式, 结合超图理论提出了2-section 图分析法和线图分析法, 并仿真分析了无标度超网络耦合映像格子的相继故障进程. 结果表明: 无标度超网络对外部攻击表现出了既鲁棒又脆弱的特性. 针对相继故障的不同扩散方式, 无标度超网络的相继故障行为表现出不同的特点. 超网络的相继故障行为和超网络的超度以及超边度分布有密切的联系, 也和超网络中超边的个数有关. 通过和同规模的Barabasi-Albert (BA)无标度网络对比, 在同一种攻击方式下同规模的无标度超网络都比BA 无标度网络表现出了更强的鲁棒性. 另外, 基于超边扩散的相继故障进程比基于节点扩散的相继故障进程更加缓慢.     

多层网络级联失效的预防和恢复策略概述

现实生活中,与国计民生密切相关的基础设施网络大多不是独立存在的,而是彼此之间相互联系或依赖的,于是用于研究这些系统的多层网络模型随之产生.多层网络中的节点在失效或者遭受攻击后会因"层内"和"层间"的相互作用而产生级联效应,从而使得失效能够在网络层内和层间反复传播并使得失效规模逐步放大.因此,多层网络比单个网络更加脆弱.多层网络级联失效产生的影响和损失往往是非常巨大的,所以对多层网络级联失效的预防和恢复的研究具有重大意义.就多层网络级联失效的预防而言,主要包含故障检测,保护重要节点,改变网络耦合机制和节点备份等策略.就多层网络发生级联失效后的恢复策略而言,主要包含共同边界节点恢复、空闲连边恢复、加边恢复、重要节点优先恢复、更改拓扑结构、局域攻击修复、自适应边修复等策略.     

一种全局同质化相依网络耦合模式

相依网络的相依模式(耦合模式)是影响其鲁棒性的重要因素之一.本文针对具有无标度特性的两个子网络提出一种全局同质化相依网络耦合模式.该模式以子网络的总度分布均匀化为原则建立相依网络的相依边,一方面压缩度分布宽度,提高其对随机失效的抗毁性,另一方面避开对度大节点(关键节点)的相依,提高其对蓄意攻击的抗毁性.论文将其与常见的节点一对一的同配、异配及随机相依模式以及一对多随机相依模式作了对比分析,仿真研究其在随机失效和蓄意攻击下的鲁棒性能.研究结果表明,本文所提全局同质化相依网络耦合模式能大大提高无标度子网络所构成的相依网络抗级联失效能力.本文研究成果能够为相依网络的安全设计等提供指导意义.     

Sensitivity of the resilience of congested random networks to rolloff and offset in truncated power-law degree distributions

Random networks were generated with the random configuration model with prescribed truncated power-law degree distributions, parameterized by an exponent, an offset, and an exponential rolloff. As a model of an attack, each network had exactly one of its highest degree nodes removed, with the result that in some cases, one or more remaining nodes became congested with the reassignment of the load. The congested nodes were then removed, and the “cascade failure” process continued until all nodes were uncongested. The ratio of the number of nodes of the largest remaining cluster to the number of nodes in the original network was taken to be a measure of the network's resiliency to highest-degree node removal. We found that the resiliency is sensitive to both rolloff and offset (but not to cutoff) in the degree distribution, and that rolloff tends to decrease resiliency while offset tends to increase it.     

Stability and topology of scale-free networks under attack and defense strategies

We study tolerance and topology of random scale-free networks under attack and defense strategies that depend on the degree k of the nodes. This situation occurs, for example, when the robustness of a node depends on its degree or in an intentional attack with insufficient knowledge of the network. We determine, for all strategies, the critical fraction p(c) of nodes that must be removed for disintegrating the network. We find that, for an intentional attack, little knowledge of the well-connected sites is sufficient to strongly reduce p(c). At criticality, the topology of the network depends on the removal strategy, implying that different strategies may lead to different kinds of percolation transitions.     

Preservation of network degree distributions from non-uniform failures

There has been a considerable amount of interest in recent years on the robustness of networks to failures. Many previous studies have concentrated on the effects of node and edge removals on the connectivity structure of a static network; the networks are considered to be static in the sense that no compensatory measures are allowed for recovery of the original structure. Real world networks such as the world wide web, however, are not static and experience a considerable amount of turnover, where nodes and edges are both added and deleted. Considering degree-based node removals, we examine the possibility of preserving networks from these types of disruptions. We recover the original degree distribution by allowing the network to react to the attack by introducing new nodes and attaching their edges via specially tailored schemes. We focus particularly on the case of non-uniform failures, a subject that has received little attention in the context of evolving networks. Using a combination of analytical techniques and numerical simulations, we demonstrate how to preserve the exact degree distribution of the studied networks from various forms of attack.     

Robustness of Cyber-Physical Supply Networks in Cascading Failures

A cyber-physical supply network is composed of an undirected cyber supply network and a directed physical supply network. Such interdependence among firms increases efficiency but creates more vulnerabilities. The adverse effects of any failure can be amplified and propagated throughout the network. This paper aimed at investigating the robustness of the cyber-physical supply network against cascading failures. Considering that the cascading failure is triggered by overloading in the cyber supply network and is provoked by underload in the physical supply network, a realistic cascading model for cyber-physical supply networks is proposed. We conducted a numerical simulation under cyber node and physical node failure with varying parameters. The simulation results demonstrated that there are critical thresholds for both firm’s capacities, which can determine whether capacity expansion is helpful; there is also a cascade window for network load distribution, which can determine the cascading failures occurrence and scale. Our work may be beneficial for developing cascade control and defense strategies in cyber-physical supply networks.     

电网在三种边攻击方式下的级联失效

研究美国西部电网在三种边攻击方式下级联失效差异性.定义边ij的初始负载为(k_ik_j)^θ,k_i,k_j分别表示节点i和j的度,θ为一可调参数.三种边攻击方式分别为:最小负载边攻击方式(LL)、最大负载边攻击方式(HL)和容量比最小边攻击方式(SPC).通过分析电网的拓扑结构,研究三种攻击方式级联失效差异性.研究表明:HL和LL攻击方式下,受攻击边的范围不随θ而改变,HL的攻击效果随θ的增大而增强,LL的攻击效果随θ的增大而减弱.而SPC法选中的被攻击边随θ变化,当θ取值较小时,SPC攻击边是拓扑结构较特殊的一种最小负载边,随着θ的增大,SPC攻击边趋向于高负载边,因此θ较小时,SPC的攻击效果和LL接近,当θ较大时,SPC的攻击效果和HL接近.     

Cascade Defense via Control of the Fluxes in Complex Networks

Exploring the possible strategies to defense to prevent the cascade from propagating through the entire network is of both theoretical interest and practical significance, and several strategies of defense have been developed recently. Following the work about the strategy based on the international removal of network elements (Motter in Phys. Rev. Lett. 93:098701, 2004), we propose and investigate three novel strategies of defense by controlling the fluxes. Extensive simulations on both an artificially created scale-free network and the Internet at autonomous system level reveal that these strategies can suppress the propagation of the cascade, even avoid the cascading failure. In addition, a more intuitive and important measure to quantify the damage caused by a cascade is developed and some new features are, thus, clearly displayed.     

A Robustness Model of Complex Networks with Tunable Attack Information Parameter

We introduce a novel model for robustness of complex with a tunable attack information parameter. The random failure and intentional attack known are the two extreme cases of our model. Based on the model, we study the robustness of complex networks under random information and preferential information, respectively. Using the generating function method, we derive the exact value of the critical removal fraction of nodes for the disintegration of networks and the size of the giant component. We show that hiding just a small fraction of nodes randomly can prevent a scale-free network from collapsing and detecting just a small fraction of nodes preferentially can destroy a scale-free network.     

Networked characteristics of the urban rail transit networks

Urban rail transit networks (URTNs) have experienced rapid development and have been receiving much attention recently. In this paper, we comprehensively analyze the topological characteristics of urban rail transit networks, and we find that the average degrees of nodes of urban rail transit networks lie in the interval [2, 2.45], most of the average shortest path lengths between pairs of nodes belong to the interval [10, 16] and the average betweenness of nodes and edges linearly increase with the increase of the number of stations. Moreover, the cumulative probability distributions of the degree and shortest path length can be fitted by exponential distribution and Gauss distribution, respectively. The network failures of the urban rail transit networks are discussed and we also discover that the highest betweenness node-based attack is the most effective method to destroy the network.     

Exploring the robustness of urban bus network: A case from Southern China

The robustness of urban bus network is essential to a city that heavily relies on buses as its main transportation solution. In this paper, the urban bus network has been modeled as a directed and space L network, and Changsha, a transportation hub of nearly 8 million people and hundreds of bus lines in southern China, is taken as a case. Based on the quantitative analyses of the topological properties, it is found that Changsha urban bus network is a scale-free network, not a small-world network. To evaluate the robustness of the network, five scenarios of network failure are simulated, including a random failure and four types of intentional attacks that differed in key node identification methods (i.e., unweighted degree or betweenness centrality) and attack strategies (i.e., normal or cascading attack). It is revealed that intentional attacks are more destructive than a random failure, and cascading attacks are more disruptive than normal attacks in the urban bus network. In addition, the key nodes identification methods are found to play a critical role in the robustness of the urban bus network. Specifically, cascading attack could be more disruptive when the betweenness centrality is used to identify key nodes; in contrast, normal attack could be more disruptive when the unweighted degree is used to identify key nodes. Our results could provide reference for risk management of urban bus network.     

Edge-based-attack induced cascading failures on scale-free networks

Most previous existing works on cascading failures only focused on attacks on nodes rather than on edges. In this paper, we discuss the response of scale-free networks subject to two different attacks on edges during cascading propagation, i.e., edge removal by either the descending or ascending order of the loads. Adopting a cascading model with a breakdown probability p of an overload edge and the initial load (k_ik_j)^α of an edge ij, where k_i and k_j are the degrees of the nodes connected by the edge ij and α is a tunable parameter, we investigate the effects of two attacks for the robustness of Barabási-Albert (BA) scale-free networks against cascading failures. In the case of α<1, our investigation by the numerical simulations leads to a counterintuitive finding that BA scale-free networks are more sensitive to attacks on the edges with the lowest loads than the ones with the highest loads, not relating to the breakdown probability. In addition, the same effect of two attacks in the case of α=1 may be useful in furthering studies on the control and defense of cascading failures in many real-life networks. We then confirm by the theoretical analysis these results observed in simulations.     

Comparison of cascading failures in small-world and scale-free networks subject to vertex and edge attacks

Complex networks may undergo a global cascade of overload failures when a single highly loaded vertex or edge is intentionally attacked. Here we use the recent load model of cascading failures to investigate the performance of the small-world (SW) and scale-free (SF) networks subject to deliberate attacks on vertex and edge. Simulation results suggest that compared with the SW network, the SF network is more vulnerable to deliberate vertex attacks and more robust to deliberate edge attacks. In the SF network, deliberate vertex attacks can result in larger cascading failures than deliberate edge attacks; however, in the SW network the situation is opposite. Furthermore, with the increase of the rewiring probability the SW network becomes more and more robust to deliberate vertex and edge attacks.     

Two-peak and three-peak optimal complex networks

A central issue in complex networks is tolerance of random failures and intentional attacks. Current literature emphasizes the dichotomy between networks with a power-law node connectivity distribution, which are robust to random failures but fragile to targeted attacks, versus networks with an exponentially decaying connectivity distribution, which are less tolerant to failures but more resilient to attacks. We prove analytically that the optimal network configuration under a classic measure of robustness is altogether different from both of the above: in all cases, failure and/or attack, there are no more than three distinct node connectivities in the optimal network.     

Evaluation of network robustness using a node tearing algorithm

Until recently the study of failure and vulnerability in complex networks focused on the role of high degree nodes, and the relationship between their removal and network connectivity. Recent evidence suggested that in some network configurations, the removal of lower degree nodes can also cause network fragmentation. We present a disassembling algorithm that identifies nodes that are core to network connectivity. The algorithm is based on network tearing in which communities are defined and used to construct a hierarchical structure. Cut-nodes, which are located at the boundaries of the communities, are the key interest. Their importance in the overall network connectivity is characterized by their participation with neighbouring communities in each level of the hierarchy. We examine the impact of these cut-nodes by studying the change in size of the giant component, local and global efficiencies, and how the algorithm can be combined with other community detection methods to reveal the finer internal structure within a community.     

Complex networks: Dynamics and security

This paper presents a perspective in the study of complex networks by focusing on how dynamics may affect network security under attacks. In particular, we review two related problems: attack-induced cascading breakdown and range-based attacks on links. A cascade in a network means the failure of a substantial fraction of the entire network in a cascading manner, which can be induced by the failure of or attacks on only a few nodes. These have been reported for the internet and for the power grid (e.g., the August 10, 1996 failure of the western United States power grid). We study a mechanism for cascades in complex networks by constructing a model incorporating the flows of information and physical quantities in the network. Using this model we can also show that the cascading phenomenon can be understood as a phase transition in terms of the key parameter characterizing the node capacity. For a parameter value below the phase-transition point, cascading failures can cause the network to disintegrate almost entirely. We will show how to obtain a theoretical estimate for the phase-transition point. The second problem is motivated by the fact that most existing works on the security of complex networks consider attacks on nodes rather than on links. We address attacks on links. Our investigation leads to the finding that many scale-free networks are more sensitive to attacks on short-range than on long-range links. Considering that the small-world phenomenon in complex networks has been identified as being due to the presence of long-range links, i.e., links connecting nodes that would otherwise be separated by a long node-to-node distance, our result, besides its importance concerning network efficiency and security, has the striking implication that the small-world property of scale-free networks is mainly due to short-range links.     

Failure tolerance of spike phase synchronization in coupled neural networks

Neuronal synchronization plays an important role in the various functionality of nervous system such as binding, cognition, information processing, and computation. In this paper, we investigated how random and intentional failures in the nodes of a network influence its phase synchronization properties. We considered both artificially constructed networks using models such as preferential attachment, Watts-Strogatz, and Erdo?s-Re?nyi as well as a number of real neuronal networks. The failure strategy was either random or intentional based on properties of the nodes such as degree, clustering coefficient, betweenness centrality, and vulnerability. Hindmarsh-Rose model was considered as the mathematical model for the individual neurons, and the phase synchronization of the spike trains was monitored as a function of the percentage∕number of removed nodes. The numerical simulations were supplemented by considering coupled non-identical Kuramoto oscillators. Failures based on the clustering coefficient, i.e., removing the nodes with high values of the clustering coefficient, had the least effect on the spike synchrony in all of the networks. This was followed by errors where the nodes were removed randomly. However, the behavior of the other three attack strategies was not uniform across the networks, and different strategies were the most influential in different network structure.     

Robustness of spatial networks and networks of networks

Many complex networks have recently been recognized to involve significant interdependence between different systems. Motivation comes primarily from infrastructures like power grids and communications networks, but also includes areas such as the human brain and finance. Interdependence implies that when components in one system fail, they lead to failures in the same system or other systems. This can then lead to additional failures finally resulting in a long cascade that can cripple the entire system. Furthermore, many of these networks, in particular infrastructure networks, are embedded in space and thus have unique spatial properties that significantly decrease their resilience to failures. Here we present a review of novel results on interdependent spatial networks and how cascading processes are affected by spatial embedding. We include various aspects of spatial embedding such as cases where dependencies are spatially restricted and localized attacks on nodes contained in some spatial region of the network. In general, we find that spatial networks are more vulnerable when they are interdependent and that they are more likely to undergo abrupt failure transitions than interdependent non-embedded networks. We also present results on recovery in spatial networks, the nature of cascades due to overload failures in these networks, and some examples of percolation features found in real-world traffic networks. Finally, we conclude with an outlook on future possible research directions in this area.