基于相继故障信息的网络节点重要度演化机理分析

分析了过载机制下节点重要度的演化机理.首先,在可调负载重分配级联失效模型基础上,根据节点失效后其分配范围内节点的负载振荡程度,提出了考虑级联失效局域信息的复杂网络节点重要度指标.该指标具有两个特点:一是值的大小可以清晰地指出节点的失效后果;二是可以依据网络负载分配范围、负载分配均匀性、节点容量系数及网络结构特征分析节点重要度的演化情况.然后,给出该指标的仿真算法,并推导了最近邻择优分配和全局择优分配规则下随机网络和无标度网络节点重要度的解析表达式.最后,实验验证了该指标的有效性和可行性,并深入分析了网络中节点重要度的演化机理,即非关键节点如何演化成影响网络级联失效行为的关键节点.     

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.     

带有层级结构的复杂网络级联失效模型

针对现实世界的网络中普遍存在的层级结构建立一个级联失效模型, 该模型可用于优化金融、物流网络设计. 选择的层级网络模型具有树形骨架和异质的隐含连接, 并且骨架中每层节点拥有的分枝数服从正态分布. 级联失效模型中对底层节点的打击在不完全信息条件下进行, 也即假设打击者无法观察到隐含连接. 失效节点的负载重分配考虑了层级异质性, 它可以选择倾向于向同级或高层级完好节点分配额外负载. 仿真实验表明, 层级网络的拓扑结构随连接参数变化逐渐从小世界网络过渡到随机网络. 网络级联失效规模随隐含连接比例呈现出先增加后降低的规律. 负载重分配越倾向于高层级节点, 网络的抗毁损性越高. 同时, 由于连接参数会改变隐含连接在不同层级之间的分布, 进而对网络的抗毁损性产生显著影响, 为了提高网络抗毁损能力, 设计网络、制定管理控制策略时应合理设定连接参数. 关键词： 复杂网络 级联失效 层级结构     

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

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

Cascading failure in the wireless sensor scale-free networks

In the practical wireless sensor networks(WSNs), the cascading failure caused by a failure node has serious impact on the network performance. In this paper, we deeply research the cascading failure of scale-free topology in WSNs. Firstly,a cascading failure model for scale-free topology in WSNs is studied. Through analyzing the influence of the node load on cascading failure, the critical load triggering large-scale cascading failure is obtained. Then based on the critical load,a control method for cascading failure is presented. In addition, the simulation experiments are performed to validate the effectiveness of the control method. The results show that the control method can effectively prevent cascading failure.     

复杂网络中带有应急恢复机理的级联动力学分析

提出带有应急恢复机理的网络级联故障模型,研究模型在最近邻耦合网络,Erdos-Renyi随机网络,Watts-Strogatz小世界网络和Barabasi-Albert无标度网络四种网络拓扑下的网络级联动力学行为.给出了应急恢复机理和网络效率的定义,并研究了模型中各参数对网络效率和网络节点故障率在级联故障过程中变化情况的影响.结果表明,模型中应急恢复概率的增大减缓了网络效率的降低速度和节点故障率的增长速度,并且提高了网络的恢复能力.而且网络中节点负载容量越大,网络效率降低速度和节点故障率的增长速度越慢.同时,随着节点过载故障概率的减小,网络效率的降低速度和节点故障率的增长速度也逐渐减缓.此外,对不同网络拓扑中网络效率和网络节点故障率在级联故障过程中的变化情况进行分析,结果发现网络拓扑节点度分布的异质化程度的增大,提高了级联故障所导致的网络效率的降低速度和网络节点故障率的增长速度.以上结果分析了复杂网络中带有应急恢复机理的网络级联动力学行为,为实际网络中级联故障现象的控制和防范提供了参考.     

An LCOR model for suppressing cascading failure in weighted complex networks

Based on the relationship between capacity and load, cascading failure on weighted complex networks is investigated, and a load-capacity optimal relationship (LCOR) model is proposed in this paper. Compared with three other kinds of load-capacity linear or non-linear relationship models in model networks as well as a number of real-world weighted networks including the railway network, the airports network and the metro network, the LCOR model is shown to have the best robustness against cascading failure with less cost. Furthermore, theoretical analysis and computational method of its cost threshold are provided to validate the effectiveness of the LCOR model. The results show that the LCOR model is effective for designing real-world networks with high robustness and less cost against cascading failure.     

Impact of core-periphery structure on cascading failures in interdependent scale-free networks

Core-periphery structure is a typical meso-scale structure in networks. Previous studies on core-periphery structure mainly focus on the improvement of detection methods, while the research on the impact of core-periphery structure on cascading failures in interdependent networks is still missing. Therefore, we investigate the cascading failures of interdependent scale-free networks with different core-periphery structures and coupling preferences in the paper. First, we introduce an evaluation index to calculate the goodness of core-periphery structure. Second, we propose a new scale-free network evolution model, which can generate tunable core-periphery structures, and its degree distribution is analyzed mathematically. Finally, based on a degree-load-based cascading failure model, we mainly investigate the impact of goodness of core-periphery structure on cascading failures in both symmetrical and asymmetrical interdependent networks. Through numerical simulations, we find that with the same average degree, the networks with weak core-periphery structure will be more robust, while the initial load on node will influence the improvement of robustness. In addition, we also find that the inter-similarity coupling performs better than random coupling. These findings may be helpful for building resilient interdependent networks.     

基于负荷局域择优重新分配原则的复杂网络上的相继故障

相继故障普遍存在现实的网络系统中,为了更好地探讨复杂网络抵制相继故障的全局鲁棒性,采用网络中节点j上的初始负荷为L_j=k^α_j（k_j为节点j的度）的形式,并基于崩溃节点上负荷的局域择优重新分配的原则,提出了一个新的相继故障模型.依据新的度量网络鲁棒性的指标,探讨了4种典型复杂网络上的相继故障现象.数值模拟表明, 关键词： 相继故障 复杂网络 关键阈值 相变     

基于可调负载重分配的无标度网络连锁效应分析

为了深入研究复杂网络抵制连锁故障的全局鲁棒性,针对现实网络上的负载重分配规则常常是介于全局分配与最近邻分配、均匀分配与非均匀分配的特点,围绕负荷这一影响连锁故障发生和传播最重要的物理量以及节点崩溃后的动力学过程,提出了一种可调负载重分配范围与负载重分配异质性的复杂网络连锁故障模型,并分析了该模型在无标度网络上的连锁故障条件.数值模拟获得了复杂网络抵制连锁故障的鲁棒性与模型中参数的关系.此外,基于网络负载分配规则的分析以及理论解析的推导,验证了数值模拟结论,也证明在最近邻与全局分配两种规则下都存在负载分配均匀性参数等于初始负荷强度参数即β=τ使得网络抵御连锁故障的能力最强.     

Cascading dynamics with local weighted flow redistribution in interdependent networks

We study load cascading dynamics in a system composed of coupled interdependent networks while adopting a local weighted flow redistribution rule. We find that when the intra- or inter-connectivity increases, robustness against the cascade of load failures in the symmetrically coupled interdependent networks increases. In addition, when a failed link has to first split its flow asymmetrically to its neighbouring link groups according to the link types, even though there exists an optimal split, the robustness is lowered in contrast with the non-split situation. Furthermore, the optimal weighting mechanism in an isolated network no longer holds in interdependent networks. Finally, robustness against the cascade of load failures is not guaranteed to increase by making the distribution of the degree of intra-connectivity broader. We confirm these phenomena by theoretical analysis based on mean-field theory. Our findings might have great implications for preventing load-failure-induced local cascades in symmetrically coupled interdependent networks.     

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.     

Load-dependent random walks on complex networks

Load-dependent random walks are used to investigate the evolution of load distribution in transportation network systems. The walkers hop to a node according to node load of the last time step. The preference of walks leads to a change in the load distribution. It changes from degree-dependent distribution in the case of non-preference walks to eigenvector-centrality-dependent distribution. By numerical simulations, it is shown that the network heterogeneity has a influence on the effect of walk preference. In the cascading failure phenomenon, an appropriate degree correlation can guarantee a low risk of cascading failures.     

Dynamics of load entropy during cascading failure propagation in scale-free networks

In this Letter, we introduce the concept of load entropy, which can be an average measure of a network's heterogeneity in the load distribution. Then we investigate the dynamics of load entropy during failure propagation using a new cascading failures load model, which can represent the node removal mechanism in many real-life complex systems. Simulation results show that in the early stage of failure propagation the load entropy for a larger cascading failure increases more sharply than that for a smaller one, and consequently the cascading failure with a larger damage can be identified at the early stage of failure propagation according to the load entropy. Particularly, load entropy can be used as an index to be optimized in cascading failures control and defense in many real-life complex networks.     

Robustness analysis of static routing on networks

Robustness is one of the crucial properties that needs to be considered in the design of routing strategies on networks. We study the robustness of three typical routing strategies, which are the SP (shortest path), EP (efficient path), and OP (optimal path) strategies, by simulating several different kinds of attacks including random attacks, target attacks and cascading failures on scale-free networks. Results of the average path length, betweenness centrality, network capacity, etc., demonstrate that the EP strategy is more robust than the other two, and the OP strategy is more reliable than the SP strategy in general. However, on the power-grid network, the OP strategy is more resistant against cascading failures than the EP and SP strategies.     

基于局部路由策略的复杂网络拥塞控制

提出一种复杂网络上的局部路由策略,算法采用节点收缩法评估节点的重要度,发送节点根据邻居节点的重要度及网络的状态自适应地调整向邻居节点转发数据包的概率.在网络处于自由流通状态时充分发挥关键节点的优势,保证数据包快速到达目的地;在网络处于即将拥塞时分散业务,根据节点重要度准确识别网络中的关键节点,通过有效分流予以保护.仿真结果表明:在网络处于自由流通状态时,该局部路由策略能充分发挥网络中关键节点的枢纽作用,保持较低的传输时延;在网络部分关键节点出现拥塞时,该局部路由策略能有效避开拥挤严重的节点,将数据包均匀地分布在各个节点上,有效抑制网络拥塞,提高网络的容量.     

Robustness analysis of network controllability

Structural controllability, which is an interesting property of complex networks, attracts many researchers from various fields. The maximum matching algorithm was recently applied to explore the minimum number of driver nodes, where control signals are injected, for controlling the whole network. Here we study the controllability of directed Erdös–Rényi and scale-free networks under attacks and cascading failures. Results show that degree-based attacks are more efficient than random attacks on network structural controllability. Cascade failures also do great harm to network controllability even if they are triggered by a local node failure.     

Cascading failures of overload behaviors using a new coupled network model between edges

With the development of network science,the coupling between networks has become the focus of complex network research.However,previous studies mainly focused on the coupling between nodes,while ignored the coupling between edges.We propose a novel cascading failure model of two-layer networks.The model considers the different loads and capacities of edges,as well as the elastic and coupling relationship between edges.In addition,a more flexible load-capacity strategy is adopted to verify the model.The simulation results show that the model is feasible.Different networks have different behaviors for the same parameters.By changing the load parameters,capacity parameters,overload parameters,and distribution parameters reasonably,the robustness of the model can be significantly improved.     

IKN-CF: An Approach to Identify Key Nodes in Inter-Domain Routing Systems Based on Cascading Failures

Inter-domain routing systems is an important complex network in the Internet. Research on the vulnerability of inter-domain routing network nodes is of great support to the stable operation of the Internet. For the problem of node vulnerability, we proposed a method for identifying key nodes in inter-domain routing systems based on cascading failures (IKN-CF). Firstly, we analyzed the topology of inter-domain routing network and proposed an optimal valid path discovery algorithm considering business relationships. Then, the reason and propagation mechanism of cascading failure in the inter-domain routing network were analyzed, and we proposed two cascading indicators, which can approximate the impact of node failure on the network. After that, we established a key node identification model based on improved entropy weight TOPSIS (EWT), and the key node sequence in the network can be obtained through EWT calculation. We compared the existing three methods in two real inter-domain routing networks. The results indicate that the ranking results of IKN-CF are high accuracy, strong stability, and wide applicability. The accuracy of the top 100 nodes of the ranking result can reach 83.6%, which is at least 12.8% higher than the average accuracy of the existing three methods.     

A robust matching model of capacity to defense cascading failure on complex networks

How to control the cascading failure has become a hot topic in recent years. In this paper, we propose a new matching model of capacity by developing a profit function to defense cascading failures on artificially created scale-free networks and the real network structure of the North American power grid. Results show that our matching model can enhance the network robustness efficiently, which is particularly important for the design of networks to deduce the damage triggered by the cascading failures.