冯颜-复杂网络抗毁性优化算法的设计

《冯颜-复杂网络抗毁性优化算法的设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、复杂网络抗毁性优化算法的设计与实现冯颜张琨黄奉孝邹勇鑫南京理工大学计算机科学与技术学院南京理工大学计算机科学与技术学院目录引言1复杂网络抗毁性优化算法2算法分析与实现3实例分析4南京理工大学计算机科学与技术学院1.引言研究意义无尺度网络的双重特性：对随机失效的鲁棒性&对选择性攻击的脆弱性复杂网络抗毁性优化算法的设计与实现对提高现实世界中各种网络的抗毁性有着更为重要的应用价值。两个关键技术一、生成高度为K/2的最小生成树：满足网络的节点间跳数不大于K的要求；二、对高度为K/2的最小生成树进行优化：满足连通度为2的

2、要求。南京理工大学计算机科学与技术学院1.引言在现实应用中，几乎所有的复杂系统都可以抽象为复杂网络模型。随着复杂网络的小世界效应及无标度特性的发现，复杂网络研究逐渐成为多个学科共同关注的前沿热点。一旦网络的某个关键节点发生故障，将会给网络的用户带来不便，有时甚至会导致非常严重的后果。为了使在蓄意破坏的情况下，网络故障带给用户的损失减到最小，必须采取一定的措施使网络在发生故障后能够继续提供一定的服务。1.引言南京理工大学计算机科学与技术学院2.复杂网络抗毁性优化算法2.1抗毁性优化算法设计目标主要手段：在网络中增

3、加足够多的备份链路和备份设备。设计目标：忽略网络带宽的因素，用最少的成本建设一个最小连通度为2的网络。该网络中任意一条传输链路中断后，任意两个节点间的最大跳数仍不超过K。图论表示：给定的无向图G(V，E)以及每条边的开销Ce，寻找一个最小连通度为2的最小开销子图；去除子图中任意一条边后，子图中任意两个节点间的跳数不大于K。目前在国内这类算法主要有刘丽娟提出的优化IE模型算法、Wang等提出的熵优化模型算法以及刘啸林提出的基于生成树优化算法等。南京理工大学计算机科学与技术学院2.复杂网络抗毁性优化算法2.2算法思

4、想考虑实际的建网开销和网络使用过程情况，抗毁性优化后的网络应至少符合以下四点要求：（1）连通度为2；（2）网络的节点间跳数不能大于K值；（3）建网总开销值相对较小；（4）网络实际使用时，与网络的一个节点vi相连的一条边故障后，需通过另一条边即备份链路进行通信，以保持网络正常工作；同时还需要保证其他各点到vi的开销和相对较小。基于上述四点要求，算法涉及的相关定义如下：南京理工大学计算机科学与技术学院2.复杂网络抗毁性优化算法定义1网络拓扑结构：用邻接矩阵表示的无向图G(V，E)；顶点集合V=(v1,v2,…,vn

5、)，边集合e=(e1,e2,…,en)，eij=；定义2旁亲父节点：比节点vi的层次值小（即级别比vi高），且不在同一条枝上的所有其他节点。例如图1(b)中节点v3的旁亲父节点为v0，v1，v5。定义3最佳生成树：满足高度为K/2，且开销和相对最小的生成树。图1(a)给定一个无向图(b)根为v6时的最小生成树南京理工大学计算机科学与技术学院2.复杂网络抗毁性优化算法定义4节点vi的层次Qi：生成树的根定义为第0层，与根节点直接连接的节点定义为第l层，依此类推生成树的叶子节点为第D层Qd。对节点的优

6、化又分为下述两种情况：(1)对叶子节点vd进行优化，增加边edj，节点vj要满足下述条件:①节点vj的层次Qj≤D-1；②节点vj与vd的公共父节点只有一个，而且仅是根节点v0，或vj就是根节点v0。(2)对非叶子节点vi进行优化，增加边edj，节点vj要满足下述条件:①若节点vi的层次Qi＝k，那么节点vj的层次Qj≤k，此条件保证不会由于与节点vj的连接而导致跳数超限；②节点vj与vi的公共父节点只有一个，而且仅是根节点v0，或vj就是根节点v0。南京理工大学计算机科学与技术学院2.复杂网络抗毁性优化算法定

7、义5网络开销和addCost(G)：带权无向图G的各边权值总和。如图1(a)所代表的网络开销和为19。定义6节点vi的开销和addCost(vi)：网络中所有其他节点到vi节点的链路开销之和。例如，addCost(v3)=2+(1+2)+(1+2)+(1+1+2)+(1+1+2)+(2+1+2)=21定义7换路：当层次值Qi>K/2的节点与其父节点的连接断开时，从原无向图中重新选择一条边并连接，使得节点vi在新图中的层次值Qi′∈[1,K/2]，并且保证这条新的边是权值相对最小的一条。图1(b)根为v6时的最小

8、生成树图2换路后得到的图南京理工大学计算机科学与技术学院3.算法分析与实现3.1求最佳生成树的三种求法(1)“修改过的prim算法”算法思想：在prim生成树的每步过程中判断加入的节点的层次，如果大于K/2就停止此步，通过其他的相对最小的边连接此节点，并继续判断，直到结束。时间复杂度：O(N×N2)(2)“prim算法试探+换路”的方法”算法思想：对给出的一个完全图MG，每个节点都作为