冯颜复杂网络抗毁性优化算法的设计与实现.pptVIP

复杂网络抗毁性优化算法的设计与实现 冯颜 张琨 黄奉孝 邹勇鑫 南京理工大学计算机科学与技术学院 南京理工大学计算机科学与技术学院 目 录 引 言 1 复杂网络抗毁性优化算法 2 算法分析与实现 3 实 例 分 析 4 南京理工大学计算机科学与技术学院 1. 引 言 研究意义 无尺度网络的双重特性： 对随机失效的鲁棒性对选择性攻击的脆弱性 复杂网络抗毁性优化算法的设计与实现对提高现实世界中各种网络的抗毁性有着更为重要的应用价值。 两个关键技术 一、生成高度为K/2的最小生成树： 满足网络的节点间跳数不大于K的要求； 二、对高度为K/2的最小生成树进行优化： 满足连通度为2的要求。 南京理工大学计算机科学与技术学院 1. 引 言 在现实应用中，几乎所有的复杂系统都可以抽象为复杂网络模型。 随着复杂网络的小世界效应及无标度特性的发现，复杂网络研究逐渐成为多个学科共同关注的前沿热点。 一旦网络的某个关键节点发生故障，将会给网络的用户带来不便，有时甚至会导致非常严重的后果。 为了使在蓄意破坏的情况下，网络故障带给用户的损失减到最小，必须采取一定的措施使网络在发生故障后能够继续提供一定的服务。 1. 引 言 南京理工大学计算机科学与技术学院 2. 复杂网络抗毁性优化算法 2.1 抗毁性优化算法设计目标 主要手段：在网络中增加足够多的备份链路和备份设备。 设计目标：忽略网络带宽的因素，用最少的成本建设一个最小连通度为2的网络。该网络中任意一条传输链路中断后，任意两个节点间的最大跳数仍不超过K。 图论表示：给定的无向图G(V，E)以及每条边的开销Ce，寻找一个最小连通度为2的最小开销子图；去除子图中任意一条边后，子图中任意两个节点间的跳数不大于K。 目前在国内这类算法主要有刘丽娟提出的优化IE模型算法、Wang等提出的熵优化模型算法以及刘啸林提出的基于生成树优化算法等。 南京理工大学计算机科学与技术学院 2. 复杂网络抗毁性优化算法 2.2 算法思想 考虑实际的建网开销和网络使用过程情况，抗毁性优化后的网络应至少符合以下四点要求： （1）连通度为2； （2）网络的节点间跳数不能大于K值； （3）建网总开销值相对较小； （4）网络实际使用时，与网络的一个节点vi相连的一条边故障后，需通过另一条边即备份链路进行通信，以保持网络正常工作；同时还需要保证其他各点到vi的开销和相对较小。 基于上述四点要求，算法涉及的相关定义如下： 南京理工大学计算机科学与技术学院 2. 复杂网络抗毁性优化算法 定义1 网络拓扑结构： 用邻接矩阵表示的无向图G(V，E)； 顶点集合V=(v1, v2,…, vn)，边集合e=(e1, e2,…, en ) ，eij=vi, vj； 定义2 旁亲父节点： 比节点vi的层次值小（即级别比vi高），且不在同一条枝上的所有其他节点。例如图1(b)中节点v3的旁亲父节点为v0，v1，v5。 定义3 最佳生成树： 满足高度为K/2，且开销和相对最小的生成树。 图1 (a) 给定一个无向图 (b) 根为v6时的最小生成树 南京理工大学计算机科学与技术学院 2. 复杂网络抗毁性优化算法 定义4 节点vi的层次Qi： 生成树的根定义为第0层，与根节点直接连接的节点定义为第l层，依此类推生成树的叶子节点为第D层Qd。 对节点的优化又分为下述两种情况： (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. 复杂网络抗毁性优化算法 定义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]