一类影响网络能控性的边集研究*

赵国涛 王立夫 关博飞

(东北大学秦皇岛分校控制工程学院, 秦皇岛 066004)

应用复杂网络描述大规模复杂系统间的相互作用已被广泛接受, 网络中某些边遭受攻击或破坏会使网络不能控. 然而哪些边失效后会对网络能控性造成影响? 针对这一问题, 本文首先提出了类关键边集的概念,并给出了类关键边集的判定定理. 然后通过建立类关键边集失效模型, 来研究类关键边集失效对网络能控性的影响. 最后将类关键边集失效、随机失效、按度失效和按介数失效进行对比, 验证了无论是在模型网络(ER随机网络、BA无标度网络、随机三角形网络和随机矩形网络), 还是26种不同领域的实际网络中, 类关键边集失效对网络能控性的破坏力最大, 同时该结果为网络边攻击提供了一种新方法.

1 引 言

随着社会和科学技术的不断发展, 电力网络、社会关系网络、交通网络和生物网络等大型网络渐渐进入我们的视线. 起初人们对于复杂网络的关注点主要集中在拓扑结构特征上, 如网络的小世界特性[1]、无标度特性[2]等. 而研究复杂网络的主要目的是控制网络的行为, 减少不必要的损害, 更好地为社会服务, 因此复杂网络能控性受到越来越多学者的关注[3,4]. Lin[5]首次提出了结构能控性理论,Liu等[6]利用图的最大匹配计算网络的驱动节点,解决了有向网络的最小输入问题. 然而有些网络,仅仅通过给驱动节点添加输入仍无法使网络结构能控, 为了求解使网络结构能控的最小受控节点,Pequito等[7]提出了一种结构能控性框架, Yin和Zhang[8]给出一个带有约束的数学模型. 以上针对的是有向网络能控性, 对于无向网络的控制,Yuan等[9]利用PBH判据提出复杂网络的严格能控性判据, 该理论适用于任意结构和边权值的网络, 解决了无向网络的能控性问题. 根据网络能控性衍生出来的问题, 例如最小化[10,11]、边控制[12]和对称网络能控性[13]的研究, 都为复杂网络能控性的发展提供了新的思路. 与此同时, 对实际网络能控性的研究也从未止步, 例如交通网络能控性[14,15]、脑网络能控性[16]、电力网络能控性[17]等, 都具有重要的现实意义.

通过对网络拓扑结构的研究可以更好地认识和利用网络. 人们对网络中节点属性的研究取得一些成果, 文献[18]通过节点分类发现了网络的双峰现象, 文献[19, 20]通过节点分类解决了增长网络能控性问题. 但是在边属性方面的研究相对较少,Liu等[6]根据边失效后对网络驱动节点个数的影响, 将边分为三类: 关键边、冗余边和普通边.

当一个网络, 由于自身原因或外部攻击, 导致某些边失效时, 可能使整个网络不能控, 因此网络能控鲁棒性受到越来越多的关注. 对于网络边攻击, 最常见的攻击方法有随机、按度和按介数攻击.例如, Ruths等[21]研究了在给定一组驱动节点的前提下, 边移除对网络受控节点数量的影响.Lu和Li[22]研究了将边按随机攻击、初始度攻击、初始介数攻击和重新计算度攻击、重新计算介数攻击对网络能控性的影响, 结果表明重新计算比按初始值攻击边对网络能控性损害更大. Thomas等[23]分析了在基于度和随机的边攻击下, 用能控性和可达性来度量每次攻击后受控节点位置的改变情况.Chen等[24]在6种有向模型网络中研究了边在按随机攻击、重新计算度攻击、重新计算介数攻击时,对能控性的影响, 并展示了多环结构在网络中的良好性能. 以上的研究都没有考虑网络中某条边失效后对周围边的影响, 因为网络复杂的拓扑结构, 有时候某些边的失效可能引发局部的故障, 进而导致整个网络崩溃[25,26], 因此Nie等[27]研究了单边攻击和边级联失效对网络能控性的影响, 并且发现在无标度网络中, 级联失效并不意味着驱动节点的增加. 不同于以往基于常见的模型网络(随机网络、小世界网络和无标度网络等)的研究, Lou等[28]提出了q-snapback网络模型, 并与multiplex congruence网络、无标度网络进行对比, 研究了基于目标和随机边攻击下的网络鲁棒性. 除了研究网络的单边失效, Shang[29]通过引入子图鲁棒性, 建立了一个分析框架来研究两类子图在随机攻击、局部攻击和目标攻击下的鲁棒性.

通过以上分析可知, 当前网络结构与能控性关系的研究, 主要集中在具有某种网络拓扑属性(度、介数等)的单个节点或边失效对网络能控性的影响上, 缺少一种直接影响网络能控性的方法. 本文主要研究了一类影响网络能控性的边集—“类关键边集”, 通过边分类和节点分类得到了类关键边集的判定定理, 给出类关键边集失效模型, 并推导出失效的理论函数. 通过将类关键边集失效和常见的3种边失效方式(随机失效、按度失效、按介数失效)对比, 在4种模型网络(ER 随机网络、BA无标度网络、随机三角形网络和随机矩形网络)和实际网络中进行边攻击, 分析类关键边集失效对网络能控性的影响.

本文在论述时安排如下: 第2节主要介绍复杂网络能控性的基本概念和网络能控鲁棒性指标;第3节根据节点分类和边分类, 提出类关键边集的概念, 给出类关键边集失效模型, 并推导其失效后的理论曲线; 第4节研究在模型网络和实际网络中不同边失效方式下对网络能控性的影响; 第5节对论文的成果进行总结, 并且给出今后的研究方向.

2 复杂网络能控性

2.1 定 义

对于有向网络G(A)=(X,E) , 其中节点集X={x1,x2,...,xN}, 边集E={e1,e2,···,eM}.A=(aij)N×N表示有向网络G(A) 的邻接矩阵,aij表示节点j对节点i的影响强度. 当aij=0 时,表示节点j和节点i之间不存在有向边 (xj→xi) ;当时,aij的值越大, 表示节点j对节点i的影响强度越大.

对于有向网络G(A) , 将网络中所有边的方向翻转后形成的新网络记为G(AT) , 称G(AT) 为原网络G(A) 的转置网络, 原网络G(A) 中的边(xi→xj) 和转置网络中的边 (xj→xi) 互为转置边.如图1(a) 所示的网络, 当其所有边的方向翻转之后, 形成的转置网络如图1(b)所示. 网络中一共存在7 对转置边, 分别是边 (x4→x1) 和边 (x1→x4) ,(x4→x3) 和边 (x3→x4) , (x4→x5) 和边 (x5→x4) ,(x4→x6) 和边 (x6→x4) , (x1→x2) 和边 (x2→x1) ,(x3→x2) 和边 (x2→x3) , (x6→x5) 和边 (x5→x6).

图1 原网络与转置网络 (a) 原网络; (b) 转置网络Fig. 1. Original network and transpose network: (a) Originalnetwork; (b) transpose network.

有向网络G(A) 边集的一个子集合中任意两条边没有公共的始点也没有公共的终点, 称这个子集为网络G(A) 的一个匹配集. 如果一个节点是匹配集中某条边的终点, 称该节点为匹配节点, 否则该节点为未匹配节点. 网络G(A) 的匹配集中所含边数最多的匹配集被称为最大匹配. 如果一个网络的某个匹配中, 所有的顶点都是匹配节点, 称该匹配为一个完美匹配.

对一个有向网络G(A) 而言, 它可能存在多组不同的最大匹配. 有向网络的最大匹配可以通过对应的二部图得到, 具体做法通过以下方式构造:

2.2 有向网络系统动力学方程

线性时不变系统动力学方程可以表示为

其中,x(t)=(x1(t),x2(t),···,xN(t))T为状态向量,A∈RN×N为状态矩阵,B∈RN×M称为输入矩阵,u(t)=(u1(t),u2(t),···,uM(t))T为输入向量.

将线性时不变系统(LTI)引入到有向网络中,得到有向网络系统G(A,B)=(XA∪XB,EA∪EB) ,其中XA={x1,x2,···,xN},XB={u1,u2,···,uM},aij表示节点j对节点i的影响强度,aij的值越大, 影响强度越大.EB=bij表示在t时刻将输入信号uj(t) 作用于节点i.

2.3 结构能控性

对于一个线性时不变系统, 若存在一个分段连续的输入u(t) , 能够在有限时间 [t0,tf] 内使得系统从任意初始状态x(t0) 转移到任意终止状态x(tf) , 则称此系统是状态能控的. 在控制理论中, Kalman[32]提出的能控性判据为判断系统能控性提供了代数方法, 即系统完全能控的充分必要条件是矩阵

为满秩, 即 r ank(C)=N, 其中C被称为能控性矩阵.

在实际中, 有些网络边权重不可测, 或者随着时间的变化而改变, 因此, Lin[5]提出了结构能控性的概念. 在网络系统G(A,B) 中 , 矩阵A和矩阵B被认为是结构化的, 即它们的元素要么是固定的零, 要么是独立的自由参数. 只需要考虑网络本身的拓扑结构, 而不需要考虑网络节点间的真实权重. 如果将G(A) 中的自由参数固定到某一确定值, 使所得到的网络系统G(A,B) 在通常意义上( r ank(C)=N)是能控的, 则该网络系统G(A,B)是结构能控的.

在输入矩阵B中, 和输入节点连接的状态节点称为受控节点, 那些不共享输入节点的受控节点称为驱动节点. 满足网络结构能控所需的最少的驱动节点的集合就是最小驱动节点集(minimum driver node set, MDS), MDS可以通过最小输入定理[6]求出.

引理1 最小输入定理完全控制有向网络G(A) 所需要的最少输入节点数NI或者最少驱动节点数ND取决于网络G(A) 的最大匹配, 如果G(A) 存在完美匹配, 则ND等于1并可选择网络中的任一节点作为驱动节点; 如果G(A) 不存在完美匹配, 则ND等于网络中的未匹配节点数, 并且未匹配的节点就是所寻找的驱动节点. 即:

其中M表示网络G(A) 的一个最大匹配,|M|表示网络G(A) 最大匹配的边数.

对于有向网络, 某些边会因为外界或自身因素而失效, 为了评判边失效后对网络能控性的影响,可以由控制节点密度nD来量化, 其定义为控制网络所需要的最小驱动节点数ND占网络节点总数N的比例, 记为

其中,nD的大小反映复杂网络控制的难易程度, 其值越小, 说明网络达到完全能控所需的驱动节点数占总节点数的比例越小, 网络越容易控制, 同时网络的能控鲁棒性越好.

3 类关键边集对网络能控性的影响

3.1 节点分类与边分类

对于给定的网络, 当网络满足结构能控时, 所需的最少的驱动节点的个数是固定的. 然而, 一个网络可能存在多组最大匹配, 导致网络存在多种MDSs. 根据每个节点参与MDS的程度[18], 将网络节点分成三类, 定义如下.

定义1如果一个节点参与所有的MDSs, 则这个节点称为关键节点; 如果一个节点不全参与所有的MDSs, 则这个节点称为间歇节点; 如果一个节点不参与任何一个MDSs, 则这个节点称为冗余节点.

对于图1(a)所示的网络, 所有可能的最大匹配和MDS如图2(a). 节点4参与所有MDSs, 因此为关键节点. 节点1, 3, 6不全参与所有MDSs,因此为间歇节点. 节点2, 5不参与任何一个MDSs, 因此为冗余节点, 结果如图2(b)所示.

类似地, 根据每条边参与最大匹配的程度, 将所有边分成三类, 定义如下.

定义2如果一条边参与所有的最大匹配, 则这条边称为关键边; 如果一条边不全参与所有的最大匹配, 则这条边称为间歇边; 如果一条边不参与所有的最大匹配, 则这条边称为冗余边.

对于图1(a)所示的网络, 所有可能的最大匹配如图2(a). 根据定义2, 对网络中边进行分类, 结果见图2(b). 其中, 边 (x6→x5) 参与所有的最大匹配, 为关键边. 边 (x4→x1) , (x4→x3) , (x4→x6) ,

图2 有向网络节点分类和边分类 (a) 有向网络所有可能的最大匹配以及对应的MDS; (b) 节点分类和边分类Fig. 2. Directed network node classification and edge classification: (a) All possible maximum matching and corresponding MDS of directed network; (b) node classification and edge classification.

(x3→x2) , (x1→x2) 不全参与所有的最大匹配,因此为间歇边. 边 (x4→x5) 不参与所有的最大匹配, 因此为冗余边.

在定义2中, 通过分析边在最大匹配中的参与程度, 将网络中所有边分成了三类, 而最大匹配中边的个数会直接影响网络驱动节点个数ND, 下述定理1讨论了三类边失效后对网络能控性的影响.

定理1 网络中不同类型的边失效对能控性的影响

1) 当关键边失效时, 网络最大匹配的边数减少1, 驱动节点个数ND增加1;

2) 当间歇边失效时, 网络最大匹配的边数不变, 驱动节点个数ND保持不变, 但是网络所有可能的最大匹配个数将减少;

3) 当冗余边失效时, 网络最大匹配的边数不变, 网络驱动节点个数ND保持不变, 网络所有可能的最大匹配个数不变.

证明

1) 反证法: 对于给定的有向网络G(A) , 存在最大匹配M,|M|表示最大匹配中的边数. i)假设关键边失效后, 网络最大匹配的边数增加t,t＞0.那么在关键边不失效时, 网络最大匹配的边数就是|M|+t, 与最大匹配的边数唯一矛盾. 因此关键边失效时, 网络最大匹配的边数不会增加. ii)假设关键边失效后, 网络最大匹配的边数保持不变. 那么在关键边不失效时, 关键边就不会一直参与最大匹配, 与关键边定义矛盾. 因此关键边失效时, 网络最大匹配的边数不会保持不变. iii)假设关键边失效后, 网络最大匹配的边数减少r,r＞1. 当关键边失效后, 假如现在的最大匹配M’ 为原最大匹配M除去关键边, 则M’ 对应的最大匹配边数为|M|-1 ,与假设的最大匹配的边数为|M|-r,r＞1 矛盾.因此关键边失效时, 网络最大匹配的边数不会减少r,r＞1. 综上i) ii) iii)所述, 当关键边失效时, 网络最大匹配的边数减少1, 根据引理1, 驱动节点个数ND增加1.

2) 由于间歇边不全参与最大匹配, 至少存在一个最大匹配不包含要失效的间歇边, 因此间歇边的失效不影响最大匹配的边数, 驱动节点个数ND也保持不变. 由于去掉了间歇边, 也就去掉了所有包含该失效间歇边的最大匹配, 因此网络所有可能的最大匹配个数将减少.

3) 由于冗余边不参与最大匹配, 因此冗余边去掉之后对网络最大匹配无影响, 网络驱动节点个数ND保持不变, 网络所有可能的最大匹配个数也不变.

通过定理1, 将每个不同类型的边与网络能控性(驱动节点个数ND)建立了联系.

在对网络中的边进行分类时, 根据定义2, 需要求出网络所有的最大匹配, 但这是一个NP问题[33]. 由于给定网络的最大匹配边数是固定的, 因此, 从最大匹配边数变化的角度来对边分类将是一个可行的方法. 根据定理1可知, 关键边失效后,会使网络最大匹配边数减少1; 冗余边总是不参与最大匹配, 如果被强制参与匹配(去掉和该边同出节点以及同入节点的所有边), 会使原来参与最大匹配的两条边不参与最大匹配, 网络中最大匹配边数与之前相比将减少1; 如果一条边既不属于关键边又不属于冗余边, 则为间歇边. 综上三种情况,可以给出网络边分类的算法:

算法1 网络中边分类算法

Step 1: 求出网络一组最大匹配, 记匹配边数为m;

Step 2: 遍历网络中所有的边, 如果存在一条边 (xi→xj) , 在去掉该边后, 新网络的最大匹配边数m1满足m1=m-1 , 则该边为关键边;

Step 3: 遍历网络中所有的边, 如果存在一条边 (xi→xj) , 在去掉和该边同出节点以及同入节点的所有边后, 新网络的最大匹配边数m2满足m2=m-1, 则该边为冗余边;

Step 4: 遍历网络中所有的边, 如果存在一条边 (xi→xj) , 既不属于关键边又不属于冗余边, 则该边为间歇边.

3.2 类关键边集概念

网络中某个或某些边的失效会影响网络能控性, 使网络满足结构能控所需的最小的驱动节点个数增加, 本文研究了一类影响网络能控性的边集称为“类关键边集”, 其定义如下:

定义3对于网络中的一组边集EC, 当EC同时失效时网络驱动节点个数(ND)增加1, 并且当EC中任意|EC|-1 条边失效时网络驱动节点个数(ND)保持不变, 则称边集EC为类关键边集.

注1|EC|-1 表示边集EC中的边数减1. 根据定义3可以知道, 对于存在类关键边集的有向网络, 移除任意一个类关键边集, 都会使ND增加1.

由于类关键边集是一组边的集合, 不同的类关键边集, 其元素个数不一定相同. 因此类关键边集根据元素的多少, 又可以细分.

定义4边数为1的类关键边集称为1-元类关键边集. 边数为2的类关键边集称为2-元类关键边集. 同理, 边数为x的类关键边集称为x-元类关键边集.

3.3 类关键边集的辨识

对于一个有向网络, 通过定义3, 很难求出网络中所有的类关键边集, 因此下面给出类关键边集判定定理.

定理2 类关键边集判定定理

1) 有向网络G(A) 中指向同一个冗余节点的所有间歇边的集合, 一定为类关键边集;

2) 有向网络G(A) 的转置网络G(AT) 中指向同一冗余节点的所有间歇边的转置边的集合, 一定为类关键边集.

证明

1) 根据冗余节点的定义, 冗余节点一定不参与MDSs, 因此冗余节点一定是匹配节点, 并且指向冗余节点的边中一定存在一条匹配边. 根据间歇边的定义, 间歇边会参与最大匹配, 因此, 对于指向同一个冗余节点的所有的x条间歇边, 只有一条参与最大匹配, 而只有把这x条间歇边全部去掉才可以使网络驱动节点个数增加1.

2) 与1)同理, 只有转置网络中指向同一个冗余节点的所有间歇边全部去掉之后, 才可以使转置网络驱动节点个数增加1, 其对应的原网络驱动节点个数也增加1.

注2根据定义3, 有向网络中的关键边, 一定为类关键边集.

通过以上分析可以知道, 关键边是一种特殊的类关键边集, 而类关键边集是关键边在能控性方面的推广. 通过定理2, 可以得到对应的类关键边集搜寻算法.

算法2 类关键边集搜寻算法

Step 1: 对原网络进行节点分类和边分类, 找出关键节点、间歇节点和冗余节点, 关键边、间歇边和冗余边;

Step 2: 记每个关键边为1-元类关键边集;

Step 3: 遍历所有的冗余节点, 将指向同一个冗余节点的所有的x条间歇边记为x-元类关键边集(x=2,3,···);

Step 4: 求原网络的转置网络, 并对转置网络进行边分类和节点分类, 找出转置网络中的关键节点、间歇节点和冗余节点, 关键边、间歇边和冗余边;

Step 5: 遍历转置网络中所有的冗余节点, 将指向同一个冗余节点的所有的x条间歇边的转置边记为x-元类关键边集(x=2,3,···).

对于图1(a)所示的网络, 其原网络和转置网络的节点分类和边分类如图3(a)和图3(b)所示.通过类关键边集搜寻算法, 网络中所有的x-元类关键边集如图3(c)所示, 在原网络中, 边(x6→x5)为关键边, 因此为1-元类关键边集. 边 (x1→x2) ,(x3→x2)为指向冗余节点2的所有间歇边, 因此为2-元类关键边集. 在转置网络中, 边 (x1→x4) ,(x3→x4) , (x6→x4) 是指向冗余节点4的所有间歇边, 因此其转置边 (x4→x1) , (x4→x3) ,(x4→x6)为3-元类关键边集.

图3 寻找有向网络中的类关键边集 (a), (b) 原网络和转置网络中的节点分类和边分类; (c) 网络中的类关键边集Fig. 3. Find the quasi-critical edge set in directed network:(a), (b) Node classification and edge classification in original network and transpose network; (c) quasi-critical edge set in the network.

3.4 类关键边集失效对能控性影响分析

为了研究类关键边集失效后对网络能控性的影响, 提出了类关键边集失效模型.

类关键边集失效模型

Step 1: 搜寻网络中所有的x-元类关键边集(x=1,2,3,···);

Step 2: 任意选择一个元素最少的x-元类关键边集(x=1,2,3,···), 将其包含的所有边在网络中移除;

Step 3: 计算边移除比例p和新网络的能控性nD;

Step 4: 检查网络中是否存在边. 如果存在边,转向Step1, 否则结束运行.

由于每次失效都会选择一个类关键边集, 根据类关键边集的定义, 每移除一个x-元类关键边集(x=1,2,3,···), 都使网络驱动节点个数增加1, 因此网络能控性nD与边移除比例p之间存在正比关系, 即能控性nD与边移除比例p的理论关系曲线为一次分段函数.

假设在n个节点,e条边的有向网络中, 最大匹配的边数为m(m≤n) 个. 网络中所有边都失效后, 假设一共移除了c1个1-元类关键边集,c2个2-元类关键边集,c3个3-元类关键边集,···,cj个j-元类关键边集,···,ci个i-元类关键边集(m=则能控性nD与边移除比例p的理论函数为

根据以上分析, 可以画出失效函数的理论曲线, 如图4所示, 可以更加直观地看出类关键边集失效后曲线的分段性和一次性. 通过对曲线的分析, 可以得到其斜率为

图4 基于类关键边集的边失效理论曲线Fig. 4. Theoretical curve of edge failure based on quasi-critical edge set.

其中,x为每次失效的类关键边集中边的数量. 对于给定的网络, 斜率的最小值和最大值取决于x的大小. 当x=1 时, 即网络存在1-元类关键边集, 代入(7)式, 有斜率最大值〈kin〉=〈kout〉, 由于优先攻击边数少的类关键边集,因此其初始斜率就是最大斜率, 并且初始斜率的大小与网络平均度 〈k〉 有关. 当x→∞时, 代入(7)式, 有最小值由于网络的边数是有限的, 因此其最小斜率只能无限趋向于0.

下面通过一个实例介绍类关键边集失效过程,对于图1(a)所示网络, 其驱动节点个数为3. 按照类关键边集失效模型, 寻找网络x-元类关键边集,如图5(a). 优先移除元素个数为1的1-元类关键边集 (x6→x5) , 此时新网络驱动节点数由3变成4. 重新寻找新网络x-元类关键边集, 如图5(b)所示, 移除2-元类关键边集 (x1→x2) , (x3→x2) , 此时新网络驱动节点数由4变成5. 重新寻找新网络x-元类关键边集, 如图5(c)所示, 移除4-元类关键边集 (x4→x1) , (x4→x3) , (x4→x5) , (x4→x6) ,此时新网络节点全部变成孤立节点, 驱动节点数由5变成6, 如图5(d)所示.

图5 图1(a) 所示网络的边失效过程Fig. 5. The edge failure process of the network shown in Fig. 1(a).

根据以上失效过程, 可以计算出边失效比例p对网络能控性nD影响的曲线, 与上述攻击过程相符, 一共由3段不同斜率、不同截距的一次函数组成, 如图6所示, 斜率分别为分析斜率的大小可以知道, 当斜率越大时, 说明一定数量的边失效后, 对网络能控性破坏越大, 网络保持能控所需的ND就越多. 当斜率越小时, 说明一定数量的边失效后, 对网络能控性破坏越小, 网络保持能控所需的ND就越少.

图6 图1(a)所示网络的边失效曲线Fig. 6. The edge failure curve of the network shown in Fig. 1(a).

对于任何有向网络, 其任意一条边失效后, 驱动节点个数最多增加1. 当关键边失效时, 会使网络驱动节点数增加1, 因此关键边是对网络能控性影响最大的一类边; 当网络中无关键边时, 失效任意一条边驱动节点数不会增加, 此时失效多条边可导致驱动节点数增加,x-元类关键边集 (x≥2) 成为失效后使驱动节点个数增加1的边数最少的边集, 此时x-元类关键边集是对网络能控性影响最大的边集. 由于关键边可作为边数为1的类关键边集, 因此在失效相同边数的情况下, 类关键边集对网络能控性的影响是最大的. 在某些应用背景下,需要保持较高网络能控性时, 可对类关键边集按次序进行重点保护.

4 仿 真

4.1 网络中不同属性边占比研究

为了研究3种不同类型的边(关键边、间歇边和冗余边)占网络总边数的比例p, 分别选取了4种节点总数为500的模型网络(ER随机网络[34]、BA无标度网络[2]、随机三角形网络[35,36]和随机矩形网络[24])进行仿真.

对于ER随机网络, 平均度〈k〉=〈kin〉=〈kout〉从1增加到30, 每次增加1. 对于BA无标度网络,新节点作为弧头连接的节点数min等于新节点作为弧尾连接的节点数mout都从1增加到30, 每次初始网络存在min+1 个 节点和min+1 条边, 首尾连接, 保证网络的连通性. 对于随机三角形网络, 平均度从3开始, 增加到30, 每次增加1. 对于随机矩形网络, 平均度从4开始, 增加到30, 每次增加1. 对于每个确定度下的网络, 运行50次后取平均值, 仿真结果如图7所示.

图7 不同网络中关键边、间歇边和冗余边占网络总边数的比例随网络度的变化曲线 (a) ER随机网络; (b) BA无标度网络;(c) 随机三角形网络; (d) 随机矩形网络Fig. 7. Curve of the ratio of critical edge, intermittent edge and redundant edge to the total number of network edges with network degree in different networks: (a) ER random network; (b) BA scale-free network; (c) random triangle network; (d) random rectangle network.

通过仿真发现以下结果. i)随着网络平均度的增加, 网络中的关键边占整个网络总边数的比重逐渐降低, 间歇边占整个网络总边数的比重升高. 当网络中关键边的数量几乎为0, 间歇边占整个网络边数的比重达到1时, 对应ER随机网络的平均度〈k〉＞6; BA无标度网络新节点作为弧头和弧尾连接的节点数min=mout＞4 ; 随机三角形网络的平均度 〈 k〉＞7 ; 随机矩形网络的 平均度 〈 k〉＞6.ii)随着网络平均度的增加, ER随机网络和BA无标度网络中的冗余边占整个网络边数的比重先增加后降低, 对于ER随机网络, 其峰值对应平均度〈k〉=2; 对于BA无标度网络, 其峰值对应新节点作为弧头和弧尾连接的节点数min=mout=2.iii)对于随机三角形网络和随机矩形网络, 由于其初始度从3和4开始, 其冗余边占整个网络总边数的比重随着网络平均度的增加一直减小.

根据定理1, 网络中关键边的失效会导致ND增加1, 但是在致密网络中, 关键边的数量几乎为0, 只存在间歇边, 然而单个间歇边的失效不会对网络能控性(ND)造成影响, 因此, 对于致密网络来说, 不容易找到影响网络能控性的边. 而本文研究的类关键边集对能控性的影响结果适合所有类型的网络. 具体来说, 对于稀疏网络, 影响网络能控性的边集中既存在1-元类关键边集(关键边),又存在x-元类关键边集(多条间歇边组成的集合,x≥2); 对于致密网络, 在影响网络能控性的边集中只存在x-元类关键边集(多条间歇边组成的集合,x≥2 ).

4.2 边失效对网络能控性影响的对比

本节在4种模型网络(ER随机网络、BA无标度网络、随机三角形网络和随机矩形网络)和26种实际网络中, 将类关键边集失效(failure of quasi-critical edge set, FQ)和常见的3种边失效方式进行对比, 观察不同失效方式下的网络能控性nD, 分析类关键边集失效后对网络能控性的影响.常见的边失效方式有以下几种.

1)边随机失效: 随机删除网络中的一条边.

2)基于度的边失效: 删除网络中度最大的一条边. 边度的定义为边两端节点度的几何均数[37].对于边aij, 其边度可以表示为其中ki为节点i的入度,kj为节点j的出度.

3)基于介数的边失效: 删除网络中介数最大的一条边. 边的介数定义为网络中所有的最短路径中经过边的数量比例. 对于边aij, 其介数可以表示为其 中Nlm表 示 节 点l和节点m之间的最短路径的条数,Nlm(aij) 表示节点l和节点m之间的最短路径经过边aij的条数.

根据Lu和Li[22]的结论, 基于重新计算的失效方式通常比基于初始计算的失效方式更能损害网络的能控性. 因此, 对于以上3种失效方式, 和本文提出的类关键边集失效模型一样, 在每次边失效后都需要对网络中的度或介数重新计算. 需要注意的是, 基于随机、度、介数的失效方式每次只攻击一条边, 而我们提出的类关键边集失效模型虽然每次移除的边数不同, 但由于最终分析的是网络边移除比例p对网络能控性nD的影响, 因此每次移除边数的多少对最终的结论无影响.

4.2.1 ER 随机网络

本节将生成节点数分别为300, 500, 700,〈kin〉=〈kout〉=2的ER随机网络. 考虑到网络的能控性与网络平均度(边的密度)具有相关性[38], 又生成节点总数分别为300, 500, 700,〈kin〉=〈kout〉=6的ER随机网络, 按照以上4种边失效方式(类关键边集失效、随机失效、按度失效和按介数失效)将网络中边移除, 记录边失效比例p与网络能控性nD的曲线, 如图8(a)—图8(f)所示.

图8 不同节点总数和平均度的随机网络在4种边失效方式下网络能控性 n D 的变化 (a)节点总数 N =300 , 平均度〈kin〉=〈kout〉=2 的随机网络; (b)节点总数 N =500 , 平均度 〈 kin〉=〈kout〉=2 的随机网络; (c)节点总数 N =700 , 平均度〈kin〉=〈kout〉=2 的随机网络; (d)节点总数 N =300 , 平均度 〈 kin〉=〈kout〉=6 的随机网络; (e)节点总数 N =500 , 平均度〈kin〉=〈kout〉=6 的随机网络; (f)节点总数 N =700 , 平均度 〈 kin〉=〈kout〉=6 的随机网络Fig. 8. The change of controllability n D of random networks with different number of nodes and average degree under four kinds of edge failure modes: (a) A random network with number of nodes N =300 and average degree 〈 kin〉=〈kout〉=2 ; (b) a random network with number of nodes N =500 and average degree 〈 kin〉=〈kout〉=2 ; (c) a random network with number of nodes N=700 and average degree 〈 kin〉=〈kout〉=2 ; (d) a random network with number of nodes N =300 and average degree〈kin〉=〈kout〉=6 ; (e) a random network with number of nodes N =500 and average degree 〈 kin〉=〈kout〉=6 ; (f) a random network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=6.

通过仿真发现: i)在不同的4种失效方式下,随着网络边移除比例p的增加, 网络能控性nD也在一直增加, 说明网络的能控性在不断降低. ii)不管网络节点总数N和平均度 〈k〉 如何变化, 类关键边集失效对网络能控性的影响最大. 在网络边移除前期, 当移除比例为0.1时, 网络能控性nD上升大约20%. 另外, 按介数失效和随机失效、按度失效相比, 对网络能控性的影响最大, 并且随着网络平均度的增加, 介数失效和随机失效、按度失效之间的差距越来越明显. iii)随着网络平均度的增加, 失效曲线的一次性和分段性变得不明显, 曲线变得更加平滑, 说明此时网络中存在单个类关键边集的元素个数非常大.

4.2.2 BA 无标度网络

本节将生成节点数分别为300, 500, 700 的BA无标度网络. 设置初始网络为 4 个节点和 4 条边, 且首尾连接. 为了研究度的影响, 分别使新节点作为弧头连接的节点数min等于新节点作为弧尾连接的节点数mout等于1或2[39]. 按照以上4种边失效方式(类关键边集失效、随机失效、按度失效和按介数失效)将网络中边移除, 记录边失效比例p与网络能控性nD的曲线, 如图9(a)—图9(f)所示.

图9 不同节点总数和平均度的无标度网络在4种边失效方式下网络能控性 n D 的变化 (a) 节点总数 N =300 ,min=mout=1 的无标度网络; (b) 节点总数 N =500 , m in=mout=1 的无标度网络; (c) 节点总数 N =700 ,min=mout=1的无标度网络; (d) 节点总数 N =300 , m in=mout=3 的无标度网络; (e) 节点总数 N =500 , m in=mout=3 的无标度网络;(f) 节点总数 N =700 , m in=mout=3 的无标度网络Fig. 9. The change of controllability n D of scale-free networks with different number of nodes and average degree under four kinds of edge failure modes: (a) A scale-free network with number of nodes N =300 and m in=mout=1 ; (b) a scale-free network with number of nodes N =500 and m in=mout=1 ; (c) a scale-free network with number of nodes N =700 and m in=mout=1 ; (d)a scale-free network with number of nodes N =300 and m in=mout=3 ; (e) a scale-free network with number of nodesN=500 and m in=mout=3 ; (f) a scale-free network with number of nodes N =700 and m in=mout=3.

通过仿真发现: i)在不同的4种失效方式下,随着网络边移除比例p的增加, 网络能控性nD也在一直增加, 说明网络的能控性在不断降低; ii)不管网络节点总数N和平均度 〈k〉 如何变化, 类关键边集失效对网络能控性的影响最大. 在网络边移除前期, 当min=mout=1 时, 边移除比例为0.1,nD大约上升20%. 当min=mout=3 时, 边移除比例为0.1,nD大约上升30%. 另外, 按介数失效和随机失效、按度失效相比, 对网络能控性的影响最大, 随着网络平均度的增加, 介数失效和随机失效、按度失效之间的差距越来越明显.

4.2.3 随机三角形网络

本节生成节点总数分别为300, 500, 700, 平均度为2的随机三角形网络, 又生成节点总数分别为300, 500, 700, 平均度为6的随机三角形网络, 选取4种失效方式分别对网络中的边进行移除, 记录能控性变化nD与边失效比例p的曲线, 如图10(a)—图10(f)所示.

图10 不同节点总数和平均度的随机三角形网络在4种边失效方式下网络能控性 n D 的变化 (a) 节点总数 N =300 , 平均度〈kin〉=〈kout〉=2 的随机三角形网络; (b) 节点总数 N =500 , 平均度 〈 kin〉=〈kout〉=2 的随机三角形网络; (c) 节点总数N=700 , 平均度 〈 kin〉=〈kout〉=2 的随机三角形网络; (d) 节点总数 N =300 , 平均度 〈 kin〉=〈kout〉=6 的 随 机 三 角形网络;(e) 节点总数 N =500 , 平均度 〈 kin〉=〈kout〉=6 的随机三角形网络; (f) 节点总数 N =700 , 平均度 〈 kin〉=〈kout〉=6 的随机三角形网络Fig. 10. The change of controllability n D of random triangle networks with different number of nodes and average degree under four kinds of edge failure modes: (a) A random triangle network with number of nodes N =300 and average degree〈kin〉=〈kout〉=2 ; (b) a random triangle network with number of nodes N =500 and average degree 〈 kin〉=〈kout〉=2 ;(c) a random triangle network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=2 ; (d) a random triangle network with number of nodes N =300 and average degree 〈 kin〉=〈kout〉=6 ; (e) a random triangle network with number of nodes N=500 and average degree 〈 kin〉=〈kout〉=6 ; (f) a random triangle network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=6.

通过仿真发现: i)在不同的4种失效方式下,随着网络边移除比例p的增加, 网络能控性nD也在一直增加, 说明网络的能控性在不断降低; ii)不管网络节点总数N和平均度 〈k〉 如何变化, 类关键边集失效对网络能控性的影响最大, 在网络边移除前期, 当平均度 〈kin〉=〈kout〉=3 时, 边移除比例为0.1, 网络能控性nD上升大约25%. 当〈kin〉=〈kout〉=6 时, 边移除比例为0.1, 网络能控性nD上升大约20%; iii) 按介数失效和随机失效、按度失效相比, 当网络平均度 〈k〉 较小时, 三者差别不大,随着网络平均度 〈k〉 的增大, 按介数失效相较于随机失效、按度失效, 对网络能控性的影响逐渐明显.

4.2.4 随机矩形网络

本节生成节点总数分别为300, 500, 700, 平均度为2的随机矩形网络, 又生成节点总数分别为300, 500, 700, 平均度为6的随机矩形网络, 选取4种失效方式分别对网络中的边进行移除记录能控性变化nD与边失效比例p的曲线, 如图11(a)—图11(f)所示.

图11 不同节点总数和平均度的随机矩形网络在四4边失效方式下网络能控性 n D 的变化 (a) 节点总数 N =300 , 平均度〈kin〉=〈kout〉=2 的随机矩形网络; (b) 节点总数 N =500 , 平均度 〈 kin〉=〈kout〉=2 的随机矩形网络; (c) 节点总数 N =700 , 平均度 〈 kin〉=〈kout〉=2 的随机矩形形网络; (d) 节点总数 N =300 , 平均度 〈 kin〉=〈kout〉=6 的随机矩形网络; (e) 节点总数N=500 , 平均度 〈 kin〉=〈kout〉=6 的随机矩形网络; (f) 节点总数 N =700 , 平均度 〈 kin〉=〈kout〉=6 的随机矩形网络Fig. 11. The change of controllability n D of random rectangle networks with different number of nodes and average degree under four kinds of edge failure modes: (a) A random rectangle network with number of nodes N =300 and average degree〈kin〉=〈kout〉=2 ; (b) a random rectangle network with number of nodes N =500 and average degree 〈 kin〉=〈kout〉=2 ; (c) a random rectangle network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=2 ; (d) a random rectangle network with number of nodes N =300 and average degree 〈 kin〉=〈kout〉=6 ; (e) a random rectangle network with number of nodes N=500 and average degree 〈 kin〉=〈kout〉=6 ; (f) a random rectangle network with number of nodes N =700 and average degree 〈 kin〉=〈kout〉=6.

通过仿真发现: i)在不同的4种失效方式下,随着网络边移除比例p的增加, 网络能控性nD也在一直增加, 说明网络的能控性在不断降低; ii)不管网络节点总数N和平均度 〈k〉 如何变化, 类关键边集失效对网络能控性的影响最大. 在网络边移除前期, 当 〈kin〉=〈kout〉=3 时, 边移除比例为0.1, 网络能控性nD上升大约25%, 当 〈kin〉=〈kout〉=6 时,边移除比例为0.1, 网络能控性nD上升大约20%;iii) 按介数失效和随机失效、按度失效相比, 当网络平均度 〈k〉 较小时, 三者差别不大, 随着网络平均度 〈k〉 的增大, 按介数失效相较于随机失效、按度失效, 对网络能控性的影响逐渐明显; iv)随机失效和按度失效相比, 当网络平均度 〈k〉 较小时, 随机失效对网络影响较大, 随着网络平均度 〈k〉 的增大, 按度失效对网络能控性影响大.

4.2.5 实际网络

下面将4种边失效方式应用到实际网络中, 进一步比较4种失效方式(关键边集失效、随机失效、按度失效和按介数失效)对网络能控性nD的影响. 选取电力网络、动物网络、人际关系网络和商品贸易网络等不同领域的26种网络[40]. 这些网络的规模从几十个到几百个节点不等, 既有稀疏网络又有致密网络. 针对4种失效方式, 分别计算当边移除比例p=0.2 ,p=0.5 和p=0.8 时网络能控性nD的数值, 结果见表1.

对比表1中同一移除比例下4种失效方式的能控性nD的大小, 可以发现: i)不管是哪种失效方式, 网络能控性nD都在不断增加, 且类关键边集失效方式对应的nD比其余3种边失效方式都要大;ii)对于类关键边集失效, 当边移除比例p=0.8 时,以上不同类型的所有网络的能控性nD都可以达到80%以上, 且与初始nD和网络平均度的大小无关;iii)对于节点总数少、边总数多(平均度大)的网络,例如Animal Hens, Collaboration in jazz, Joint senate press releases, Children’s network of friendship, Trade goods in different countries和Questionnaire for grade seven students等, 网络能控性的初始值nD比较小, 在边失效初期, 随机失效、按介数失效和按度失效在移除边数比较少时对网络能控性影响较小, 但是, 类关键边集失效对网络能控性nD造成的破坏性较大; iv) 对于平均度比较大的网络, 随机攻击对网络能控性的影响最小,当网络中边失效比例达80%时, 能控性nD还未达到50%, 例如Animal Hens, Collaboration in jazz,Joint senate press releases, corporate law partnership_law firm, Trade goods in different countries_Foods, Trade goods in different countries_Crude materials和 Trade goods in different countries_Diplomacy等, 这与模型网络中的结论一致.

表1 实际网络中4 种边失效对能控性的影响Table 1. Influence of four edge failures on controllability in real networks.

5 结 论

本文通过对节点和边分类, 提出了类关键边集的概念, 得到了类关键边集的判定定理, 并提出了基于类关键边集的边失效模型. 对类关键边集失效曲线进行理论分析, 发现失效曲线为一次分段函数, 其最大(初始)斜率与网络度有关, 并且类关键边集是对网络能控性影响最大的一类边, 和常见的边失效方式相比, 该失效模型对网络能控性破坏最大. 通过在4种模型网络和26种实际网络中对比常用的3种边失效方式(随机失效、按度失效和按介数失效)进行仿真, 结果验证了类关键边集是对网络能控性影响最大的一类边, 以及基于类关键边集的失效模型也是对网络能控性破坏力最大的边失效方式. 在实际生活中, 对于癌细胞网络、恐怖主义通信网络等对人类存在危害的网络, 该失效模型可提供一种可行的攻击方案.

本文只考虑到有向网络一类边在能控性方面的属性, 有没有一类节点也影响网络能控性, 或者是否存在一类影响网络多种性质(能控性、连通性等)的节点或者边, 需要进行深入研究. 另外, 类关键边集的概念只适合有向网络, 是否可以推广至无向网络同样值得去探索. 与此同时, 和攻击策略对应的就是防御策略, 如何去增强网络鲁棒性又是另一个有意义的研究方向.