相依网络上基于相连边的择优恢复算法

如何有效地应对和控制故障在相依网络上的级联扩散避免系统发生结构性破碎,对于相依网络抗毁性研究具有十分重要的理论价值和现实意义.最新的研究提出一种基于相依网络的恢复模型,该模型的基本思想是通过定义共同边界节点,在每轮恢复阶段找出符合条件的共同边界节点并以一定比例实施恢复.当前的做法是按照随机概率进行选择.这种方法虽然简单直观,却没有考虑现实世界中资源成本的有限性和择优恢复的必然性.为此,针对相依网络的恢复模型,本文利用共同边界节点在极大连通网络内外的连接边数计算边界节点的重要性,提出一种基于相连边的择优恢复算法(preferential recovery based on connectivity link,PRCL)算法.利用渗流理论的随机故障模型,通过ER随机网络和无标度网络构建的不同结构相依网络上的级联仿真结果表明,相比随机方法和度数优先以及局域影响力优先的恢复算法,PRCL算法具备恢复能力强、起效时间早且迭代步数少的优势,能够更有效、更及时地遏制故障在网络间的级联扩散,极大地提高了相依网络遭受随机故障时的恢复能力.     

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

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

增长速度对合作网络参与者节点度分布的影响

采用率方程对合作网络自组织演化模型进行解析,得到参与者节点度分布服从Yule-Simon分布,这种分布可以用漂移幂律分布近似.分析参与者节点增长速度与参与者节点度分布之间的关系,发现随节点增长速度加快,参与者节点度分布远离幂律,表明节点增长速度是除优先连接之外的另一个影响合作网络拓扑性质的重要因素.通过对城市公交网络和科研合作网络的实证研究,验证了度分布解析结果的正确性.结合实证研究,探讨了合作网络中参与者节点增长速度的形成机制及其实际意义.     

基于电力网络的级联故障模型

以电力系统的停电事故为例,提出一种节点具有能量耗散和扩容行为的级联故障模型,并分别在二维规则网络和无标度网络上对该系统的演化过程进行计算机模拟.结果表明,在两种不同结构的网络中系统的演化过程都出现了自组织临界现象,说明网络中节点能量的耗散及容量的扩充是导致电力系统出现自组织临界现象的重要因素.此外,还发现无标度网络中的最大级联故障规模要远大于二维规则网络中的级联故障规模.     

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

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

利用节点效率评估复杂网络功能鲁棒性

为了克服现有复杂网络鲁棒性研究模型只考虑节点失效的局部影响性和网络拓扑鲁棒性的缺陷, 提出了一种利用节点效率来评估复杂网络功能鲁棒性的方法. 该方法综合考虑节点失效的全局影响性, 利用网络中节点的效率来定义各节点的负载、极限负载和失效模型, 通过打击后网络中最终失效节点的比例来衡量网络的功能鲁棒性, 并给出了其评估优化算法. 实验分析表明该方法对考虑节点负载的复杂网络功能鲁棒性的评定可行有效, 对于大型复杂网络可以获得理想的计算能力.     

异质弱相依网络鲁棒性研究

传统研究认为网络间相依边的引入使网络鲁棒性大幅降低,但现实相依网络的鲁棒性往往优于理论结果.通过观察现实相依网络的级联失效过程,发现节点不会因相依节点失效而损失所有连接边,且由于网络节点的异质性,每个节点的连接边失效概率也不尽相同.针对此现象,提出一种异质弱相依网络模型,与传统网络逾渗模型不同,本文认为两个弱相依节点的其中一个失效后,另一个节点的连接边以概率g失效而不是全部失效,并且不同节点连接边失效概率g会因节点的异质性而不同.通过理论分析给出模型基于生成函数的逾渗方程,求解出任意随机分布异质对称弱相依网络的连续相变点.仿真结果表明方程的理论解与随机网络逾渗模拟值相符合,网络鲁棒性随着弱相依关系异质程度的增大而提高.     

基于在线社交网络的信息传播模型

本文构造了一个基于在线社交网络的信息传播模型.该模型考虑了节点度和传播机理的影响,结合复杂网络和传染病动力学理论,进一步建立了动力学演化方程组.该方程组刻画了不同类型节点随着时间的演化关系,反映了传播动力学过程受到网络拓扑结构和传播机理的影响.本文模拟了在线社交网络中的信息传播过程,并分析了不同类型节点在网络中的行为规律.仿真结果表明:由于在线社交网络的高度连通性,信息在网络中传播的门槛几乎为零;初始传播节点的度越大,信息越容易在网络中迅速传播;中心节点具有较大的社会影响力;具有不同度数的节点在网络中的变 关键词： 在线社交网络 信息传播 微分方程 传染病动力学     

基于有限资源提升网络可生存性的拓扑重构方法

给定网络拓扑结构和有限添加边资源,如何优化配置添加边使重构后的网络拓扑结构具有最优可生存性是非常有价值的研究问题.本文首先明确网络可生存性的量化评估指标,以移除节点后网络结构的鲁棒性和有效性为优化目标,提出网络拓扑重构优化问题的建模与分析方法.同时在给定资源代价的约束下,为实现添加边资源配置效率的最大化,提出优先配置节点加强保护圈的启发式算法.仿真实验表明,该算法在有限资源约束的随机局部故障和选择性攻击环境中,能兼顾改善网络鲁棒性和传输效率,有效提升网络结构的可生存性.     

无线传感器网络中无标度拓扑的动态容错性分析

增强网络的动态容错性对于抵御级联失效具有重要的现实意义.根据无线传感器网络无标度拓扑中节点可变负载和恒定容量的特点建立级联失效模型,在随机节点失效下研究负载参数和拓扑参数对其级联失效容错性的影响规律,解析推导出该网络大规模级联失效的承载极限,同时模拟结果发现该网络的级联失效容错性与其度分布系数和幂指数正相关.这为从参数优化角度抵御随机节点失效下无线传感器网络无标度拓扑级联失效危害提供了依据.     

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.     

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 failures in congested complex networks with feedback

In this article, we investigate cascading failures in complex networks by introducing a feedback. To characterize the effect of the feedback, we define a procedure that involves a self-organization of trip distribution during the process of cascading failures. For this purpose, user equilibrium with variable demand is used as an alternative way to determine the traffic flow pattern throughout the network. Under the attack, cost function dynamics are introduced to discuss edge overload in complex networks, where each edge is assigned a finite capacity (controlled by parameter α). We find that scale-free networks without considering the effect of the feedback are expected to be very sensitive to α as compared with random networks, while this situation is largely improved after introducing the feedback.     

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.     

负荷作用下相依网络中的级联故障

研究负荷作用下相依网络中的级联故障具有重要的现实意义, 可为提高相依网络的鲁棒性提供参考. 构建了双层相依网络级联故障模型, 主要研究了外部度和内部度对负荷贡献比、耦合因素、层内度-度相关性对相依网络级联故障的影响. 研究表明, 当外部度和内部度对负荷贡献比达到一定值时, 相依网络抵抗级联故障的鲁棒性最强. 而耦合因素的影响是多方面的, 为了达到较高鲁棒性, 建议采用异配耦合方式和尽可能大的平均外部度, 并尽量使外部度保持均匀分布. 另外, 与不考虑负荷作用时相反, 当表征层内度-度相关性的相关系数越大时, 其抵抗级联故障的能力越强.     

Tolerance of edge cascades with coupled map lattices methods

This paper studies the cascading failure on random networks and scale-free networks by introducing the tolerance parameter of edge based on the coupled map lattices methods. The whole work focuses on investigating some indices including the number of failed edges, dynamic edge tolerance capacity and the perturbation of edge. In general, it assumes that the perturbation is attributed to the normal distribution in adopted simulations. By investigating the effectiveness of edge tolerance in scale-free and random networks, it finds that the larger tolerance parameter λ can more efficiently delay the cascading failure process for scale-free networks than random networks. These results indicate that the cascading failure process can be effectively controlled by increasing the tolerance parameter λ. Moreover, the simulations also show that, larger variance of perturbation can easily trigger the cascading failures than the smaller one. This study may be useful for evaluating efficiency of whole traffic systems, and for alleviating cascading failure in such systems.     

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

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

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

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

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.