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

复杂网络抗毁性优化算法的设计与实现,冯颜 张琨 黄奉孝 邹勇鑫,南京理工大学计算机科学与技术学院,南京理工大学计算机科学与技术学院,目 录,南京理工大学计算机科学与技术学院,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=； 定义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在新图中的层次值Qi1, K/2，并且保证这条新的边是权值相对最小的一条。,图1 (b) 根为v6时的最小生成树 图2 换路后得到的图,南京理工大学计算机科学与技术学院,3. 算法分析与实现,3.1 求最佳生成树的三种求法 (1) “修改过的prim算法” 算法思想：在prim生成树的每步过程中判断加入的节点的层次，如果大于K/2就停止此步，通过其他的相对最小的边连接此节点，并继续判断，直到结束。 时间复杂度：O(NN 2) (2) “prim算法试探+换路”的方法” 算法思想：对给出的一个完全图MG，每个节点都作为根执行prim算法进行试探，找到使生成树高度达到最小的那个根节点。找到此根节点后，对此生成树中高度大于K/2的节点进行“换路”。 时间复杂度：O(NN 2)。,南京理工大学计算机科学与技术学院,3. 算法分析与实现,3.1 求最佳生成树的三种求法 (3) “一次prim+换路”的方法” 算法思想：对一个给出的完全图MG，任意选取一个节点作为根，执行prim算法求最小生成树，然后扭转此树，找到使得生成树高度达到最小的那个根节点。寻根前后树的拓扑结构是不变的。 时间复杂度：O(N 2) 通过时间复杂度的比较，本文采用第三种方法。,南京理工大学计算机科学与技术学院,3. 算法分析与实现,3.2 生成树节点的优化 得到高度为K/2的“最佳生成树之后”，针对K是奇数或偶数两种情况对节点进行优化： K为偶数 (1) 对叶子节点vi的优化方法： 从旁亲父节点集合中选择一个最优的vj节点(开销值最小)，增加边eij ； (2) 对非叶子节点vi的优化方法： 从相同层次值或层次值小于自己的旁枝节点集合中选择一个最优的vj节点，增加边eij 。 K为奇数 从同级别（即高度相同）或比自己级别高（节点层次值小于自己）的节点集合中选择一个最优的vj节点，增加边eij 。 根节点无需优化，实际网络中对重要的根节点进行信息备份即可。,南京理工大学计算机科学与技术学院,3. 算法分析与实现,3.3 两种优化参数的方法及比较 在节点优化算法过程中，本文给出两种从备选节点集合vj中寻找最优备份链路的方法。两种方法的区别在于选取备份链路时界定“最优”的标准不同，也具有不同的实际意义。 根据“最小开销值” 这种方法很简单，且目的性很明确，直接比较vi与备选节点集合vj中的各个节点之间链路的开销，选取最小的那条链路作为备份。 优点：实现简单； 缺点：只能保证建网的初始开销较小，没有完全考虑链路出现故障后的实际情况。 根据“节点vi的开销和” 用“节点vi的开销和”来评估vj节点，这个值越小越好，根据这个值选择出最佳的那个vj。 优点：网络不仅在建网初期开销值较小，而且在网络出现故障时，仍能通过最节省开销的备份链路，维护网络的正常工作。,南京理工大学计算机科学与技术学院,4.实例分析,原始网络 以一个节点数为9的带权无向图为例，开销矩阵如表1； 优化目标：K=4，寻找一个最小连通度为2的最小开销子图，同时在去除子图中任意一条边后，子图中任意两个节点间的跳数不大于4。,表1 网络的开销矩阵,南京理工大学计算机科学与技术学院,4.实例分析,三种方法求最佳生成树,图3 三种方法求最佳生成树,(a) 修改过的prim算法,(b) 最佳根节点为v0,(c) 换路后的生成树,南京理工大学计算机科学与技术学院,4.实例分析,用两种参数优化生成树,图4 用两种参数优化生成树,(a) 根据“最小开销值”选择备份链路,(b) 根据“节点vi的开销和” 选择备份链路,南京理工大学计算机科学