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

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

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

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

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

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

基于度的正/负相关相依网络模型及其鲁棒性研究

利用典型的Barabási-Albert无标度网络构建了基于度的正/负相关相依网络模型, 该模型考虑子网络间的相依方式及相依程度, 主要定义了两个参数F和K, F表示相依节点比例, K表示相依冗余度. 在随机攻击及基于度的蓄意攻击模式下, 针对网络的级联失效问题, 研究了不同的F值和K值对该相依网络模型鲁棒性的影响, 与随机相依网络模型进行了对比研究. 仿真结果表明:无论是随机相依或是基于度的正/负相关相依网络, 其鲁棒性都是随着F的增大而减弱, 随着K的增大而增强; 在随机攻击下, 全相依模式(F=1)时, 基于度正相关相依网络模型鲁棒性最优, 部分相依模式 (F =0.2, 0.5, 0.8)时, 基于度的负相关相依网络模型则表现出更好的鲁棒性. 而在基于度的蓄意攻击下, 无论F为何值, 基于度的正相关相依网络模型表现出弱鲁棒性.     

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

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

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

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

相依网络的条件依赖群逾渗

相依网络鲁棒性研究多集中于满足无反馈条件的一对一依赖,但现实网络节点往往依赖于多节点构成的依赖群,即使群内部分节点失效也不会导致依赖节点失效.针对此现象提出了一种相依网络的条件依赖群逾渗模型,该模型允许依赖群内节点失效比例不超过容忍度γ时,依赖节点仍可正常工作.通过理论分析给出了基于生成函数方法的模型巨分量方程,仿真结果表明方程理论解与相依网络模拟逾渗值相吻合,增大γ值和依赖群规模可提高相依网络鲁棒性.本文模型有助于更好地理解现实网络逾渗现象,对如何增强相依网络鲁棒性有一定指导作用.     

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

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

光突发交换网络中基于LDPC码的丢包恢复机制(英文)

基于前向纠错编码理论,在光突发交换网络中提出一种丢包恢复机制来降低突发丢失率.构造了一种能对突发包进行在线编解码的低密度奇偶校验码.入口边缘节点通过对信息突发包进行在线编码产生冗余突发包,出口边缘节点利用译码算法从接收到的突发包中恢复出丢失的突发数据.另外,为信息突发包增加一个额外的偏置时间以减少冗余突发与信息突发竞争信道资源.通过OPNET仿真软件对不同丢包恢复机制的性能进行仿真,结果表明,与奇偶校验码提出的丢包恢复机制相比,具有更低的突发丢失率和良好的丢包恢复能力.     

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

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

A Simple Asymmetric Evolving Random Network

We introduce a new oriented evolving graph model inspired by biological networks. A node is added at each time step and is connected to the rest of the graph by random oriented edges emerging from older nodes. This leads to a statistical asymmetry between incoming and outgoing edges. We show that the model exhibits a percolation transition and discuss its universality. Below the threshold, the distribution of component sizes decreases algebraically with a continuously varying exponent depending on the average connectivity. We prove that the transition is of infinite order by deriving the exact asymptotic formula for the size of the giant component close to the threshold. We also present a thorough analysis of aging properties. We compute local-in-time profiles for the components of finite size and for the giant component, showing in particular that the giant component is always dense among the oldest nodes but invades only an exponentially small fraction of the young nodes close to the threshold.     

A Resiliency-Connectivity metric in wireless sensor networks with key predistribution schemes and node compromise attacks

Applications for wireless sensor networks require widespread, highly reliable communications even in the face of adversarial influences. Maintaining connectivity and secure communications between entities are vital networking properties towards ensuring the successful and accurate completion of desired sensing tasks. We examine the required communication range for nodes in a wireless sensor network with respect to several parameters. Network properties such as key predistribution schemes and node compromise attacks are modelled with several network parameters and studied in terms of how they influence global network connectivity. These networks are physically vulnerable to malicious behavior by way of node compromise attacks that may affect global connectivity. We introduce a metric that determines the resilience of a network employing a key predistribution scheme with respect to node compromise attacks. In this work,we provide the first study of global network connectivity and its relationship to node compromise attacks. Existing work considers the relationship between the probability of node compromise and the probability of link compromise and the relationship of the probability of secure link establishment and overall network connectivity for the Erdős network model. Here, we present novel work which combines these two relationships to study the relationship between node compromise attacks and global network connectivity. Our analysis is performed with regard to large-scale networks; however, we provide simulation results for both large-scale and small-scale networks. First, we derive a single expression to determine the required communication radius for wireless sensor networks to include the effects of key predistribution schemes. From this, we derive an expression for determining required communication range after an adversary has compromised a fraction of the nodes in the network. The required communication range represents the resource usage of nodes in a network to cope with key distribution schemes and node compromise attacks. We introduce the Resiliency-Connectivity metric, which measures the resilience of a network in expending its resources to provide global connectivity in adverse situations.     

Complexity in human transportation networks: a comparative analysis of worldwide air transportation and global cargo-ship movements

We present a comparative network-theoretic analysis of the two largest global transportation networks: the worldwide air-transportation network (WAN) and the global cargo-ship network (GCSN). We show that both networks exhibit surprising statistical similarities despite significant differences in topology and connectivity. Both networks exhibit a discontinuity in node and link betweenness distributions which implies that these networks naturally segregate into two different classes of nodes and links. We introduce a technique based on effective distances, shortest paths and shortest path trees for strongly weighted symmetric networks and show that in a shortest path tree representation the most significant features of both networks can be readily seen. We show that effective shortest path distance, unlike conventional geographic distance measures, strongly correlates with node centrality measures. Using the new technique we show that network resilience can be investigated more precisely than with contemporary techniques that are based on percolation theory. We extract a functional relationship between node characteristics and resilience to network disruption. Finally we discuss the results, their implications and conclude that dynamic processes that evolve on both networks are expected to share universal dynamic characteristics.     

Bicomponents and the robustness of networks to failure

We study bicomponents in networks, sets of nodes such that each pair in the set is connected by at least two independent paths, so that the failure of no single node in the network can cause them to become disconnected. We show that standard network models predict there to be essentially no small bicomponents in most networks, but there may be a giant bicomponent, whose presence coincides with the presence of the ordinary giant component, and we find that real networks seem by and large to follow this pattern, although there are some interesting exceptions. We also study the size of the giant bicomponent as nodes in the network fail and find in some cases that our networks are quite robust to failure, with large bicomponents persisting until almost all vertices have been removed.     

Self-organization of balanced nodes in random networks with transportation bandwidths

We apply statistical physics to study the task of resource allocation in random networks with limited bandwidths along the transportation links. The mean-field approach is applicable when the connectivity is sufficiently high. It allows us to derive the resource shortage of a node as a well-defined function of its capacity. For networks with uniformly high connectivity, an efficient profile of the allocated resources is obtained, which exhibits features similar to the Maxwell construction. These results have good agreements with simulations, where nodes self-organize to balance their shortages, forming extensive clusters of nodes interconnected by unsaturated links. The deviations from the mean-field analyses show that nodes are likely to be rich in the locality of gifted neighbors. In scale-free networks, hubs make sacrifice for enhanced balancing of nodes with low connectivity.     

Number and length of attractors in a critical Kauffman model with connectivity one

The Kauffman model describes a system of randomly connected nodes with dynamics based on Boolean update functions. Though it is a simple model, it exhibits very complex behavior for "critical" parameter values at the boundary between a frozen and a disordered phase, and is therefore used for studies of real network problems. We prove here that the mean number and mean length of attractors in critical random Boolean networks with connectivity one both increase faster than any power law with network size. We derive these results by generating the networks through a growth process and by calculating lower bounds.     

Continuum Percolation with Unreliable and Spread-Out Connections

We derive percolation results in the continuum plane that lead to what appears to be a general tendency of many stochastic network models. Namely, when the selection mechanism according to which nodes are connected to each other, is sufficiently spread out, then a lower density of nodes, or on average fewer connections per node, are sufficient to obtain an unbounded connected component. We look at two different transformations that spread-out connections and decrease the critical percolation density while preserving the average node degree. Our results indicate that real networks can exploit the presence of spread-out and unreliable connections to achieve connectivity more easily, provided they can maintain the average number of functioningconnections per node.     

Growing random networks with fitness

Three models of growing random networks with fitness-dependent growth rates are analysed using the rate equations for the distribution of their connectivities. In the first model (A), a network is built by connecting incoming nodes to nodes of connectivity k and random additive fitness η, with rate (k−1)+η. For η>0 we find the connectivity distribution is power law with exponent γ=〈η〉+2. In the second model (B), the network is built by connecting nodes to nodes of connectivity k, random additive fitness η and random multiplicative fitness ζ with rate ζ(k−1)+η. This model also has a power law connectivity distribution, but with an exponent which depends on the multiplicative fitness at each node. In the third model (C), a directed graph is considered and is built by the addition of nodes and the creation of links. A node with fitness (α,β), i incoming links and j outgoing links gains a new incoming link with rate α(i+1), and a new outgoing link with rate β(j+1). The distributions of the number of incoming and outgoing links both scale as power laws, with inverse logarithmic corrections.