复杂网络抗毁性测度研究综述

随着对复杂网络的定性特征与定量规律的深入探索,复杂网络的抗毁性测度研究已成为复杂性科学的研究热点之一。文章从抗毁性需求出发,给出了网络抗毁性的定义和抗毁性量化指标,并基于网络攻击策略详述了目前复杂网络抗毁性测度方法的研究进展。最后对复杂网络抗毁性测度研究存在的问题进行了总结,对未来的发展趋势作了展望。     

网络抗毁性测度研究

针对网络抗毁性测度问题,依据抗毁性三原则——阻挡、识别和恢复,提出了多维网络抗毁性测度提取方法,该方法综合运用了多种抗毁性分析技术,结合实际验证筛选,为提炼抗毁性测度提供了有效途径;提出了三层树状结构的网络抗毁性测度集,为抗毁性测度提供了可行的分类参考;最后,提出了抗毁性测度度量方法并给出了其形式化描述,实现不同类型抗毁性测度值的获取。分析表明,提出的网络抗毁性测度提取方法、测度集合和度量方法具有良好的一致性和可行性。     

基于社团划分的复杂网络级联抗毁攻击策略

为研究在社团划分基础上复杂网络的级联抗毁攻击策略,采用节点及其邻居节点介数定义初始负荷,这种定义方式综合考虑了节点的信息,采用局部择优分配策略处理故障节点负荷,研究了网络耦合强度,WS(Watts-Strogatz)小世界网络、BA(Barabási-Albert)无标度网络、ER(Erds-Rényi)随机网络、局域世界(WL)网络在社团划分攻击策略下抗毁性,以及不同攻击策略下具有重叠和非重叠社团结构网络的抗毁性。仿真结果表明,网络的耦合强度与抗毁性成负相关;不同类型网络在快速分裂算法识别社团前提下,攻击介数最大节点时网络抗毁性最弱;具有重叠社团结构的网络在集团渗流算法（CPM）识别后,采用攻击重叠部分介数最大节点的策略时网络抗毁性最弱。结论表明采用社团划分的攻击策略可以最大规模破坏网络。     

有向加权复杂网络抗毁性测度研究

为有效评估有向加权复杂网络的抗毁性能,考虑网络边的有向性和权重对复杂网络拓扑层抗毁性的影响,提出一种有向加权复杂网络抗毁性测度算法(IMADW)。IMADW利用最短调和距离度量节点之间以及整个网络节点对之间的连接紧密度,采用节点环路系数反映节点可选的路径数,由此得到网络拓扑层的全局抗毁性测度值。通过算法分析和实验仿真验证了该算法的准确性。     

基于复杂网络理论的中国航空网络抗毁性测度分析

运用复杂网络理论建立的网络抗毁性测度方法,对中国航空网络进行了抗毁性实证分析。对中国航空网络连通性影响最大的机场是乌鲁木齐、昆明、西安等区域枢纽机场;针对度值进行选择性蓄意攻击,攻击机场数量达到5%时,就能使中国航空网络效率下降至50%左右;根据关键机场遭受蓄意攻击后,航空流量的重新流向对其他机场产生的流量压力来看,北京、上海及广州三个城市的机场对保持中国航空网络的稳定起着决定性的作用。     

复杂网络二维抗毁性测度指标及评价算法

为衡量网络结构破坏和动态流变化对网络性能的影响,构造一个具有二维特征的抗毁性测度综合效率指标,利用基于度和介数的节点删除法模拟蓄意攻击,将网络遭遇攻击后动态流的总流动成本的倒数作为网络的综合效率值以评价网络遭遇攻击后的破坏程度,并设计网络抗毁性能评价算法。以某快递企业的配送网络为例进行验证,结果表明对于具有动态流的现实网络,该指标能有效地揭示其破坏 状况。     

复杂网络抗毁性研究综述

复杂网络的抗毁性直接关系到复杂网络的安全性和可靠性,是近年来复杂网络研究的热点分支。从抗毁性测度、抗毁性分析以及抗毁性优化三方面详细综述了复杂网络抗毁性的研究进展,并对该研究领域存在的问题和未来的发展趋势进行了总结和展望。     

基于复杂网络的车载自组织网络抗毁性分析

针对车载自组织网络（VANET）的抗毁性问题,分析了其在随意攻击和蓄意攻击下网络的抗毁性特征。首先,提出以最大连通度、连通分支平均规模、临界点移除比例及网络效率为评价指标的VANET拓扑抗毁性参数;然后,基于带有车辆换道功能的智能驾驶员模型,应用VanetMobisim仿真软件建立VANET;最后,通过仿真实验分析了网络节点数、通信半径以及攻击模式对VANET抗毁性的影响。实验结果表明由于车辆节点度分布的不均匀性,VANET对随意攻击具有较强的抗毁性,而在蓄意攻击下显得比较脆弱;基于节点介数的蓄意攻击对网络的破坏更快、更强。这些规律为优化VANET拓扑控制、网络协议开发和网络管理提供新的指导。     

基于复杂网络理论的Internet抗毁性研究

针对Internet这一典型的复杂网络,依据TCP拥塞控制协议能重新调整数据流流速的特性,提出了一种新的抗毁性测度方法,并在流速可变的通信模型下对Internet进行了抗毁性研究,仿真结果表明Internet仍然具有鲁棒且脆弱性;然后分析了Internet在不完全信息下和基于局部网络拓扑信息的分布式攻击下的抗毁性,并且提出了相应的保护措施,仿真结果表明,不同情况下的不完全信息会对有目的攻击的攻击效率产生不同程度的影响,而基于局部信息的攻击可以达到有目的攻击的攻击效率,该结果对制订高效的Internet攻击(保护)策略具有重要意义。     

基于复杂网络的城市公交网络抗毁性分析*

以国内四个城市公共交通系统为研究对象,对由停靠站点构建的公交网络拓扑结构进行了计算和分析。在此基础上提出了公交网络的抗毁性测度——最大连通子图的相对大小和网络效率,并考察了公交网络在不同攻击模式下的抗毁性。结果表明,公交网络具有对随机攻击的鲁棒性,同时又具有对选择攻击的脆弱性。网络的可靠性是由一些关键节点（公交枢纽站点）的稳定性决定的,应当切实保障这类站点的正常、高效运行。     

Detecting community structure in complex networks using genetic algorithm based on object migrating automata

Community structure is an important topological feature of complex networks. Detecting community structure is a highly challenging problem in analyzing complex networks and has great importance in understanding the function and organization of networks. Up until now, numerous algorithms have been proposed for detecting community structure in complex networks. A wide range of these algorithms use the maximization of a quality function called modularity. In this article, three different algorithms, namely, MEM-net, OMA-net, and GAOMA-net, have been proposed for detecting community structure in complex networks. In GAOMA-net algorithm, which is the main proposed algorithm of this article, the combination of genetic algorithm (GA) and object migrating automata (OMA) has been used. In GAOMA-net algorithm, the MEM-net algorithm has been used as a heuristic to generate a portion of the initial population. The experiments on both real-world and synthetic benchmark networks indicate that GAOMA-net algorithm is efficient for detecting community structure in complex networks.     

基于介度相关性的无标度网络抗毁性研究

复杂网络主要面临随机攻击和选择性攻击,在不同的攻击方式下复杂网络的抗毁性有很大差异。综合考虑复杂网络的抗毁性参数,以节点的度和介数中心性为度量参数,通过5种不同攻击方式对无标度网络的抗毁性进行测试,得到度和介数的实时测量值,动态分析攻击下无标度网络的介度相关性。实验结果表明,无标度网络在ID、RD攻击下介度满足幂律关系,而在IB、RB和随机攻击下不严格满足幂律关系。     

基于子网络结构属性的网络分割研究

Girvan和Newman等人提出了一种基于“中间状态边”概念的网络分割算法,成为研究网络结构的代表性算法。根据“中间状态边”概念,提出了一种新颖的网络分割算法：该算法通过分析构成子网络的两个结构属性,给出了一种划分子网络的方法。根据计算机生成的随机网络和一些真实世界网络的子网络划分实验表明,该算法具有划分准确、计算量小的优点。     

基于通信网抗毁性的链路重要性比较

为了比较通信链路在通信网抗毁性中的重要性,提出了一种基于链路收缩的算法。该算法通过比较每条链路收缩后的通信网生成树数目,判断每条链路对通信网抗毁性影响的重要程度,生成树数目越多,表明该链路越重要,对通信网抗毁性的影响越大。实验结果表明,该算法计算简单,可以精确地反映不同链路对通信网抗毁性的重要程度。     

基于多种群遗传算法的复杂网络社区结构发现*

提出了一种基于多种群遗传算法的复杂网络社区结构发现新算法,该算法无须预先知道社区内节点的数量以及任何门限值,同时引入并行遗传算法的思想,进一步提高了算法的运行效率。实验结果表明,与传统算法相比,在无先验信息的条件下,使用该算法对不同规模的网络图Zachary和Dophins网络结构进行验证时,能够以较低的时间复杂度、高效并准确地完成对网络社区的有效划分。     

基于元胞自动机的无线传感器网络抗毁性分析

因能耗敏感与有效连通性特征等所造成的网络抗毁性能低下是制约无线传感器网络规模应用的主要技术瓶颈之一。针对该问题,利用二维元胞自动机考虑能耗失效、连通性失效等五种失效情形,建立无线传感器网络拓扑演化规则,并基于随机性失效策略与选择性失效策略对网络抗毁性能展开分析。研究表明,网络面临随机失效时抗毁性能明显优于选择性失效。通过失效节点构成分析,在随机失效策略下,能耗失效为造成网络失败主因,而在选择性失效策略下,连通性失效对性能影响更为显著。基于所得结论,为进一步研究网络抗毁性能提升方法提供有益借鉴。     

基于多基因族编码的股票网络社团划分研究

针对传统股票网络社团划分算法发现精度低、时间复杂度高、容易陷入局部最优解的缺点,提出一种基于多基因族(MGF)编码的基因表达式编程(GEP)股票网络社团划分算法,来研究股票市场复杂网络社团化现象.该算法利用多基因族编码的特性,将代表股票节点的ID号和表示社团的类型分别编码在两个不同的多基因族中,再通过一个映射函数将两者的相互作用关系隐式编码在染色体中;同时,将精英迁移策略应用到基因选择、交叉、倒置、限制交换等各个遗传阶段,以避免早熟现象,加快遗传收敛到全局最优解的速度.实验分析表明,该算法能够准确和高效地实现股票复杂网络社团的划分,其划分结果对投资者进行决策具有重要的指导意义.     

基于复杂网络的应急物流网络抗毁性研究*

基于复杂网络理论,引入平均最短路径距离和极大连通子图,研究应急物流网络的抗毁性测度模型,在最大度和介数等不同的攻击策略下分析了单点应急物流网络的抗毁性能。理论分析和实验结果表明,随机攻击的网络易毁性小于选择性攻击;在攻击较多顶点时,度攻击的抗毁性能较弱。     

复杂网络中社团结构划分的快速分裂算法*

针对已有分裂算法时间复杂度较高,不适用于社团数目未知的大型网络等问题,借鉴电压谱分割算法和GN算法的思想,提出以扩散距离为分割依据,以模块度函数为社团结构划分满意度的快速分裂算法.实验结果表明,与已有的社团结构划分算法相比,基于扩散距离的快速分裂算法能够得到高质量的社团结构,其时间复杂度较低,不仅对稀疏网络能够快速运算...