基于袭击的复杂网络上的全局相继故障

针对复杂网络遭遇随机故障和蓄意攻击引发的相继故障问题,采用一种新的节点初始负荷的定义方法,并基于崩溃节点负荷的局域择优重新分配的原则,提出一个带有可调参数的相继故障模型.通过度量网络鲁棒性的一个新的指标,对比了两种袭击策略下复杂网络上的全局相继故障现象,并探讨不同袭击策略的有效性.数值模拟表明,在模型中可调参数的一定取值内,袭击网络中度最小的节点比袭击网络中度最大的节点更易于导致相继故障.此外,对数值模拟结果给出理论的分析解释.     

面向相继故障的复杂网络上袭击策略研究

针对复杂网络遭遇随机故障和蓄意攻击引发的相继故障问题,采用网络中节点j上的初始负荷为Lj=βkjα(这里kj表示为节点j的度,α和β是可调参数),并基于崩溃节点负荷局域择优重新分配的原则,提出了一个带有可调参数的相继故障模型.通过度量网络鲁棒性的一个新的指标,即:关键阈值Tc,对比了两种袭击策略下网络上的全局相继故障现象.数值模拟得到了一些有趣而又违背直觉的结论:一方面,当模型中的可调参数α<1时,袭击网络中度最小的节点比袭击度最大的节点更易导致相继故障;而另一方面,当α=1时,两种袭击对网络的破坏几乎是相同的.此外,数值模拟结果也得到了理论解析的验证.     

基于节点局域特征的复杂网络上相继故障模型

为了更好地探讨复杂网络抵制相继故障的全局鲁棒性,基于节点的局域特征,并紧紧围绕负荷这一影响连锁故障发生和传播最重要的物理量以及节点崩溃后的动力学过程,提出了带有可调参数的相继故障模型.数值模拟获得了复杂网络抵制相继故障的鲁棒性与模型中参数的关系以及网络的平均度对相继故障的影响.此外,基于不同网络图的分析以及理论解析的推导,数值模拟结论也得到了验证.     

耦合网络边相继故障模型研究

针对耦合网络上频发的相继故障问题,通过分析边级联故障蔓延的动力学演化机制,构建耦合网络上边相继故障模型。以提高耦合网络整体抵制相继故障能力为出发点,依据不同度量指标,多角度分析具有不同耦合模式的耦合网络鲁棒性与模型参数之间的关联性,研究耦合网络间耦合模式和网络基本模型等因素对相继故障的影响,探讨耦合网络边相继故障模型的整体保护策略。研究结果表明,同配连接模式能够增强耦合网络抵制级联故障的鲁棒性;相互依赖的两个耦合网络之间拓扑结构越相似,网络抵制相继故障的鲁棒性越强;耦合网络鲁棒性与网络平均度正相关;适当的增加耦合网络间对称边数量,能够有效提高网络的鲁棒性。最后,应用边相继故障模型在耦合电力网络上进行实例分析。     

关联供应链网络级联失效机理及鲁棒性研究

为了分析复杂关联供应链网络在遭遇干扰事件时的鲁棒性,研究关联网络层内和层间级联失效机理.通过随机规则生成供应链无向信息层网络和有向物理层网络,描述并分析由α、β、σ等参数表征的节点负荷、容量等网络结构特性.针对存在边流量约束的情况,提出相应的失效负荷分流策略;通过构建极大簇函数,判断关联供应链网络中经分流策略后仍具运作功能的有效节点,并依据供应链信息层网络和物理层网络间一对一匹配的关联关系,构建时变失效迭代状态方程,从而有效描述关联网络间的动态失效传递.最后,在不同参数控制下,对初始单个节点故障和多个节点故障两种情况下的关联供应链网络综合鲁棒性进行数值仿真分析.按节点度从大到小、从小到大、随机3种方式去除多个节点,结果表明在β=0.5, 1, 1.5, 2 4种参数下,按度从小到大方式去除多节点,其引发的关联网络级联失效规模较之其它两种方式大;同时发现关联供应链网络在多节点去除情况下,其级联失效较之单层网络具有明显的一级相变特性,即少量的节点移除就会导致整个关联供应链网络崩溃.     

基于组织-任务网络的研发项目工期风险分析——以组织失效为风险因素

在项目工期风险管理领域,大多基于活动工期的不确定性进行研究,对由组织失效引起的工期风险问题较少关注。在对研发项目组织网络和任务网络分析的基础上,提出了研发项目的组织-任务网络模型。借鉴相继故障理论中的耦合映象格子,构建了以组织失效为风险因素的研发项目工期风险分析模型,并对该理论模型进行了数值仿真。结果表明,施加给组织节点的外部扰动达到某一数值即关键扰动阈值时可显著导致项目工期延误,该关键扰动阈值与组织间的耦合度呈负相关,与组织网络的平均度呈正相关,度大袭击比随机袭击和度小袭击更易于导致项目工期风险的发生,且造成工期延误的程度随着组织间耦合度的减小而愈加显著。研究结论为网络化背景下研发项目工期风险管理提供了新的视角。     

考虑自适应行为的研发网络风险传播模型构建及仿真

构建风险视域下研发网络企业自适应行为规则，基于SIS模型构建研发网络风险传播模型，运用数值仿真的方法通过改变模型参数探索在考虑自适应行为的情况下研发网络的风险传播规律，研究结果表明：（1）C1策略增强了网络的层次性和社团强度，一定程度上抑制了研发网络中风险的传播；C2策略下节点之间新连接的建立更多是基于临近性的考量，容易陷入路径依赖和能力陷阱；（2）研发网络企业的自适应行为会导致社团强度的涨落，平均路径长度的下降以及平均聚类系数的增长充分体现出C1策略的有效性。（3）C1策略下，断边概率p与I*之间呈现"U"型相关关系；在C2策略下随着断边概率p的增长I*逐渐降低。（4）在C1策略和C2策略下，随着参数ζ的增长I*也随之增长，可知组织依赖水平是研发网络风险传播控制中需要重点关注的因素。本文揭示了在考虑自适应行为的情况下研发网络的风险传播规律，为网络化运作背景下研发网络治理提供理论依据。     

电信社群网络用户行为特征及演化分析

通过某地移动客户的通话数据构建电信社群网络,并对其网络结构进行分析,发现电信社群网络并不满足小世界特征,而且该网络的演化是以边生长为主导。基于该结构特征,构建电信社群网的演化模型,发现网络非均匀性与节点的朋友圈数目、连接概率和新增节点边数有关。其研究结论对新运营商通过营销策略的制定,推动电信社群网络快速向小世界网络演化具有积极的现实意义。     

赋权网络中的弱化免疫研究

随着复杂网络在社会经济管理领域应用研究的发展,信息扩散或谣言传播及相应的传播控制也得到了人们的广泛关注.本文定义了边赋权网络中的控制行为--弱化免疫,即通过降低免疫节点所关联的边的权值,同时保持免疫后网络节点间的连接畅通,可使整个网络保持一定效率下的正常运行的免疫策略;其次,建立基于病毒传播SI模型上的弱化免疫模型,给出加权网络中弱化免疫下的谣言密度演化规律. 最后研究加权网络中基于弱化免疫下的目标免疫策略,并分析弱化免疫网络同步性能, 对加权网络中谣言传播和免疫策略等相关参数进行数值模拟,表明理论模型的可行性以及免疫策略的合理性.     

随机网络瓶颈容量扩张相关机会规划模型

文章研究的问题为,在不确定环境中,怎样去增加网络中一组边的容量到一个指定的容量,以至于网络瓶颈扩张的费用不超过给定的总费用上限的概率尽可能的大.本文假定每一条边的单位扩张费用Wi是一个随机的变量,它服从一定的概率分布.带有随机单位扩张费用W的网络瓶颈容量扩张问题可以根据一些规则,列出它的相关机会规划模型的通用表达式.随后,本文将网络瓶颈容量算法、随机模拟方法和遗传算法合成在一起,设计出该问题的混合智能通用算法.最后,给出数值算例.     

On edge orienting methods for graph coloring

We consider the problem of orienting the edges of a graph so that the length of a longest path in the resulting digraph is minimum. As shown by Gallai, Roy and Vitaver, this edge orienting problem is equivalent to finding the chromatic number of a graph. We study various properties of edge orienting methods in the context of local search for graph coloring. We then exploit these properties to derive four tabu search algorithms, each based on a different neighborhood. We compare these algorithms numerically to determine which are the most promising and to give potential research directions.     

Efficient algorithms for shared backup allocation in networks with partial information

We study efficient algorithms for establishing reliable connections with bandwidth guarantees in communication networks. In the normal mode of operation, each connection uses a primary path to deliver packets from the source to the destination. To ensure continuous operation in the event of an edge failure, each connection uses a set of backup bridges, each bridge protecting a portion of the primary path. To meet the bandwidth requirement of the connection, a certain amount of bandwidth must be allocated the edges of the primary path, as well as on the backup edges. In this paper, we focus on minimizing the amount of required backup allocation by sharing backup bandwidth among different connections. We consider efficient sharing schemes that require only partial information about the current state of the network. Specifically, the only information available for each edge is the total amount of primary allocation and the cost of allocating backup bandwidth on this edge. We consider the problem of finding a minimum cost backup allocation together with a set of bridges for a given primary path. We prove that this problem is NP-hard and present an approximation algorithm whose performance is within of the optimum, where n is the number of edges in the primary path. We also consider the problem of finding both a primary path and backup allocation of minimal total cost. A preliminary version of this paper appears in the Proceedings of 13th Annual European Symposium on Algorithms - ESA 2005, Mallorca, Spain. J. (Seffi) Naor: This research is supported in part by a foundational and strategical research grant from the Israeli Ministry of Science, and by a US-Israel BSF Grant 2002276.     

Monotonicity of strong searching on digraphs

Given a digraph, suppose that some intruders hide on vertices or along edges of the digraph. We want to find the minimum number of searchers required to capture all the intruders hiding in the digraph. In this paper, we propose and study two digraph searching models: strong searching and mixed strong searching. In these two search models, searchers can move either from tail to head or from head to tail when they slide along edges, but intruders must follow the edge directions when they move along edges. We prove the monotonicity of each model respectively, and show that both searching problems are NP-complete. The research of B. Yang was supported in part by NSERC and MITACS.     

Fast searching games on graphs

Given a graph, suppose that intruders hide on vertices or along edges of the graph. The fast searching problem is to find the minimum number of searchers required to capture all the intruders satisfying the constraint that every edge is traversed exactly once and searchers are not allowed to jump. In this paper, we prove lower bounds on the fast search number. We present a linear time algorithm to compute the fast search number of Halin graphs and their extensions. We present a quadratic time algorithm to compute the fast search number of cubic graphs.     

Island refuges for surviving nuclear winter and other abrupt sunlight-reducing catastrophes

Some island nations in the Southern Hemisphere might survive a severe sun-reducing catastrophe such as nuclear winter and be well placed to help reboot-collapsed human civilization. Such islands must be resilient to the cascading effects abrupt sunlight reduction scenarios (ASRS) would impose beyond the impacts on agricultural systems. We aimed to identify island nations whose societies are most likely to survive nuclear winter or other ASRS. We also aimed to conduct a case study of one island nation to consider how it might enhance its resilience and therefore its chance of aiding a global reboot of complex technological society. We performed a threshold analysis on food self-sufficiency under severe nuclear winter conditions to identify islands. We then profiled each island across global macroindices representing resilience factors reported in the literature. We undertook a case study of the island nation of New Zealand. The island nations of Australia, New Zealand, Iceland, the Solomon Islands, and Vanuatu appear most resilient to ASRS. However, our case-study island nation of New Zealand is threatened in scenarios of no/low trade, has precarious aspects of its energy supply, and shortcomings in manufacturing of essential components. Therefore, inadequate preparations and critical failures in these systems could see rapid societal breakdown. Despite some islands’ favorable baseline conditions and apparent food security even in a severe ASRS, cascading impacts through other socioecological systems threaten complex functioning. We identified specific resilience measures, many with cobenefits, which may protect island nodes of sustained complexity in ASRS.     

Optimization of Cascade‐Resilient Electrical Infrastructures and its Validation by Power Flow Modeling

Large‐scale outages on real‐world critical infrastructures, although infrequent, are increasingly disastrous to our society. In this article, we are primarily concerned with power transmission networks and we consider the problem of allocation of generation to distributors by rewiring links under the objectives of maximizing network resilience to cascading failure and minimizing investment costs. The combinatorial multiobjective optimization is carried out by a nondominated sorting binary differential evolution (NSBDE) algorithm. For each generators–distributors connection pattern considered in the NSBDE search, a computationally cheap, topological model of failure cascading in a complex network (named the Motter‐Lai [ML] model) is used to simulate and quantify network resilience to cascading failures initiated by targeted attacks. The results on the 400 kV French power transmission network case study show that the proposed method allows us to identify optimal patterns of generators–distributors connection that improve cascading resilience at an acceptable cost. To verify the realistic character of the results obtained by the NSBDE with the embedded ML topological model, a more realistic but also more computationally expensive model of cascading failures is adopted, based on optimal power flow (namely, the ORNL‐Pserc‐Alaska) model). The consistent results between the two models provide impetus for the use of topological, complex network theory models for analysis and optimization of large infrastructures against cascading failure with the advantages of simplicity, scalability, and low computational cost.     

基于复杂网络的金融传染风险模型研究

随着金融创新向更广和更深层面发展,金融体系中的传染风险和系统性风险越来越大,对此类风险进行准确度量是有效宏观审慎管理的重要内容。本文基于复杂网络理论,采用模拟方法对金融传染风险模型进行系统研究。首先,借鉴复杂网络的Watts级联动力学理论,构建了基于随机网络的金融传染模型,其较大的网络连通度水平不仅为传染提供更多的传播渠道,而且抵消了风险共享的能力。其次,引入Gleeson和Cahalane(2007)的分析框架,探讨了计算预期违约银行节点规模的解析模型,并对Watts模型中各种参数对系统风险的影响效应进行测度。最终,形成一个包括网络模拟方法、模型解析结论,以及网络统计分析方法等较全面的计算算法工具集合。