第4期 陈世明，等：有向相依网络的可控性研究 ·603· 的研究得到了充分的关注与重视。Lin给出了线 响，却未考虑到实际网络中存在有向网络相互依 性时不变控制系统“结构”和“结构可控性”的概 存的情况，例如在交通网络与供电网络中，某 念，并通过研究找到了结构可控性的充要条件； 时间内列车的运行方向是定向的，同时供电系统 Lu等基于线性时不变控制系统的结构可控性 按照列车运行的线路提供电力支持保证其正常运 理论，对实际复杂系统进行了研究并建立了网络 行。在供电网络中某一处发生故障会通过网络之 结构可控性模型：Jia6发现了两种不同的网络控 间的相依关系，将其传递到交通网络中从而导致 制模式：集中式控制和分布式控制；同时基于控 经过这条线路的列车都无法运行，反之亦然。这 制能力和随机抽样算法对有向复杂网络的结构可 样在某个网络中产生的故障会因为彼此间的相依 控性做了进一步探索，随后一些研究者通过改变 关系，使得故障在两个网络之间相互蔓延，从而 连接边的方向实现了网络可控性的优化⑧1。目 对网络造成更大的破坏，由此表明有向相依网络 前复杂网络可控性研究已经取得了众多的重要成 间的相依关系对整个有向相依网络有重要影响。 果，但复杂网络控制方面的研究仍然处于起步阶 为了探究有向网络间相依关系对网络的影响，本 段，还有很多未解决的理论问题，例如结构可控 文首先构建了基本的有向相依网络模型，并结合 性理论无法适用于无向网络、权重网络和时变网 严格可控性理论，给出了基于最少控制输人的可 络的可控性等问题。针对结构可控性理论仅适用 控性评判指标；其次，针对相依方式对有向相依 于有向网络的局限性，Yuan引入了严格可控性 网络可控性产生的影响，基于经典的有向随机网 (exact controllability)的概念，证明完全控制复杂 络(DER)和有向无标度网络(DSF),构建了DER 网络所需的最少控制器数目由网络矩阵特征值的 DER、DER-DSF、DSF-DSF3类有向相依网络模 最大重数决定，并提出了利用矩阵初等变换甄别 型，并研究了随机相依方式下3类网络的可控性 网络中需要被独立控制的节点的方法，通过对大 能：最后，基于随机相依方式下对网络可控性的 量真实网络和模型网络的计算结果表明了严格可 分析，提出了3种有向网络的相依方式：最高入度 控性理论的有效性和实用性；L针对实际网络 与最高出度节点相依(H-HO)、最高入度与最低 的分型特征，运用严格可控性理论对分型网络的 出度节点相依(HⅡ-LO)、最低入度与最低出度节 可控性进行了分析。基于单层有向网络和无可控 点相依(LI-LO),且在既定的3种相依方式下对网 络的可控性进行了仿真分析。 性进行的研究已取得了较大突破。但现实中的网 络通常是相互依存的，例如，公交-地铁网络、电 1有向相依网络可控性 力-通信网络、电力-供水网络等，且通过研究已 经发现相依网络的动态特性如级联失效1刃、扩 1.1有向相依网络 散现象11、演化博弈动力学9、同步性20等，均明 有向相依网络由两个有向子网络（子网络A 显区别于单层网络。怎样合理地控制相依网络将 和子网络B)通过双向连接线连接而成，{A1,A2,…, 是面临的重要挑战。Yuan运用严格可控性理论 Aw}表示子网络A中的节点，节点数为NA:{B,B2,·,Bw} 对多重网络的可控性进行了研究，发现在多关系 表示子网络B中的节点，节点数为Na,子网络之 网中存在主导关系网，其结构和连接权重对于整 间的双向连接线为网络相依边，其余单向连线为 内部边。F表示节点相依比例。F包括Fa和F, 个网络的严格可控性起主导作用；在多层网中， 其中Fa表示子网络A的相依节点数N以占子网络 不同层间的连接方式以及疏密程度对整个网络的 A总节点数Na的比例值，F表示子网络B的相依 严格可控能力都有重要的影响，并且发现在层间 节点数N占子网络B总节点数Ns的比例值，即 加入少量连接能够大大提高整个网络的可控能 FA=N/NA 力。Ni22分析了多层网络中层间连边结构对网 F8=Ni/Ng (1) 络可控性能的影响，研究发现层间连边比例较小 本文仅考虑相依子网络节点数相同的情况， 时，网络最少驱动节点的数目随着连边度相关性 即Na=Ng,且网络为单相依，则有N=N,即FA= 的增加而减小，层间连边同配性强的网络易于控 FB=F。 制；当层间连边比例较大时，则会出现相反的情 如图1所示，定义了简单的有向相依网络模 况，层间连边异配性强的网络易于控制。然而以 型，NA=N6=5,N以=NM=4,FA=FB=0.8,单向箭 上研究仅分析了网络层间的连接方式及网络层间 头实线表示子网络内部连接边，黑色双箭头虚线 连接边的度相关性对无向相依网络可控性的影 表示子网络间的连接线，即网络相依边。的研究得到了充分的关注与重视。Lin[4]给出了线 性时不变控制系统“结构”和“结构可控性”的概 念，并通过研究找到了结构可控性的充要条件； Liu 等 [5]基于线性时不变控制系统的结构可控性 理论，对实际复杂系统进行了研究并建立了网络 结构可控性模型；Jia[6-7]发现了两种不同的网络控 制模式：集中式控制和分布式控制；同时基于控 制能力和随机抽样算法对有向复杂网络的结构可 控性做了进一步探索，随后一些研究者通过改变 连接边的方向实现了网络可控性的优化[8-10]。目 前复杂网络可控性研究已经取得了众多的重要成 果，但复杂网络控制方面的研究仍然处于起步阶 段，还有很多未解决的理论问题，例如结构可控 性理论无法适用于无向网络、权重网络和时变网 络的可控性等问题。针对结构可控性理论仅适用 于有向网络的局限性，Yuan[11]引入了严格可控性 (exact controllability) 的概念，证明完全控制复杂 网络所需的最少控制器数目由网络矩阵特征值的 最大重数决定，并提出了利用矩阵初等变换甄别 网络中需要被独立控制的节点的方法，通过对大 量真实网络和模型网络的计算结果表明了严格可 控性理论的有效性和实用性；Li[12]针对实际网络 的分型特征，运用严格可控性理论对分型网络的 可控性进行了分析。基于单层有向网络和无可控 性进行的研究已取得了较大突破。但现实中的网 络通常是相互依存的，例如，公交–地铁网络、电 力–通信网络、电力–供水网络等，且通过研究已 经发现相依网络的动态特性如级联失效[13-17] 、扩 散现象[18] 、演化博弈动力学[19] 、同步性[20]等，均明 显区别于单层网络。怎样合理地控制相依网络将 是面临的重要挑战。Yuan[21]运用严格可控性理论 对多重网络的可控性进行了研究，发现在多关系 网中存在主导关系网，其结构和连接权重对于整 个网络的严格可控性起主导作用；在多层网中， 不同层间的连接方式以及疏密程度对整个网络的 严格可控能力都有重要的影响，并且发现在层间 加入少量连接能够大大提高整个网络的可控能 力。Nie[22]分析了多层网络中层间连边结构对网 络可控性能的影响，研究发现层间连边比例较小 时，网络最少驱动节点的数目随着连边度相关性 的增加而减小，层间连边同配性强的网络易于控 制；当层间连边比例较大时，则会出现相反的情 况，层间连边异配性强的网络易于控制。然而以 上研究仅分析了网络层间的连接方式及网络层间 连接边的度相关性对无向相依网络可控性的影 响，却未考虑到实际网络中存在有向网络相互依 存的情况，例如在交通网络与供电网络中，某一 时间内列车的运行方向是定向的，同时供电系统 按照列车运行的线路提供电力支持保证其正常运 行。在供电网络中某一处发生故障会通过网络之 间的相依关系，将其传递到交通网络中从而导致 经过这条线路的列车都无法运行，反之亦然。这 样在某个网络中产生的故障会因为彼此间的相依 关系，使得故障在两个网络之间相互蔓延，从而 对网络造成更大的破坏，由此表明有向相依网络 间的相依关系对整个有向相依网络有重要影响。 为了探究有向网络间相依关系对网络的影响，本 文首先构建了基本的有向相依网络模型，并结合 严格可控性理论，给出了基于最少控制输入的可 控性评判指标；其次，针对相依方式对有向相依 网络可控性产生的影响，基于经典的有向随机网 络 (DER) 和有向无标度网络 (DSF)，构建了 DER￾DER、DER-DSF、DSF-DSF 3 类有向相依网络模 型，并研究了随机相依方式下 3 类网络的可控性 能；最后，基于随机相依方式下对网络可控性的 分析，提出了 3 种有向网络的相依方式：最高入度 与最高出度节点相依 (HI-HO)、最高入度与最低 出度节点相依 (HI-LO)、最低入度与最低出度节 点相依 (LI-LO)，且在既定的 3 种相依方式下对网 络的可控性进行了仿真分析。 1 有向相依网络可控性 1.1 有向相依网络 {A1,A2,··· , AN} NA {B1,B2,··· ,BN} NB FA FB FA N I A NA FB N I B NB 有向相依网络由两个有向子网络 (子网络 A 和子网络 B) 通过双向连接线连接而成， 表示子网络A中的节点，节点数为 ； 表示子网络 B 中的节点，节点数为 ，子网络之 间的双向连接线为网络相依边，其余单向连线为 内部边。F 表示节点相依比例。F 包括 和 ， 其中 表示子网络 A 的相依节点数 占子网络 A 总节点数 的比例值， 表示子网络 B 的相依 节点数 占子网络 B 总节点数 的比例值，即 FA = N I A /NA FB = N I B /NB (1) NA = NB N I A = N I B FA = FB = F 本文仅考虑相依子网络节点数相同的情况， 即 ，且网络为单相依，则有 ，即 。 NA = NB = 5 N I A = N I A = 4 FA = FB = 0.8 如图 1 所示，定义了简单的有向相依网络模 型 ， ， ， ，单向箭 头实线表示子网络内部连接边，黑色双箭头虚线 表示子网络间的连接线，即网络相依边。 第 4 期 陈世明，等：有向相依网络的可控性研究 ·603·