边转换与增加对有向网络能控性的影响

张虎林　李成铁　王立夫

摘要： 复杂网络的不同类型边转换（方向改变）和在不同节点间增加边对网络能控性有不同影响，为了更好地了解有向网络边转换和增加对网络能控性影响，提出一种边分类方法，把边根据节点类别和匹配关系分成12种类型，并给出辨识算法。基于此分类给出网络边转换和增加时网络能控性（驱动节点数目）的变化规律。通过模型网络和实际网络分析了每种边在网络中的比例，并分析了边转换和增加时驱动节点数目变化。结果验证了定理的正确性。

关键词： 网络能控性;驱动节点;最大匹配;转换边;增加边

中图分类号： N94文献标识码： A

Influence of Alteration and Addition of Edges on Directed Network Controllability

ZHANG Hulin， LI Chengtie， WANG Lifu

Abstract：The alternation of different types of edges （direction changed） and the addition of edges between different nodes in complex networks will have different effect on the controllability of the network. In order to better understand the influence of altering different edges and adding different edges on network controllability in directed networks， this paper proposes a classification method of edges. According to the node category and matching relationship， the directed edges are divided into twelve types， and the algorithm of identification is given. Based on the classification， the change law of network controllability （the number of driving nodes） is given when the edges of networks are altered and added. Through the simulation experiment of the model networks and the actual networks， the proportion of different types of edges is analyzed. When edges are altered and added， the changes in the number of driven nodes are analyzed in the model networks and the actual networks. The correctness of the theorems of this article are verified.

Key words： network controllability; driver node; maximum matching; alteration of edges; addition of edges

0 引言

近些年来，随着网络科学的发展，人们发现各种复杂系统（相互作用和依赖的各部分组成的具有特定功能的整体）可以由节点和连边组成的网络来表示，其中网络中各节点表示系统的各个组成部分，节点间的边表示各组成部分的相互作用和依赖关系。例如，计算机网络［1］可以看成由很多独立工作的计算机通过传输介质相连而成的网络［1］，其中独立工作的计算机看作节点，传输介质看作节点间的连边；电力网络［2-3］可以看作由各个变电站通过电缆连接而成的网络，其中變电站看作节点，电缆看作连接节点间的连边。类似的还有交通网络［4］和生物网络［5］等。

研究复杂网络［6-7］的最终目的是寻找有效的控制手段控制网络行为。从经典控制理论可知，控制网络行为的前提是该网络必须是完全能控的，因此研究复杂网络能控性具有重要的理论意义。此外，复杂网络能控性的研究也具有重要的现实意义。例如，在基因调控网络［8］中，选择哪些基因作为药物靶点，能使整个生物网络达到预期状态；在社交网络里［9］，选择哪些平台发布信息，能使信息的传播达到期望结果。很多实际网络都涉及复杂网络能控性问题。

为使复杂网络完全能控，将线性系统能控性理论应用到复杂网络。2011年，Liu等［10］提出一种求解复杂网络能控性所需的最少驱动节点数目的方法，该方法采用图论的匹配定理［11-12］，将复杂网络的能控性问题转换为有向网络的最大匹配问题，从而建立关于复杂网络可控性的理论研究框架。然而对于无向网络的能控性问题该方法并不适用。因此，Yuan等［13］通过采用PBH能控性判据提出复杂网络精确能控性的理论框架，可求解有边权重和任意结构网络的能控性。基于这两个框架，许多学者对时变网络能控性［14］，多层网络能控性［15］，对称网络结构能控性［16］等方面进行了深入研究。

随着研究的深入，人们发现网络拓扑结构对复杂网络的能控性有重要影响。网络拓扑结构变化分为节点或边的变化，其中节点的变化会造成边数目的变化，边的变化不会造成节点数目的变化。因此边的变化对网络能控性的变化更易判断，而目前边变化的研究包括边变换对网络能控性优化和边的失效。对于边变换对网络能控性优化主要从以下3种方法考虑［17］：增加边［18-22］、交换边［23］、转换边（改变边的方向）［24-26］。Zhang等［21］提出了一种增加边的算法，利用给出的最小生成森林使网络加边的成本最小，该算法使网络增加边的数目最少并实现网络的结构能控。Wang等［22］给出一种网络加边的优化算法，该算法将介数中心性作为网络加边的成本，使加边成本最小且实现网络结构能控。Rong等［23］提出一种在保持度分布不变的约束下重新布线的算法，该算法可改变网络能控性并提高网络的鲁棒性。Hou等［24］提出一种基于匹配边的节点和边的分类方法，在此基础上提出一种转换边的算法，该算法通过局部信息来改变网络的能控性，而且网络的优化成本大幅度降低，比如电力网络［27］。对于边的失效，Hao等［28］根据节点和无标度网络的特征，提出了14种基于两条边重要性函数的边攻击策略，使网络能控性降低。Lou等［29］给出一种边的分类方法，根据该边的分类对网络的边进行攻击，从而实现网络能控性改变。此外，还有许多研究通过边的变化改变网络拓扑结构，从而对网络能控性造成影响。

综上所述，发现当前通过边的变化实现对网络能控性影响的研究主要集中在边失效对网络能控性影响和边变换对网络能控性优化上，并未从理论层面出发，给出转换边和增加边对网络能控性的影响。对于整个复杂网络，哪些边转换或在哪些节点间增加边能改变网络能控性，哪些边转换对网络能控性没有影响，至今没有明确的结论。因此，本文为了对此问题进行研究，将网络中边进行分类，并从理论层面给出不同边变换对网络能控性影响的确切结论。首先根据节点类型和边的匹配关系提出一种有向网络的边分类方式，给出边辨识算法，然后研究了有向网络中边转换和节点间增加边对网络能控性的影响，最后通过模型网络和实际网络仿真，分析了不同类型边在网络中的占比并验证了转换边和增加边定理的有效性。

1 复杂网络能控性

考虑一个N个节点的复杂网络，其动力学方程表示为

（1）

其中，x（t）=［x1，x2，…，xN］T表示网络中节点的状态，xj（t）表示第j个节点在t时刻时的状态，A=［aij］∈RN×N为网络的邻接矩阵，其中aij代表节点j作用到节点i的强度，aij＞0表示积极作用，aij＜0表示消极作用，aij=0表示节点j与节点i无连接关系，即节点j不作用到节点i；u（t）=［u1，u2，…，uM］T表示M个输入控制信号在t时刻的输入量；B∈RN×M称为输入矩阵，B表示外部输入节点与内部节点的耦合关系，bij表示输入信号uj（t）与节点i之间的耦合关系。

对于复杂网络系统（1），若存在一个分段连续的u（t），可在有限的时间［t0，tf］内从任意初始状态x（t0）驱动到任何期望的最终状态x（tf），则称此系统的状态是完全能控的。在控制理论中，通过卡尔曼判据判断系统是否完全能控，系统（1）完全能控当且仅当能控性矩阵C=［B，AB，…，AN-1B］是满秩的，即rank（C）=N。因此要使一个给定网络能控，则需要寻找一个输入矩阵B使得能控性矩阵C满秩。当复杂网络节点间不考虑连接强度时，即不考虑矩阵A与B具体权值，仅考虑矩阵中的元素是零或独立自由参数，这时矩阵A与B称为结构化矩阵。如果存在A与B中一组非零值，使得网络是能控的，则称系统（1）为结构能控，也可记为（A，B）结构能控。根据有向边的方向，在下文中将边的起始节点称为头节点，边的结束节点称为尾节点。

对于有向复杂网络G=（V，E），其中V和E为网络的节点集和边集。如果网络边集E的一个子集M中没有两条边共享一个公共的头节点或尾节点，则M称为G的一个匹配。G中边数最多的匹配称为G的最大匹配。最大匹配一般是非唯一的，可由Hopcroft-Karp算法［30］得到。如果一个节点是匹配中某条边的尾节点，则该节点为匹配节点，否则为非匹配节点。对于网络节点i，从网络中其他节点指向节点i的边数目是节点i的入度，节点i指向其他节点的边数目是节点i的出度。

Liu等［10］把图论中匹配理论与结构能控性相结合，给出一种求解最小驱动节点集分析复杂网络能控性的理论框架，并给出最小输入定理，证明了实现网络结构能控所需独立控制的节点集合等于非最大匹配的节点集合，其中需要被不共享输入信号控制的节点称为网络的驱动节点，驱动节点数目用ND表示，使得网络结构能控所需的最小驱动节点集合为最小驱动节点集（Minimum Driven Node Set，简称MDS），通过对MDS中节点施加外部输入控制信号可使控制信息传达到网络中每一个节点，实现整个网络的完全能控。

引理1 最小输入定理［10］：控制有向网络G的最小输入节点数NI与最小驅动节点数目ND等价。若有向网络G存在完全匹配，NI等于1并且网络中任意一个节点可作驱动节点；否则，NI等于网络中最大匹配后没有被匹配的节点数。用式（2）表示：

（2）

其中，N为有向网络中节点数目，|M|为网络中最大匹配节点数目。

网络的能控性nD的大小由网络所需的最小驱动节点数与网络节点总数的比值来计算，即nD=ND/N，nD的大小表示该网络被控的难易程度，nD越小，网络越易被控制，nD越大，网络越难被控制。

有向网络中，若实现网络完全能控，需对个数固定的未匹配节点进行控制。但是由于一个网络存在多组不同最大匹配，使网络有很多不同的MDS。根据节点参与MDS的程度，将节点分为三类，定义［31］如下：

定义1 如果一个节点参与全部的MDS，则这个节点为关键节点；如果一个节点不全参与全部的MDS，则这个节点为间歇节点；如果一个节点不参与任何一个MDS，则这个节点为冗余节点。

对于图1d网络，存在3组最大匹配和MDS，如图1a、1b和1c所示。其中节点1参与全部MDS，故为关键节点；节点2不参与任何一个MDS，故为冗余节点；节点3，4，5参与部分MDS，故为间歇节点。

2 边分类及类型辨识

2.1 边的分类方式

有向网络中，节点的类型有所不同，节点间通过有向边连接，网络中边的最大匹配也是非唯一的，故参与最大匹配的边也存在不同。根据边匹配关系与边两端节点的类型将边进行分类。

类型1 关键输出完全匹配和冗余输入完全匹配边：如果该边的头节点为关键节点，尾节点为冗余节点，并且该边参与全部最大匹配，则这个边称为关键输出完全匹配和冗余输入完全匹配边（Critical Output Matching and Redundant Input Matching，简称COM-RIM）。

类型2 间歇输出完全匹配和冗余输入完全匹配边：如果该边的头节点为间歇节点，尾节点为冗余节点，并且该边参与全部最大匹配，则这个边称为间歇输出完全匹配和冗余输入完全匹配边（Intermittent Output Matching and Redundant Input Matching，简称IOM-RIM）。

类型3 冗余输出完全匹配和冗余输入完全匹配边：如果该边的头节点为冗余节点，尾节点为冗余节点，并且该边参与全部最大匹配，则这个边称为冗余输出完全匹配和冗余输入完全匹配边（Redundant Output Matching and Redundant Input Matching，简称ROM-RIM）。

类型4 关键输出不完全匹配和冗余输入不完全匹配边：如果该边的头节点为关键节点，尾节点为冗余节点，并且该边参与部分最大匹配，则这个边称为关键输出不完全匹配和冗余输入不完全匹配边（Critical Output No Perfect Matching and Redundant Input No Perfect Matching，简称COOPM-RIOPM）。

类型5 间歇输出不完全匹配和冗余输入不完全匹配边：如果该边的头节点为间歇节点，尾节点为冗余节点，并且该边参与部分最大匹配，则这个边称为间歇输出不完全匹配和冗余输入不完全匹配边（Intermittent Output No Perfect Matching and Redundant Input No Perfect Matching，简称IOOPM-RIOPM）。

类型6 冗余输出不完全匹配和冗余输入不完全匹配边：如果该边的头节点为冗余节点，尾节点为冗余节点，并且该边参与部分最大匹配，则这个边称为冗余输出不完全匹配和冗余输入不完全匹配边（Redundant Output No Perfect Matching and Redundant Input No Perfect Matching，简称ROOPM-RIOPM）。

类型7 关键输出不完全匹配和间歇输入不完全匹配边：如果该边的头节点为关键节点，尾节点为间歇节点，并且该边参与部分最大匹配，则这个边称为关键输出不完全匹配和间歇输入不完全匹配边（Critical Output No Perfect Matching and Intermittent Input No Perfect Matching，简称COOPM-IIOPM）。

类型8 间歇输出不完全匹配和间歇输入不完全匹配边：如果该边的头节点为间歇节点，尾节点为间歇节点，并且该边参与部分最大匹配，则这个边称为间歇输出不完全匹配和间歇输入不完全匹配边（Intermittent Output No Perfect Matching and Intermittent Input No Perfect Matching，简称IOOPM-IIOPM）。

类型9 冗余輸出不完全匹配和间歇输入不完全匹配边：如果该边的头节点为冗余节点，尾节点为间歇节点，并且该边参与部分最大匹配，则这个边称为冗余输出不完全匹配和间歇输入不完全匹配边（Redundant Output No Perfect Matching and Intermittent Input No Perfect Matching，简称ROOPM-IIOPM）。

类型10 关键输出不匹配和冗余输入不匹配边：如果该边的头节点为关键节点，尾节点为冗余节点，并且该边不参与任意一个最大匹配，则这个边称为关键输出不匹配和冗余不完全匹配边（Critical Output No Matching and Redundant Input No Matching，简称COOM-RIOM）。

类型11 间歇输出不匹配和冗余输入不匹配边：如果该边的头节点为间歇节点，尾节点为冗余节点，并且该边不参与任意一个最大匹配，则这个边称为间歇输出不匹配和冗余输入不匹配边（Intermittent Output No Matching and Redundant Input No Matching，简称IOOM-RIOM）。

类型12 冗余输出不匹配和冗余输入不匹配边：如果该边的头节点为冗余节点，尾节点为冗余节点，并且该边不参与任意一个最大匹配，则这个边称为冗余输出不匹配和冗余输入不匹配边（Redundant Output No Matching and Redundant Input No Matching，简称ROOM-RIOM）。

对于图2a和2b网络，对应二分网络如图3a和3b所示，根据边分类可知，边（1→2）参与全部最大匹配，且节点1为关键节点，节点2为冗余节点，所以边（1→2）为COM-RIM边。同理边（1→3）为COOM-RIOM边，边（2→3）、（6→7）、（16→18）和（18→17）为ROM-RIM边，边（3→4）和（3→5）为ROOPM-IIOPM边，边（4→8）、（5→6）和（20→19）为IOM-RIM边，边（5→7）为IOOM-RIOM边，边（8→9）为ROOPM-RIOPM边，边（10→9）为COOPM-RIOPM边，边（11→12）和（11→20）为IOOPM-IIOPM边，边（13→11）和（13→14）为COOPM-IIOPM边，边（14→16）为IOOPM-RIOPM边，边（15→16）为COOPM-RIOPM边，边（16→17）为ROOM-RIOM边。

2.2 边辨识算法

为研究转换边和增加边对网络能控性的影响，需先对网络边类型进行辨识。本节给出辨识网络边类型的算法，流程图如图4所示。具体步骤为：

步骤1：识别网络的最大匹配边数m和网络总边数L，并令参数a=0。

步骤2：将网络节点编号，记为y1，y2，…yN（N为网络节点数目）。选择网络中一条边（yi→yj），去除该边后，识别新网络最大匹配边数m1，判断是否满足m1=m-1，若不满足，则跳至步骤3；否则跳至步骤4。

步骤3：去除节点yi的输入边和节点yj的输出边后，识别新网络的最大匹配边数m2，判断是否满足m2=m-1，若不满足，则跳至步骤6；否则跳至步骤5。

步骤4：边（yi→yj）为完全匹配边。判断节点yi是否存在输入边，若节点yi不存在输入边，则该边为COM-RIM边；若存在，则去掉节点yi的输入边，识别新网络最大匹配边数m3，若满足m3=m-1，则该边为ROM-RIM边；否则为IOM-RIM边。

步骤5：边（yi→yj）为不匹配边。判断节点是否存在输入边，若节点yi不存在输入边，则该边为COOM-RIOM边；若存在，则去除节点yi的输入边，识别新网络的最大匹配边数m4，若满足m4=m-1，则该边为ROOM-RIOM边；否则为IOOM-RIOM边。

步骤6：边（yi→yj）为不完全匹配边。判断节点yi是否存在输入边，若不存在输入边，则跳至步骤7；若存在输入边，则跳至步骤8。

步骤7：节点yi为关键节点，去除节点yj的输入边，识别新网络的最大匹配边数m5，若满足m5=m-1，则节点yj为冗余节点，而边（yi→yj）为COOPM-RIOPM边；若不满足m5=m-1，则节点为间歇节点，边（yi→yj）为COOPM-IIOPM边。

步骤8：去除节点yi的输入边，识别新网络的最大匹配边数m6，若满足m6=m-1，则跳至步骤9；若不满足m6=m-1，则跳至步骤10。

步骤9：节点yi为冗余节点，然后去除节点yj的输入边，并识别新网络的最大匹配边数m7，若满足m7=m-1，则节点yj为冗余节点，边（yi→yj）为ROOPM-RIOPM边；若不满足m7=m-1，则节点为间歇节点，而边（yi→yj）为ROOPM-IIOPM边。

步骤10：节点yi为间歇节点，然后去除节点yj的输入边，识别新网络的最大匹配边数m8，若满足m8=m-1，则节点yj为冗余节点，边（yi→yj）为IOOPM-RIOPM边；若不满足m8=m-1，则节点yj为间歇节点，边（yi→yj）为IOOPM-IIOPM边。

步骤11：若a＜L，则a=a+1，返回步骤2；否则结束操作。

3 转换边与增加边对网络能控性的影响

3.1 转换边对网络能控性的影响

对于有向网络，转换不同的边对网络能控性有不同的影响。考虑到转换边的现实意义，本节给出边转换使网络驱动节点数目减少和不变的变化规律。

定理1 对于N个节点的有向网络，转换一条边类型为COOM-RIOM、IOOM-RIOM、COOPM-RIOPM、IOOPM-RIOPM，如果该边尾节点出度为0；或转换一条边类型为COOPM-IIOPM、IOOPM-IIOPM，如果该边尾节点出度为0且入度为1，则网络中的最大匹配数增加1，驱动节点数减少1。

证明：设网络有N个节点，最大匹配边为L，由二分图得到最大匹配中被匹配的节点个数为M，最小驱动节点数目为ND=N-M，转换边后的最小驱动节点数目为ND′。对于COOPM-RIOPM边或COOM-RIOM边，原头节点是关键节点，转换边后，被原尾节点匹配，变为冗余节点。原尾节点为冗余节点，转换边后，被其它节点匹配，故被匹配节点数目为M+1，驱动节点数目变为ND′=N-（M+1）=N-M-1=ND-1，驱动节点数目减少1。对于IOOM-RIOM边或IOOPM-RIOPM边，原头节点是间歇节点，转换边后，被原冗余节点匹配，变为冗余节点。原尾节点为冗余节点，转换边后，仍被其他节点匹配，故被匹配的节点数目为M+1，驱动节点数目变为ND′=N-（M+1）=N-M-1=ND-1，驱动节点数目减少1。对于COOPM-IIOPM边或IOOPM-IIOPM边，原头节点为关键节点或间歇节点，转换边后，被原尾节点匹配，变为冗余节点。原尾节点为间歇节点且出度为0，转换边后，变为关键节点，而同头节点下的其他间歇节点必会有一个被匹配，故被匹配节点数目为M+1，驱动节点数目为ND′=N-（M+1）=N-M-1=ND-1，驱动节点数目减少1。

定理2 对于N个节点有向网络，转换一条边类型为COM-RIM、ROOM-RIOM、ROOPM-RIOPM、IOM-RIM，如果该边尾节点出度为0；或转换一条ROOPM-IIOPM边，如果该边尾节点出度为0且入度为1；或转换一条ROM-RIM边，如果该边尾节点出度为0且入度为2，则网络中最大匹配数不增加，驱动节点数也不改变。

证明：设网络有N个节点，最大匹配边为L，由二分图得到最大匹配中被匹配的节点个数为M，驱动节点个数为ND=N-M，转换边后的最小驱动节点数目为ND′。对于ROM-RIM边、ROOM-RIOM边或ROOPM-RIOPM边，原头节点为冗余节点，转换边后，被原尾节点匹配。原尾节点为冗余节点，存在其他节点匹配该尾节点，转换边后，仍被其他节点匹配，故网络中被匹配节点数目为M，驱动节点数目为ND′=N-M=ND，驱动节点的数目不变。对于COM-RIM边、IOM-RIM边或ROOPM-IIOPM邊，原头节点为关键节点、间歇节点或冗余节点，转换边后，被原尾节点匹配。原尾节点为间歇节点或冗余节点且出度为0，转换边后，不被匹配，变为关键节点，故网络中被匹配节点数目为M，驱动节点数目为ND′=N-M=ND，驱动节点数目保持不变。

3.2 增加边对网络能控性的影响

对于有向网络，在不同节点间增加边对网络能控性有不同的影响。考虑到增加边的现实意义，本节将给出增加边使网络驱动节点数目减少的变化规律。

定理3 对于N个节点的有向网络，考虑以下情况时，网络最大匹配数增加1，驱动节点数减少1。1）在COOPM-IIOPM边、IOOPM-IIOPM边、ROOPM-IIOPM边的尾节点之间增加一条边l1，如果l1的头节点出度为1；2）在COOPM-RIOPM边、IOOPM-RIOPM边的头节点与COOPM-RIOPM边、IOOPM-RIOPM边、ROOPM-RIOPM边的头节点之间增加一条边l2，如果l2的尾节点为关键节点或间歇节点；3）在出度为0的边尾节点与边类型为COM-RIM、COOM-RIOM、COOPM-IIOPM或COOPM-RIOPM的头节点间增加一条边l3。