具有弱依赖组的复杂网络上的级联失效

复杂系统的功能通过节点之间的连接而维持,部分节点的失效会对系统的连通性造成破坏而影响整体的功能.除此之外,部分节点还会通过隐含依赖性而形成“依赖组”,其中一个节点的失效会对依赖组中其余节点造成损害.本文研究了“依赖组”的平均规模,规模分布和节点之间的依赖强度对网络级联失效和鲁棒性的影响.通过数值模拟和理论分析发现,网络的级联失效在尺度层次上可以分为“组内级联”和“组间级联”两个过程.在组内级联过程中,一个节点的失效会通过节点之间的依赖性对组内其他节点造成破坏,从而诱发更多节点的失效,进而产生更大的破坏力.在组间级联过程中,失效节点会引起网络发生破碎而导致组外节点脱离网络巨分支而失效,这就引起了失效节点的跨依赖组传播.在这两种失效过程的共同作用下,网络在级联失效过程中会表现出连续和不连续的两种渗流相变现象,这两种相变现象的发生与节点间的依赖强度、网络度分布以及依赖组规模分布有关.这意味着通过控制依赖组的特征,如依赖组中节点之间的依赖强度或依赖组规模分布,可以避免系统突然崩溃进而提高网络的鲁棒性.     

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

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

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

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

基于时滞耦合映像格子的多耦合边耦合网络级联抗毁性研究

现实中各网络之间的耦合促进了网络间的交流,但也带来了级联故障大范围传播的风险.考虑到故障的传播一般存在时滞,并且一个节点可能拥有不止一条耦合边的情况,本文构建了基于时滞耦合映像格子的多耦合边无标度耦合网络级联故障模型.研究表明,对于BA(Barabási-Albert)无标度耦合网络,存在一个阈值hT≈3,当耦合强度小于此阈值时,耦合越强抗毁性越弱;反之,耦合越强抗毁性反而越强.另外,研究发现时滞对耦合网络的影响不仅仅是延长了故障传播的时间,为采取防护措施争取了时间,而且也对最终故障规模产生了影响,具体地,当层内时滞τ1和层间时滞τ2可取任意值时,当两者成整数倍关系时其最终故障规模将更大.本文的研究可为构建高抗毁性的耦合网络或提高耦合网络的级联抗毁性提供参考.     

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

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

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

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

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

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

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

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

基于时间序列的网络失效模型

随着网络科学的发展,静态网络已不能清晰刻画网络的动态过程.在现实网络中,个体之间的交互随时间而快速演化.这种网络模式将时间与交互过程紧密联系,能够清晰刻画节点的动态过程.因此,如何更好地基于时间序列刻画网络行为变化是现有级联失效研究的重要问题.为了更好地研究该问题,本文提出一种基于时间序列的失效模型.通过随机攻击某时刻的节点,分析了时间、激活比例、连边数、连接概率4个参数对失效的影响并发现网络相变现象.同时为验证该模型的有效性与科学性,采用真实网络进行研究.实验表明,该模型兼顾时序以及传播动力学,具有较好的可行性,为解释现实动态网络的级联传播提供了参考.     

多层单向耦合星形网络的特征值谱及同步能力分析

随着复杂网络同步的进一步发展,对复杂网络的研究重点由单层网络转向更加接近实际网络的多层有向网络.本文分别严格推导出三层、多层的单向耦合星形网络的特征值谱,并分析了耦合强度、节点数、层数对网络同步能力的影响,重点分析了层数和层间中心节点之间的耦合强度对多层单向耦合星形网络同步能力的影响,得出了层数对多层网络同步能力的影响至关重要.当同步域无界时,网络的同步能力与耦合强度、层数有关,同步能力随其增大而增强;当同步域有界时,对于叶子节点向中心节点耦合的多层星形网络,当层内耦合强度较弱时,层内耦合强度的增大会使同步能力增强,而层间叶子节点之间的耦合强度、层数的增大反而会使同步能力减弱;当层间中心节点之间的耦合强度较弱时,层间中心节点之间的耦合强度、层数的增大会使同步能力增强,层内耦合强度、层间叶子节点之间的耦合强度的增大反而会使同步能力减弱.对于中心节点向叶子节点耦合的多层星形网络,层间叶子节点之间的耦合强度、层数的增大会使同步能力增强,层内耦合强度、节点数、层间中心节点之间的耦合强度的增大反而会使同步能力减弱.     

Cascading failure in multilayer networks with dynamic dependency groups

The cascading failure often occurs in real networks. It is significant to analyze the cascading failure in the complex network research. The dependency relation can change over time. Therefore, in this study, we investigate the cascading failure in multilayer networks with dynamic dependency groups. We construct a model considering the recovery mechanism.In our model, two effects between layers are defined. Under Effect 1, the dependent nodes in other layers will be disabled as long as one node does not belong to the largest connected component in one layer. Under Effect 2, the dependent nodes in other layers will recover when one node belongs to the largest connected component. The theoretical solution of the largest component is deduced and the simulation results verify our theoretical solution. In the simulation, we analyze the influence factors of the network robustness, including the fraction of dependent nodes and the group size, in our model. It shows that increasing the fraction of dependent nodes and the group size will enhance the network robustness under Effect 1. On the contrary, these will reduce the network robustness under Effect 2. Meanwhile, we find that the tightness of the network connection will affect the robustness of networks. Furthermore, setting the average degree of network as 8 is enough to keep the network robust.     

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

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

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.     

Cascading failure in Watts-Strogatz small-world networks

In this paper, we study the cascading failure in Watts-Strogatz small-world networks. We find that this network model has a heterogeneous betweenness distribution, although its degree distribution is homogeneous. Further study shows that this small-world network is robust to random attack but fragile to intentional attack, in the cascading failure scenario. With comparison to standard random graph and scale-free networks, our result indicates that the robust yet fragile property in the cascading failure scenario is mainly related to heterogeneous betweenness, rather than the network degree distribution. Thus, it suggests that we have to be very careful when we use terms such as homogeneous network and heterogeneous network, unless the distribution we refer to is specified.     

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

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

Mitigation strategies on scale-free networks against cascading failures

According to the dynamic characteristics of the cascading propagation, we introduce a mitigation mechanism and propose four mitigation methods on four types of nodes. By the normalized average avalanche size and a new measure, we demonstrate the efficiencies of the mitigation strategies on enhancing the robustness of scale-free networks against cascading failures and give the order of the effectiveness of the mitigation strategies. Surprisingly, we find that only adopting once mitigation mechanism on a small part of the overload nodes can dramatically improve the robustness of scale-free networks. In addition, we also show by numerical simulations that the optimal mitigation method strongly depends on the total capacities of all nodes in a network and the distribution of the load in the cascading model. Therefore, according to the protection strength for scale-free networks, by the distribution of the load and the protection price of networks, we can reasonably select how many nodes and which mitigation method to efficiently protect scale-free networks at the lower price. These findings may be very useful for avoiding various cascading-failure-induced disasters in the real world and for leading to insights into the mitigation of cascading failures.     

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.