-
摘要: 复杂系统间的相互作用能够用复杂网络描述. 复杂网络中某些节点遭受攻击或破坏会造成网络故障, 导致整个网络能控性变化. 不同节点失效会对网络能控性有不同的影响. 本文提出一种网络节点的分类方式, 将网络中的节点根据边的方向和匹配关系分成九种类型, 并给出了辨识节点类型的算法. 另外, 本文给出了基于此分类方式下复杂网络中某类节点失效时, 网络中驱动节点数量(用来衡量网络能控性大小的指标)的变化规律. 并通过模型网络进行仿真实验, 验证了当节点失效时本文给出的驱动节点数量变化情况, 同时还分析社交网络中不同类型节点的占比与实际中人际交往的对应关系.Abstract: The interaction between complex systems can be described by complex networks. In complex network, some nodes are attacked or destroyed, which may cause network failure and lead to the change of the whole network controllability. Different node failures have different effects on network controllability. In this paper, a classification method of network nodes is proposed, which divides the nodes into nine types according to the direction of the edge and the matching relationship, and the algorithm for identifying the type of nodes is given. In addition, the change rule of the number of driving nodes is given when a certain type of node fails in the complex network based on this classification method, which is used to measure the controllability of the network. And simulation experiments are carried out through the model network to demonstrate the change of the number of driving nodes given in this paper when the node fails. At the same time, the corresponding relationship between the proportion of different types of nodes in social networks and actual interpersonal communication is also analyzed.
-
Key words:
- Complex networks /
- network controllability /
- nodes failure /
- driver node
-
近年来, 随着科学技术的发展, 人们已经认识到各种复杂系统是由相互作用和相互依赖的若干部分组成的具有特定功能的有机整体. 而网络是由节点和连接节点的边所组成的. 如果用节点表示系统的各个组成部分, 两节点之间的边表示各个组成部分之间的相互作用, 那么网络就为研究复杂系统提供了一种新的描述方式[1-5]. 例如神经系统可以看作是由神经细胞通过神经纤维相互连接形成的网络[2]; 计算机网络可以看作是自主工作的计算机通过通信介质(如光缆、同轴电缆等)相互连接形成的网络[3]; 人际关系网是将每一个人作为一个节点, 如果两个人之间存在某种关系(比如相识)就连一条边[4]; 类似的还有电力网络和交通网络等.
复杂网络研究的近年来受到了许多关注, 其最终目标是寻找有效的策略来控制网络的行为使其为人类服务[6-7]. 许多学者对复杂网络的控制算法进行了研究, 并取得了丰硕的成果, 如牵制控制[8-11], 自适应控制[12-13], 同步控制及存在延时的网络系统同步[14-19], 最优滤波[20]等方法都已应用于网络中. 然而对网络进行控制算法应用的前提条件是此网络系统必须是能控的. 另外, 现实世界中很多复杂的系统问题也可以抽象为网络能控性问题. 例如, 在错综复杂的基因调控网络中, 如何选择最有效的基因节点作为药物的靶标, 使得整个生物体网络系统朝着预期的良好状态发展; 在电力网络中, 如何优化网络的拓扑结构使得可以用最少的变电站就能够控制整个地区的电力供应; 在计算机网络中, 当部分计算机遭遇黑客袭击后, 如何重新选择控制节点保证整个计算机系统的正常运转. 对于线性系统能控性的基础理论已较为成熟, 并广泛应用于工程中. 然而, 要把传统的线性系统结构能控性理论直接应用到复杂系统或者复杂网络中却存在诸多困难. 如何选择一部分节点控制整个复杂网络, 首要问题是需要多少外界输入信号才能使网络达到期望状态, 也就是满足能控性条件的控制器的最少个数是多少. 2011年, Liu等[21]在Nature上发表了关于复杂网络结构能控性的论文通过引入图论中的匹配理论得到了求解最少输入信号和驱动节点的最少(最小)输入定理, 建立复杂网络能控性研究框架. Yuan 等[22]从PBH能控性判据出发提出了求解网络严格能控性的理论框架, 可用于求解具有确定性边权和任意结构的网络的能控性. 许多学者在这两个框架下研究了时变网络的能控性[23]、深度耦合动态网络的能控性[24]、对称网络结构能控性[25]、具有对抗相互作用的多智能体网络的能控性[26]和多层网络的能控性[27]等问题, 这些研究大大提高了人们对网络能控性问题的认识.
现实生活中, 网络某些节点遭到攻击或发生故障失效, 可能会导致整个网络失控, 例如互联网络中某个计算机或服务器发生故障可能导致互联网络瘫痪; 电力网络中某个电站或变压器发生故障可能会导致电力系统瘫痪等. 网络中不同节点失效时, 对整个网络功能的影响是不同的. Pu等[28]研究了单一节点攻击和级联失效两种攻击模式下网络可控性的影响, 结果表明基于度的攻击方式都比随机攻击对网络能控性的影响更大. Liu等[29]提出了一种随机上游攻击策略来破坏有向网络的结构能控性, 该策略移除随机选择的点的上游节点, 相较于依据节点度的攻击策略, 该策略不需要知道网络全局的拓扑结构信息. Lu等[30]研究了边失效对网络能控性的影响, Pu等[31]研究了最长简单路径失效时网络能控性的影响, 以上研究说明当失效边介数越大或失效时简单路径越长, 对网络能控性的影响更大.
综上所述, 可以发现当前节点失效对网络能控性的影响的研究主要集中在部分节点或者边失效对网络能控性的影响上, 主要针对具有某种结构特征的节点或边通过实验和仿真等手段给出结论, 并未从理论层面给出节点失效对网络能控性的影响. 对于整个网络而言, 不同类型的节点对网络能控性的影响也不相同: 有些节点失效网络能控性会增加, 有些节点失效网络的能控性保持不变, 有些节点失效网络能控性会降低. 哪些节点失效对网络能控性有何影响, 至今未有明确结论. 因此, 本文为了研究此问题将网络节点进行分类, 并从理论层面给出不同类型的节点对网络能控性影响的确切结论. 首先根据边的方向和匹配关系提出一种网络节点的分类方式, 将网络中的节点分成九种类型, 并给出了辨识节点类型的算法, 然后研究了复杂网络中某类节点失效对网络能控性有何影响, 给出了节点失效后网络能控性的变化规律, 最后通过仿真实验验证上述规律的有效性.
1. 复杂网络能控性
考虑一个具有
$ N $ 个节点的复杂网络, 其动力学方程表示为$$ {\dot{\boldsymbol{x}}} = {{\boldsymbol{{A}x}(t)}}+{{\boldsymbol{{B}u}(t)}} $$ (1) 其中
${{\boldsymbol{x}}(t)} = [{{\boldsymbol{x}}_{1}},{{\boldsymbol{x}}_{2}},\cdots,{{\boldsymbol{x}}_{N}}]^{\rm T}$ 表示网络中节点的状态,$ {{\boldsymbol{x}}_{j}(t)} $ 表示第$ j $ 个节点在$ t $ 时刻时的状态;${\boldsymbol{A}} = $ $ [a_{ij}]\in {\bf{R}}^{N\times N}$ 为网络邻接矩阵, 其中$ a_{ij} $ 代表节点$ j $ 影响节点$ i $ 的强度,$ a_{ij}>0 $ 表示这种影响是积极,$ a_{ij}<0 $ 表示这种影响是消极的, 若$ a_{ij} = 0 $ 表示从节点$ j $ 到节点$ i $ 没有连接关系, 即节点$ j $ 不影响节点$ i $ ;${{\boldsymbol{u}}(t)} = [{{\boldsymbol{u}}_{1}},{{\boldsymbol{u}}_{2}},\cdots,{{\boldsymbol{u}}_{M}]}$ 表示$ M $ 个输入控制信号在$ t $ 时刻的输入量;$ {{\boldsymbol{B}}}\in {\bf{R}}^{N\times M} $ 称为输入矩阵, 表示外部输入节点与内部节点的耦合关系,$ b_{ij} $ 表示输入信号$ u_{j}(t) $ 与节点$ i $ 之间的耦合连接.对于复杂网络系统(1), 若存在一个分段连续的
$ {{\boldsymbol{u}}(t)} $ , 可在有限的时间内$ [t_{0},t_{f}] $ 从任意初始状态$ x(t_{0}) $ 驱动到任意期望的终端状态$ x(t_{f}) $ , 则称此系统的状态是完全能控. 在控制理论中, 判断系统是否完全能控可通过卡尔曼判据, 对于系统(1)完全能控当且仅当能控性矩阵${{\boldsymbol{C}}} = [{{\boldsymbol{B}}},{{\boldsymbol{A}}}{{\boldsymbol{B}}},\cdots, {{\boldsymbol{A}}}^{N-1}{{\boldsymbol{B}}}]$ 是满秩的, 即$$ {\rm rank}({{\boldsymbol{C}}}) = N $$ (2) 因此要使一个给定网络能控需要寻找一个输入矩阵
$ {{\boldsymbol{B}}} $ 使得能控性矩阵$ {{\boldsymbol{C}}} $ 满秩.当复杂网络节点间不考虑连接强度时, 即不考虑矩阵
$ {{\boldsymbol{A}}} $ 与$ {{\boldsymbol{B}}} $ 具体数值, 仅考虑矩阵中的元素是零或为独立自由参数, 这时矩阵$ {{\boldsymbol{A}}} $ 与$ {{\boldsymbol{B}}} $ 称为结构矩阵. 如果存在$ {{\boldsymbol{A}}} $ 与$ {{\boldsymbol{B}}} $ 中一组非零取值, 使得网络是能控的, 则称系统(1)为结构能控, 也可记为$ ({{\boldsymbol{A}}},{{\boldsymbol{B}}}) $ 结构能控.对于有向复杂网络
$ G = (V, E) $ , 其中$ V $ 为网络的节点集,$ E $ 为网络的边集. 如果网络边集$ E $ 的一个子集$ M $ 中没有两条边共享一个公共的起始节点或结束节点, 则$ M $ 称为$ G $ 的一个匹配.$ G $ 中边数最多的匹配称为$ G $ 的最大匹配. 最大匹配一般是非唯一的. 如果一个节点是匹配中某条边的结束节点, 则该节点为匹配节点, 否则, 它为非匹配节点.对任意有网络而言, 它可能存在多组不同的最大匹配. 有向图的最大匹配可以从它的二分图中得出. 如图1(a)所示由6个节点所构成的有向网络. 与它对应的二分图如图1(b)所示, 为
$ H(A) = $ $ (V^{+}_{A},V^{-}_{A},\Gamma) $ .$ V^{+}_{A} $ 和$ V^{-}_{A} $ 是二分图的两个顶点集$V^{+}_{A} = $ $ \{v^{+}_{1}, v^{+}_{2},\cdots,v^{+}_{6}\}$ ,$V^{-}_{A} = \{v^{-}_{1},v^{-}_{2},\cdots,v^{-}_{6}\}$ .$ \Gamma $ 是它的边集, 如果在$ G(A) $ 中节点$ i $ 有边指向节点$ j $ , 则在$ \Gamma $ 中对应$ x^{+}_{i} $ 到$ x^{-}_{j} $ 的有向边. 边数最多的匹配为$\{v^{+}_{1}\to $ $ v^{-}_{4},v^{+}_{3}\to v^{-}_{5}\}$ 或$ \{v^{+}_{1}\to v^{-}_{4},v^{+}_{3}\to v^{-}_{6}\} $ 或$\{v^{+}_{2}\to v^{-}_{4}, $ $ v^{+}_{3}\to v^{-}_{5}\}$ 或$ \{v^{+}_{2}\to v^{-}_{4},v^{+}_{3}\to v^{-}_{6}\} $ 均为两条边$|M| = $ $ 2$ , 所以该网络最大匹配边集共有四组. 将最大匹配$ M $ 中对应的起始节点集记为$ V^{+}_{M} $ , 结束节点集记为$V^{-}_{M}$ . 对于任意一个二分图而言, 它的最大匹配可以通过Hopcroft-Karp算法[32]得出.Liu等[21]通过将图的匹配理论与结构可控性相结合, 提出了一种基于最大匹配算法求解最小驱动节点集的分析复杂网络能控性的理论框架, 并给出最小输入定理, 证明了实现网络结构可控所需独立控制的节点集合等于非最大匹配的节点集合, 其中需要被外部输入施加控制的节点称为网络的驱动节点, 驱动节点个数用
$ N_{D} $ 表示, 通过对这些驱动节点施加外部输入控制信号可使控制信息传达到网络中每一个普通节点, 可实现整个网络的完全能控.引理 1. 最小输入定理[21]:网络的最小输入集等价于最小驱动节点集(
$ N_{D} $ ). 如果网络是完美匹配, 最小输入集是网络中的任意一个节点; 否则, 它等于网络最大匹配后未被匹配的节点集. 用公式表示:$$ N_{D} = \max\{1,N-|M|\} $$ (3) 其中,
$ N $ 为有向网络节点个数,$ |M| $ 为网中最大匹配节点个数.网络能控性大小可由控制网络所需要的最小驱动节点数占总节点数的比例来衡量, 即网络中的驱动节点密度, 记为
$$ n_{D} = N_{D}/N $$ (4) 其大小反映该网络能被控制的难易程度, 控制网络所需的驱动节点数占总节点数的比例越小, 即
$ n_{D} $ 越小, 表明网络越容易实现完全能控, 反之, 控制网络所需的驱动节点数占总节点数的比例越大, 即$ n_{D} $ 越大, 表明网络越难实现完全能控.2. 节点分类辨识及能控性分析
复杂网络中的节点失效会使网络驱动节点数发生变化, 从而影响网络的能控性. 然而, 不同的节点失效, 对网络的能控性的影响也不同. 当哪些节点失效, 驱动节点个数会增加? 哪些节点失效驱动节点数会减少? 针对这个问题, 本节将网络节点进行分类, 研究不同类型节点失效对网络结构可控性有何影响.
2.1 节点分类方式
在有向网络中, 节点与节点之间通过有向边相连. 节点与边的连接存在以下四种关系:
A : 只存在输出边, 不存在输入边的节点. 如图2中节点A所示, 将这类节点构成的集合记为
$ V_{O} $ .B : 只存在输入边, 不存在输出边的节点. 如图2中节点B
所示, 将这类节点构成的集合记为 $ V_{I} $ .C : 既存在输出边又存在输入边的节点. 如图2中节点C所示, 将这类节点构成的集合记为
$ V_{IO} $ .D : 既不存在输出边又不存在输入边的节点. 如图2中节点D所示, 将这类节点构成的集合记为
$ V_{D} $ .对于任意网络而言, 最大匹配一般是非唯一. 因此网络中节点参与最大匹配的可能性也不相同, 可根据匹配关系对原始的网络节点进行分类.
对于属于
$ V_{O} $ 的节点而言, 即节点只包含输出边, 则该类节点一定为最大匹配的起始节点. 可以将其分为以下两种类型:类型 1. 输出完全匹配节点: 如果该节点在所有组的最大匹配中一定是最大匹配边集的起始点, 则这个节点称为输出完全匹配节点(Output matching node, OM), 将这类节点的集合记为
$ V_{OM} $ .类型 2. 输出不完全匹配节点: 如果该节点不是所有组最大匹配边集的起始点, 则这个节点称为输出不完全匹配节点(Output non matching node, ONM), 将这类节点的集合记为
$ V_{ONM} $ .例如图1中, 节点
$ v_{1},v_{2},v_{3} $ 只含输出边不含输入边, 属于$ V_{O} $ . 在四组最大匹配中, 节点$ v_{3} $ 为所有组最大匹配集中匹配边的起始节点, 属于类型1为OM节点. 节点$ v_{1} $ 和$ v_{2} $ 属于某些组最大匹配, 不是所有组最大匹配边集的起始点节点, 所以属于类型2为ONM节点. 这两类节点集存在如下关系,$V_{ONM}\bigcup $ $ V_{OM} = V_{O}\subseteq V_{M}^{+}$ .对于属于
$ V_{I} $ 的节点, 即节点只存在输入边, 则该类节点一定为最大匹配的终止节点, 可以分成以下两种类型:类型 3. 输入完全匹配节点: 如果该节点在所有组的最大匹配中一定是最大匹配边集的终点, 则这个节点为输入完全匹配节点(Input matching node, IM). 将这类节点的集合记为
$ V_{IM} $ .类型 4. 输入不完全匹配节点: 如果该节点不是所有组最大匹配边集的终点, 则这个节点称为输入不完全匹配节点(Input non matching node, INM). 将这类节点的集合记为
$ V_{INM} $ .例如图1中, 节点
$ v_{4},v_{5},v_{6} $ 都属于$ V_{I} $ . 四组最大匹配中, 节点$ v_{4} $ 是所有组最大匹配边集的终点, 所以其类型为IM节点, 属于$ V_{IM} $ . 节点$ v_{5} $ 和$ v_{6} $ 只存在于某些最大匹配中, 不是所有组最大匹配边集的终止节点, 所以其类型为INM, 属于$ V_{INM} $ . 这两类节点集存在如下关系,$ V_{INM}\bigcup V_{IM} = V_{I}\subseteq V_{M}^{-} $ .对于属于
$ V_{IO} $ 的节点, 即当节点既包含输出边又包含输入边时, 根据节点匹配与被匹配的关系, 可分为以下四种类型:类型 5. 输入完全匹配和输出完全匹配节点: 如果该节点在所有组的最大匹配中一定是最大匹配边集的起点也一定是最大匹配边集的终点, 则这个节点为输入完全匹配和输出完全匹配节点(Input matching and output matching node, IM&OM). 将这类节点的集合记为
$ V_{IM\&OM} $ .类型 6. 输入不完全匹配和输出完全匹配节点: 如果该节点在所有组的最大匹配中一定是最大匹配边集的起点, 但不是所有组最大匹配边集的终点, 则这个节点为输入不完全匹配和输出完全匹配节点(Input non matching and output matching node, INM&OM). 将这类节点的集合记为
$ V_{INM\&OM} $ .类型 7. 输入完全匹配和输出不完全匹配节点: 如果该节点不是所有组最大匹配边集的起点, 但在所有组的最大匹配中一定是最大匹配边集的终点, 则这个节点为输入完全匹配和输出不完全匹配节点(Input matching and output non matching node, IM&ONM). 将这类节点的集合记为
$ V_{IM\&ONM} $ .类型 8. 输入不完全匹配和输出不完全匹配节点: 如果该节点不是所有组最大匹配边集的起点, 也不是所有组最大匹配边集的终点, 则这个节点为输入不完全匹配和输出不完全匹配节点(Input non matching and output non matching node, INM&ONM), 将这类节点的集合记为
$ V_{INM\&ONM} $ .这四类节点集存在如下关系:
$V_{IM\&OM}\bigcup $ $V_{INM\&OM}\;\bigcup \; V_{IM\&ONM}\;\bigcup \;V_{INM\&ONM} = V_{IO} $ . 如图3(a)所示的有向网络, 节点$ v_{4},v_{5}, $ $ v_{6} $ 和$ v_{8} $ 属于$ V_{IO} $ 节点. 从该网络的二分图3(b)可知, 该网络最大匹配边集存在以下8种情况.$$ \begin{array}{l} \;\;\;\;\{ v_1^ + \to v_3^ - ,v_2^ + \to v_5^ - ,v_4^ + \to v_6^ - ,v_5^ + \to \\ v_8^ - ,v_6^ + \to v_9^ - \} ;\\ \;\;\;\;\{ v_1^ + \to v_3^ - ,v_2^ + \to v_5^ - ,v_4^ + \to v_6^ - ,v_5^ + \to \\ v_8^ - ,v_8^ + \to v_9^ - \} ;\\ \;\;\;\;\{ v_1^ + \to v_3^ - ,v_2^ + \to v_5^ - ,v_4^ + \to v_7^ - ,v_5^ + \to \\ v_8^ - ,v_6^ + \to v_9^ - \} ;\\ \;\;\;\;\{ v_1^ + \to v_3^ - ,v_2^ + \to v_5^ - ,v_4^ + \to v_7^ - ,v_5^ + \to \\ v_8^ - ,v_8^ + \to v_9^ - \} ;\\ \;\;\;\;\{ v_1^ + \to v_4^ - ,v_2^ + \to v_5^ - ,v_4^ + \to v_6^ - ,v_5^ + \to \\ v_8^ - ,v_6^ + \to v_9^ - \} ;\\ \;\;\;\;\{ v_1^ + \to v_4^ - ,v_2^ + \to v_5^ - ,v_4^ + \to v_6^ - ,v_5^ + \to \\ v_8^ - ,v_8^ + \to v_9^ - \} ;\\ \;\;\;\;\{ v_1^ + \to v_4^ - ,v_2^ + \to v_5^ - ,v_4^ + \to v_7^ - ,v_5^ + \to \\ v_8^ - ,v_6^ + \to v_9^ - \} ;\\ \;\;\;\;\{ v_1^ + \to v_4^ - ,v_2^ + \to v_5^ - ,v_4^ + \to v_7^ - ,v_5^ + \to \\ v_8^ - ,v_8^ + \to v_9^ - \} . \end{array} $$ 节点
$ v_{4} $ 作为起始节点(即$ v_{4}^{+} $ )出现在所有最大匹配集中, 该节点作为终止节点(即$ v_{4}^{-} $ )只存在部分最大匹配中, 所以节点$ v_{4} $ 在所有组的最大匹配中一定是最大匹配边集的起点, 但不是所有组最大匹配边集的终点, 因此节点$ v_{4} $ 类型为INM&OM.对于节点
$ v_{5} $ 而言,$ v_{5}^{+} $ 和$ v_{5}^{-} $ 出现在所有最大匹配情况中. 所以节点$ v_{5} $ 在所有组的最大匹配中一定是最大匹配边集的起点和终点, 因此节点$ v_{5} $ 类型为IM&OM.对于节点
$ v_{6} $ 而言,$ v_{6}^{+} $ 和$ v_{6}^{-} $ 都只存在部分最大匹配情况中, 所以节点$ v_{6} $ 既不是所有组最大匹配边集的起点, 也不是所有组最大匹配边集的终点, 因此节点$ v_{6} $ 类型为INM&ONM.对于节点
$ v_{8} $ 而言,$ v_{8}^{+} $ 只存在部分最大匹配中, 而$ v_{8}^{-} $ 出现在所有最大匹配情况中, 所以节点$ v_{8} $ 不是所有组最大匹配边集的起点, 但在所有组的最大匹配中一定是最大匹配边集的终点, 因此节点$ v_{8} $ 类型为IM&ONM.类型 9. 孤立节点: 当节点既不包含输出边也不包含输入边时, 该节点称为孤立节点(记为
$ V_{D} $ , 见图2). 这类节点在原始中一定既不是最大匹配的起始节点也不是最大匹配的终止节点, 因此如果要实现网络完全能控, 这类节点一定为驱动节点.2.2 节点辨识算法
为了分析不同类型节点对网络可控性的影响, 需要识别网络中节点属于哪一类型. 因此, 本节给出识别出网络中节点类型的算法, 算法流程如图4所示. 具体步骤如下:
步骤 1. 通过Hopcroft-Karp算法[32]识别二分图网络中的最大匹配组.
步骤 2. 选择节点集合中一个节点, 记为
$ v_{i} $ ($ i = 1,2,\cdots,N $ ).$ N $ 为集合中节点个数.步骤 3. 判断节点
$ v_{i} $ 是否存在输入边和输入边.步骤 4. 若只存在输入边, 则跳转步骤5. 若只存在输出边, 则跳转步骤6. 若既存在输出边, 又存在输入边, 则跳转步骤7. 若既不存在输出边又不存在输入边, 则节点类型为孤立节点, 跳转步骤8.
步骤 5. 节点输入边相连的节点为
$ u_{i} $ . 去掉节点$ v_{i} $ 输入边, 以深度优先搜索算法观察是否存在以节点$ u_{i} $ 为起点的增广路径, 若存在, 则节点$ v_{i} $ 为INM, 若不存在, 则节点$ v_{i} $ 为IM.步骤 6. 节点输出边相连的节点为
$ w_{i} $ . 去掉节点$ v_{i} $ 输出边, 以深度优先搜索算法观察是否存在以节点$ w_{i} $ 为终点的增广路径. 若存在, 则节点$ v_{i} $ 为ONM, 若不存在, 则节点$ v_{i} $ 为OM.步骤 7. 节点输入边相连的节点为
$ x_{i} $ . 节点输出边相连的节点为$ y_{i} $ . 去掉节点$ v_{i} $ 输入边和输出边, 以深度优先搜索算法观察是否存在以节点$ x_{i} $ 为起点和以节点$ y_{i} $ 为终点的增广路径.若同时存在以节点
$ x_{i} $ 为起点和以节点$ y_{i} $ 为终点的增广路径, 则节点$ v_{i} $ 为INM&ONM.若只存在以节点为起点
$ x_{i} $ 的增广路径, 不存在以节点$ y_{i} $ 为终点的增广路径. 则节点$ v_{i} $ 为INM&OM.若只存在以节点
$ y_{i} $ 为终点的增广路径, 不存在以节点$ x_{i} $ 为起点的增广路径. 则节点$ v_{i} $ 为IM&ONM.若同时不存在以节点
$ x_{i} $ 为起点和以节点$ y_{i} $ 为终点的增广路径, 则节点$ v_{i} $ 为IM&OM.步骤 8. 若
$ i<N $ ,$ i = i+1 $ , 返回步骤2. 反之结束操作.算法伪代码如下:
1) 通过H-K算法[32]识别二分图网络最大匹配.
2) for i = 1:N do
3) if
$ v_{i} $ 存在输入边 then4) if
$ v_{i} $ 存在输出边 then5) 输入边相连节点记为
$ x_{i} $ , 输出边相连节点记为$ y_{i} $ , 去掉$ v_{i} $ 输入边和输出边.6) 深度优先搜索算法判断是否存在以
$ x_{i} $ 为起点或以$ y_{i} $ 为终点的增广路径.7) if 存在以
$ x_{i} $ 为起点的增广路径 then8) if 存在以
$ y_{i} $ 为终点的增广路径 then9)
$ v_{i} $ 为INM&ONM10) else
11)
$ v_{i} $ 为INM&OM12) end if
13) else
14) if 存在以
$ y_{i} $ 为终点的增广路径 then15)
$ v_{i} $ 为IM&ONM16) else
17)
$ v_{i} $ 为IM&OM18) end if
19) end if
20) else
21) 输入边相连节点记为
$ u_{i} $ , 去掉$ v_{i} $ 输入边22) 深度优先搜索算法判断是否存在以
$ u_{i} $ 为起点的增广路径23) if 存在以
$ u_{i} $ 为起点的增广路径 then24)
$ v_{i} $ 为INM25) else
26)
$ v_{i} $ 为IM27) end if
28) end if
29) else
30) if
$ v_{i} $ 存在输出边 then31) 输出边相连节点记为
$ w_{i} $ , 去掉$ v_{i} $ 输出边32) 深度优先搜索算法判断是否存在以
$ w_{i} $ 为终点的增广路径33) if 存在以
$ w_{i} $ 为终点的增广路径 then34)
$ v_{i} $ 为ONM35) else
36)
$ v_{i} $ 为OM37) end if
38) else
39)
$ v_{i} $ 为孤立节点40) end if
41) end if
42) end for
注 1. 假设网络中含有
$ N $ 个节点和$ L $ 条边. 算法时间复杂度由以下两个部分组成, 第一部分是识别网络二分图的最大匹配; 第二部分是通过深度优先搜索算法寻找增广路径. 由文献[29]可知识别网络二分图最大匹配的时间复杂度为${\rm O}(N^{0.5}L)$ . 通过深度优先搜索算法寻找增广路径可能存在以下四种情况:1)当
$ v_{i} $ 只含有输入边时, 与$ v_{i} $ 输入边相连的节点记为$ u_{i} $ . 去掉$ v_{i} $ 输入边, 以深度优先搜索算法识别是否存在以$ u_{i} $ 为起点的增广路径. 使用一次深度优先搜索算法, 复杂度为${\rm O}(L)$ .2)当
$ v_{i} $ 只含有输出边时, 与$ v_{i} $ 输出边相连的节点记为$ w_{i} $ . 去掉$ v_{i} $ 输出边, 以深度优先搜索算法识别是否存在以$ w_{i} $ 为终点的增广路径. 使用一次深度优先搜索算法, 复杂度为${\rm O}(L)$ .3)当
$ v_{i} $ 既含有输入边又含有输出边时, 与$ v_{i} $ 输入边相连节点记为$ x_{i} $ , 与$ v_{i} $ 输出边相连节点记为$ y_{i} $ . 去掉$ v_{i} $ 输入边与输出边, 以深度优先搜索算法识别是否存在以$ x_{i} $ 为起点或$ y_{i} $ 为终点的增广路径. 使用一次深度优先搜索算法, 复杂度为${\rm O}(L)$ .4)当
$ v_{i} $ 既不含有输入边又不含有输出边时, 该节点类型为孤立节点. 无需深度搜索.综上可知, 节点
$ v_{i} $ 为上述这四种情况中之一, 网络节点总数为$ N $ , 寻找增广路径的复杂度最大为${\rm O}(L)$ . 因最大匹配和寻找增广路径为并列关系, 故该算法的最大复杂度为${\rm O}(N^{0.5}L)+{\rm O}(NL)$ .2.3 节点失效对能控性的影响
现实的复杂网络在遭受攻击或意外时, 网络中的节点会被破坏或故障失去原有功能, 造成节点失效. 不同类型的节点失效对网络能控性有何影响? 本节根据第2.1节点分类的方式, 给出了网络节点失效时, 对网络能控性和驱动节点的影响情况.
定理 1. 对于一个含有
$ N $ 个节点的复杂网络, 当某一个节点遭受攻击失效时, 若失效节点为输入完全匹配节点(IM)时, 网络中驱动节点个数保持不变. 若失效节点为输入不完全匹配节点(INM)时, 网络中驱动节点个数减少一个.证明. 假设网络中节点个数为
$ N $ . 网络二分图最大匹配中被匹配的节点个数为$ H $ 个. 由式(3)可知驱动节点个数$ N_{D} = N-H $ . 当网络中输入完全匹配节点失效时, 节点个数为$ N-1 $ . 由输入完全匹配节点的定义可知, 该节点在原始网络中一定被其他节点的匹配. 因此该节点失效后, 网络中被匹配节点个数变成$ H-1 $ . 驱动节点个数$N_{D}^{'} = (N-1)- $ $ (H-1) = N-H = N_{D}$ . 驱动节点个数保持不变. 当网络中输入不完全节点失效时, 节点个数为$ N-1 $ . 由输入不完全匹配节点定义可以知, 该节点在最大匹配中不一定被其他节点所匹配. 因此该节点失效后, 网络最大匹配中被匹配节点个数保持不变为$ H $ . 驱动节点个数$N_{D}^{'} = (N-1)- $ $ H = N_{D}-1$ . 驱动节点个数减少一个. □定理 2. 对于一个含有
$ N $ 个节点的复杂网络, 当一个节点遭受攻击失效时, 若失效节点为输出完全匹配节点(OM)时, 网络中驱动节点个数保持不变. 若失效节点为输出不完全匹配节点(ONM)时, 驱动节点个数减少一个.证明. 假设网络中节点总数为
$ N $ 个, 被匹配节点个数为$ H $ 个. 驱动节点个数$ N_{D} = N-H $ . 当输出完全匹配节点失效时, 节点个数为$ N-1 $ . 由输出完全匹配节点定义可以该节点一定参与其他节点的匹配, 因此当该节点失效后, 一定会造成某个与之连的节点变成未匹配节点, 因此失效后网络中被匹配节点个数减少一个, 变成$ H-1 $ . 驱动节点个数$ N_{D}^{'} = (N-1)-(H-1) = N-H = N_{D} $ . 驱动节点个数保持不变. 当输出不完全匹配节点失效时, 节点个数为$ N-1 $ . 由输出不完全匹配节点定义可知, 该节点在最大匹配中不一定参与其他节点的匹配, 因此当该节点失效时, 网络最大匹配中被匹配的节点个数保持不变为$ H $ . 驱动节点个数$N_{D}^{'} = $ $ (N-1)-H = N_{D}-1$ . 驱动节点个数减少一个. □定理 3. 对于一个含有
$ N $ 个节点的复杂网络, 当一个节点遭受攻击失效时, 若失效的节点类型为IM&OM, 网络的驱动节点个数增加一个. 当失效的节点类型为IM&ONM或者INM&OM时, 网络的驱动节点个数保持不变. 当失效的节点类型为INM&ONM时, 网络的驱动节点个数减少一个.证明. 网络中节点个数为
$ N $ , 假设匹配节点个数为$ H $ . 将包含输出边又包含输入边的节点分解为两个节点, 一个只含有输出边, 另一个只含有输入边. 此时网络中节点个数为$ N+1 $ , 这样失效某个既包含输出边又包含输入边的节点等效为失效一个只包含输出边的节点和一个只包含输入边的节点. 将IM&OM节点分解为IM节点和OM节点, 此时网络中节点总数为$ N+1 $ . 失效IM&OM节点等效为IM 节点和OM 节点失效, 失效一个匹配起始节点和一个匹配终点, 匹配节点数少2. 引理1可知$N_{D}^{'} = (N+1-2)-(H-2) = N-H+1 = N_{D}+ 1$ 即驱动节点个数增加一个; 同理将IM&ONM 节点等效为IM节点和ONM节点, INM&OM节点等效为INM节点和OM节点, 失效一个匹配起点或一个匹配终点, 匹配节点数少$1,\, N_{D}^{'} = (N+1-2)- $ $ (H-1) = N-H = N_{D}$ ; INM&ONM节点等效为INM节点和ONM节点, 匹配节点数保持不变,$N_{D}^{'} = $ $ (N+1-2)-H = N-H-1 = N_{D}-1$ . 即驱动节点个数减少一个. □注 2. 由定理1, 2, 3可以看出, 当失效节点为IM, OM, INM&OM, IM&ONM节点时, 网络的驱动节点数不变, 但网络总节点数减少1, 由式(4) 可知由
$ n_{D} = N_{D}/(N-1) $ 衡量能控性大小, 所以网络能控性略有减弱; 当失效节点为IM&OM类型时, 网络的驱动节点数增加1, 网络总节点数减少1, 由式(4)可知能控性$ n_{D} = (N_{D}+1)/(N-1) $ , 所以$ n_{D} $ 明显变大, 能控性有明显减弱; 当失效节点为INM或ONM 或INM&ONM类型时, 网络的驱动节点数减少1, 网络总节点数减少1, 由式(4)可知能控性$ n_{D} = (N_{D}-1)/(N-1) $ , 所以$ n_{D} $ 明显减小, 能控性明显增强.3. 仿真实验
3.1 模型网络
首先生成三种典型的网络模型, 即ER随机网络模型[33], BA无标度网络模型[34], WS小世界网络模型[35], 其中生成ER网络节点个数
$ N $ 为500个, 节点间连接概率为$ p = 0.02 $ ; BA网络从初始点数是10个, 边数是8的网络, 每次引入一个新节点和4条边, 按照度大的节点优先连接的原则, 生成节点数为500的无标度网络; WS小世界网络, 从500个节点近邻边数为4的近邻耦合网络, 重连的概率为0.3, 生成的小世界网络. 采用2.2节所述节点类型识别算法, 得出三种网络每种节点类型数量, 如表1所示. 由于该分类方式针对有向网络, 因此在生成网络模型时, 将节点之间无向连接关系变成单向有向连接, 然后进行仿真.表 1 模型网络不同类型节点占比表Table 1 Proportion of different types of nodes in the model networkER网络 BA网络 WS网络 节点数 500 500 500 边数 2485 1968 1000 INM 27 25 0 IM 24 43 0 ONM 24 46 10 OM 31 39 2 INM&ONM 272 266 358 INM&OM 51 48 105 IM&ONM 42 33 20 IM&OM 32 0 5 $ V_{D}$ 0 0 0 从表1中可以看出,INM&ONM类型的节点数量在BA网络和WS网络中较多, 而IM&OM节点在BA网络和WS网络中较少. 因为BA网络中新添加的节点倾向于连接节点度高的节点, 而WS网络具有较高的聚类系数, 因此这两类网络中大部分节点不一定是所有匹配边集的起点和终点, 即不是固定与某个节点完成匹配.
为了验证每种类型节点失效对网络可控性的影响, 对网络中的每类节点进行逐个随机选则并删除, 然后计算网络中驱动节点个数占比
$ n_{D} $ . 由于网络失效一个节点后, 网络结构发生变化, 失效节点的邻近节点类型也会变化, 需要重新对网络节点进行分类, 再随机选取该类节点失效, 计算$ n_{D} $ . 需要注意是网络中不同类型节点个数不同, 为了能够有效对比, 失效节点个数保持一致, 失效节点的数量以数量最少的类型节点数量为准.按照上述方法, 在ER网络、BA网络和WS网络中逐个失效INM节点、IM节点、ONM节点和OM节点后网络的驱动节点个数占总节点数的比例
$ n_{D} $ 与失效节点数量占总节点数的比例$ f $ 的关系如图5、图6和图7所示. 图中可以看出INM节点和ONM节点失效后, 驱动节点个数减少,$ n_{D} $ 值降低, 随着INM节点和ONM节点失效, 网络可控性增加, 网络的控制更加容易. 相反IM节点和OM节点失效后,$ n_{D} $ 值略有增加. 实际上, 驱动节点个数$ N_{D} $ 不变, 但由于节点失效, 节点总数减少, 所以$ n_{D} $ 值呈现出略有增加的现象. 对于一个大规模网络, 节点数$ N $ 很大时, 失效少量节点时, 驱动节点个数$ N_{D} $ 不变时, 可以近似认为能控性$ n_{D} $ 不变.
图 5 ER网络$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 5 Controllability changes of$V_{I}$ and$V_{O}$ failure in ER networks
图 6 BA网络$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 6 Controllability changes of$V_{I}$ and$V_{O}$ failure in BA networks
图 7 WS网络$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 7 Controllability changes of$V_{I}$ and$V_{O}$ failure in WS networksER随机网络模型、BA无标度网络模型和WS小世界网络模型中INM&ONM节点、INM&OM节点、IM&ONM节点和IM&OM 节点失效后, 网络可控性
$ n_{D} $ 随失效节点个数占节点总数比例$ f $ 变化情况如图8、图9和图10所示. 图中可以看出, 当INM&ONM 节点失效后, 驱动节点个数减少,$ n_{D} $ 值降低, 网络可控性增强. 当INM&OM节点和IM&ONM节点失效后, 驱动节点个数不变, 但网络节点总数减少,$ n_{D} $ 值略有增大, 网络可控性降低. 当IM&OM节点失效后, 驱动节点个数增多,$ n_{D} $ 值增大明显, 网络可控性显著降低, 网络变得更难控制.
图 8 ER网络$V_{IO}$ 失效可控性变化Fig. 8 Controllability changes of$V_{IO}$ f ailure in ER networks
图 9 BA网络$V_{IO}$ 失效可控性变化Fig. 9 Controllability changes of$V_{IO}$ failure in BA networks
图 10 WS网络$V_{IO}$ 失效可控性变化Fig. 10 Controllability changes of$V_{IO}$ failure in WS networks3.2 真实网络
下面应用真实网络进行节点类型及每种类型的分布情况进行分析. 选取了多种社交网络[36], 包括某公司经理之间社交网络, 某律所律师社交网络, 某银行员工间社交网络和某学校学生间社交网络等共7个网络. 在社交网络中节点代表网络中的个体(某个人), 网络的边代表不同个体之间社交关系(交流或沟通). 根据每个网络的基本数据[36], 采用本文第2.2节点类型识别算法, 得出每个网络每种节点类型数量, 如表2所示.
表 2 实际网络不同类型节点占比表Table 2 Proportion of different types of nodes in the actual network经理社交网络 律师社交网络 银行员工社交网络 (1) 银行员工社交网络 (2) 银行员工社交网络 (3) 学生社交网络 (1) 学生社交网络 (2) 节点 21 71 11 11 11 73 73 边 190 892 30 51 27 243 263 $\langle k \rangle$ 9.05 12.56 2.73 4.64 2.54 3.33 3.60 INM 0 1 1 2 1 1 1 IM 3 0 0 0 0 0 0 ONM 0 1 2 0 0 4 4 OM 0 0 1 0 1 2 2 INM&ONM 18 67 3 8 3 44 47 INM&OM 0 2 1 0 3 13 10 IM&ONM 0 0 3 0 2 3 5 IM&OM 0 0 0 0 1 3 0 $V_{D} $ 0 0 0 0 0 3 4 在实际的社交网络中INM节点和IM节点为存在输入边的节点, 可理解为从不主动与他人交流沟通, 被动的接受他人的交流邀请的人; ONM节点和OM节点为存在输出边的节点在实际的社交网络中可理解为能主动的与他人交流沟通, 从不被动的接受他人的交流邀请的人. 同理, INM&ONM、INM&OM、IM&ONM和IM&OM节点在实际社交网络中可理解为即能主动的与他人交流沟通又能被动的接受他人的交流邀请的人;
$ V_{D} $ 节点是即不能主动的与他人交流沟通又不被动的接受他人的交流邀请的人. 表2的数据表明, 在社交网络中, INM&ONM节点占比较多, 这类节点在节点最大匹配中特性为不是所有最大匹配边集的起点和终点, 即不是一定参与其他节点的匹配, 也不是一定被其他节点所匹配. 这一现象对应人在社交网络中的交流与沟通不是固定不变的, 即每个人会与多人产生交流和沟通. 与实际中人际社交关系相符合. 而INM节点、IM节点、ONM节点和OM节点等占比较少, 这是由于这类节点在网络最大匹配中是最大匹配边集的起点或者终点, 即只参与其他节点匹配或者被匹配. 这种现象对应实际社交网络中交流与沟通是单向的, 这类情况在社交网络中出现概率较少.考虑到网络中节点类型的全面性, 本文选取节点数量相对较多的学生社交网络(1)和学生社交网络(2)分析节点失效后对网络能控性的影响. 为了有效对比, 选取节点数量较多的INM&ONM类型节点、INM&OM类型节点, 且每种类型失效节点数量保持相同. 节点失效后网络的驱动节点个数占比
$ n_{D} $ 与失效节点个数占比$ f $ 的关系如图11所示.图中可以看出, 当INM&ONM节点失效后, 驱动节点个数减少,
$ n_{D} $ 值降低, 网络可控性增强. 当INM&OM节点失效后, 驱动节点个数不变, 但网络节点总数减少,$ n_{D} $ 值略有增大, 网络可控性降低. 能控性的变化规律与仿真效果与模型网络一致.4. 结论
本文针对复杂网络中节点失效问题, 根据节点相连边的方向和最大匹配关系, 将网络节点分成九种类型, 并给出辨识节点类型的算法. 分析了不同类型节点失效对网络能控性的影响, 得出不同类型节点失效对网络驱动节点个数的不同影响, 当INM、ONM和INM&ONM类型节点失效时, 驱动节点数减少1, 网络能控性增强; 当IM、OM、INM&OM和IM&ONM类型节点失效时, 驱动节点数不变, 网络可控性略有降低, 此类型节点失效对网络能控性的影响较小, 当网络总节点数N 较大时, 能控性基本不变; 当IM&OM类型节点失效时, 驱动节点个数增加1, 网络能控性明显降低, 此类型节点对网络能控性的影响较大.
-
图 5 ER网络
$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 5 Controllability changes of
$V_{I}$ and$V_{O}$ failure in ER networks
图 6 BA网络
$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 6 Controllability changes of
$V_{I}$ and$V_{O}$ failure in BA networks
图 7 WS网络
$V_{I}$ 和$V_{O}$ 失效可控性变化Fig. 7 Controllability changes of
$V_{I}$ and$V_{O}$ failure in WS networks
图 8 ER网络
$V_{IO}$ 失效可控性变化Fig. 8 Controllability changes of
$V_{IO}$ f ailure in ER networks
图 9 BA网络
$V_{IO}$ 失效可控性变化Fig. 9 Controllability changes of
$V_{IO}$ failure in BA networks
图 10 WS网络
$V_{IO}$ 失效可控性变化Fig. 10 Controllability changes of
$V_{IO}$ failure in WS networks表 1 模型网络不同类型节点占比表
Table 1 Proportion of different types of nodes in the model network
ER网络 BA网络 WS网络 节点数 500 500 500 边数 2485 1968 1000 INM 27 25 0 IM 24 43 0 ONM 24 46 10 OM 31 39 2 INM&ONM 272 266 358 INM&OM 51 48 105 IM&ONM 42 33 20 IM&OM 32 0 5 $ V_{D}$ 0 0 0 
下载: 导出CSV
表 2 实际网络不同类型节点占比表
Table 2 Proportion of different types of nodes in the actual network
经理社交网络 律师社交网络 银行员工社交网络 (1) 银行员工社交网络 (2) 银行员工社交网络 (3) 学生社交网络 (1) 学生社交网络 (2) 节点 21 71 11 11 11 73 73 边 190 892 30 51 27 243 263 $\langle k \rangle$ 9.05 12.56 2.73 4.64 2.54 3.33 3.60 INM 0 1 1 2 1 1 1 IM 3 0 0 0 0 0 0 ONM 0 1 2 0 0 4 4 OM 0 0 1 0 1 2 2 INM&ONM 18 67 3 8 3 44 47 INM&OM 0 2 1 0 3 13 10 IM&ONM 0 0 3 0 2 3 5 IM&OM 0 0 0 0 1 3 0 $V_{D} $ 0 0 0 0 0 3 4
下载: 导出CSV
-
[1] Watts D J. The “new” science of networks. Annual Review of Sociology, 2004, 30(1): 243-270 doi: 10.1146/annurev.soc.30.020404.104342 [2] Yan G, Vértes P E, Towlson E K, Chew Y L, Walker D s, Schafer W R. Network control principles predict neuron function in the caenorhabditis elegans connectome. Nature, 2017, 550(7677): 519-523 doi: 10.1038/nature24056 [3] Zhang Z K, Liu C, Zhan X X, Lu X, Zhang C X, Zhang Y C. Dynamics of information diffusion and its applications on complex networks. Physics Reports, 2016, 651(1): 1-34 [4] Urena R, Kou G, Dong Y C, Chiclana F, Herrera-Viedma E. A review on trust propagation and opinion dynamics in social networks and group decision making frameworks. Information Sciences, 2019, 478(1): 461-475 [5] 任卓明. 动态复杂网络节点影响力的研究进展. 物理学报, 2020, 69(4): 048901 doi: 10.7498/aps.69.20190830Ren Zhuo-Ming. Research progress of node influence in dynamic complex networks. Acta Physica Sinica, 2020, 69(4): 048901 doi: 10.7498/aps.69.20190830 [6] Li A, Cornelius S P, Liu Y Y, Wang L, Barabási A L. The fundamental advantages of temporal networks. Science, 2017, 358(6366): 1042-1046 doi: 10.1126/science.aai7488 [7] Gao J X, Liu Y Y, D'Souza R M, Barabási A L. Target control of complex networks. Nature Communications, 2014, 5(1): 5415-5422 doi: 10.1038/ncomms6415 [8] Wang X F, Chen G R. Pinning control of scale-free dynamical networks. Physica A, 2002, 310(3): 521-531 [9] Li X, Wang X F, Chen G R. Pinning a complex dynamical network to its equilibrium. IEEE Transactions on Circuits and Systems I: Regular Papers, 2004, 51(10): 2074-2087 doi: 10.1109/TCSI.2004.835655 [10] Liu X W, Chen T P. Cluster synchronization in directed networks via intermittent pinning control. IEEE Transactions on Neural Networks, 2011, 22(7): 1009-1020 doi: 10.1109/TNN.2011.2139224 [11] Liu X W, Chen T P. Finite-time and fixed-time cluster synchronization with or without pinning control. IEEE Transactions on Cybernetics, 2018, 48(1): 240-252 doi: 10.1109/TCYB.2016.2630703 [12] Yu W W, DeLellis P, Chen G R. Distributed adaptive control of synchronization in complex networks. IEEE Transactions on Automatic Control, 2012, 57(8): 2153-2158 doi: 10.1109/TAC.2012.2183190 [13] Su H S, Rong Z H, Chen M Z. Decentralized adaptive pinning control for cluster synchronization of complex dynamical networks. IEEE Transactions on Cybernetics, 2013, 43(1): 394-399 doi: 10.1109/TSMCB.2012.2202647 [14] 杨青林, 王立夫, 李欢, 余牧舟. 基于相对距离的复杂网络谱粗粒化方法. 物理学报, 2019, 68(10): 100501 doi: 10.7498/aps.68.20181848Yang Qing-Lin, Wang Li-Fu, Li Huan, Yu Mu-Zhou. A spectral coarse-graining algorithm based on relative distance. Acta Physica Sinica, 2019, 68(10): 100501 doi: 10.7498/aps.68.20181848 [15] 王振华, 刘宗华. 复杂网络上的部分同步化: 奇异态、遥同步与集团同步. 物理学报, 2020, 69(8): 088902 doi: 10.7498/aps.69.20191973Wang Zhen-Hua, Liu Zong-Hua. Partial synchronization on complex networks: singular state, remote synchronization and group synchronization. Acta Physica Sinica, 2020, 69(8): 088902 doi: 10.7498/aps.69.20191973 [16] Ren H R, Karimi H R, Lu R Q, Wu Y Q. Synchronization of network systems via aperiodic sampled-data control with constant delay and application to unmanned ground vehicles. IEEE Transactions on Industrial Electronics, 2020, 67(6): 4980-4990 doi: 10.1109/TIE.2019.2928241 [17] 张檬, 韩敏. 基于单向耦合法的不确定复杂网络间有限时间同步. 自动化学报, 2020, 46(x): 1-9Zhang Meng, Han Min. Finite-time synchronization between uncertain complex networks based on unidirectional coupling method. Acta Automatica Sinica, 2020, 46(x): 1-9 [18] 潘永昊, 于洪涛. 基于网络同步的链路预测连边机理分析研究. 自动化学报, 2020, 46(12): 2607-2616Pan Yong-Hao, Yu Hong-Tao. Analysis of linkage mechanism of link prediction based on network synchronization. Acta Automatica Sinica, 2020, 46(12): 2607-2616 [19] 郭天姣, 涂俐兰. 噪声下相互依存网络的自适应 $ H_{\infty}$ 异质同步. 自动化学报, 2020, 46(6): 1229-1239GUO Tian-Jiao, TU Li-Lan. Adaptive$ H_{\infty}$ Heterogeneous Synchronization for 0.3 nterdependent Networks With Noise. Acta Automatica Sinica, 2020, 46(6): 1229-1239[20] Ren H R, Lu R Q, Xiong J L, Wu Y Q, Shi P. Optimal filtered and smoothed estimators for discrete-time linear systems with multiple packet dropouts under markovian communication constraints. IEEE Transactions on Cybernetics, 2020, 50(9): 4169-4180 doi: 10.1109/TCYB.2019.2924485 [21] Liu Y Y, Slotine J J, Barabási A L. Controllability of complex networks. Nature, 2011, 473(7346): 167-173 doi: 10.1038/nature10011 [22] Yuan Z, Zhao C, Di Z, Wang W X, Lai Y C. Exact controllability of complex networks. Nature Communications, 2013, 4(1): 2447-2455 doi: 10.1038/ncomms3447 [23] Posfai M, Hovel P. Structural controllability of temporal networks. New Journal of Physics, 2014, 16(12): 123055 doi: 10.1088/1367-2630/16/12/123055 [24] Wu J N, Li X, Chen G R. Controllability of deep-coupling dynamical networks. IEEE Transactions on Circuits and Systems I: Regular Papers, 2020, 67(12): 1-12 doi: 10.1109/TCSI.2020.3033927 [25] Tommaso M, Danielle S. Bassett, Fabio P. Structural controllability of symmetric networks IEEE Transactions on Automatic Control, 2019, 64(9): 3740-3747 doi: 10.1109/TAC.2018.2881112 [26] Sun C, Hu G Q, Xie L H. Controllability of multi-agent networks with antagonistic interactions. IEEE Transactions on Automatic Control, 2017, 62(10): 5457-5462 doi: 10.1109/TAC.2017.2697202 [27] Posfai M, Gao J, Cornelius S P, Barabási A L. Controllability of multiplex multi-time-scale networks. Physical Review E, 2016, 94(3): 032316 [28] Pu C L, Pei W J, Michaelson A. Robustness analysis of network controllability. Physica A, 2012, 391(18): 4420-4425 doi: 10.1016/j.physa.2012.04.019 [29] Liu Y Y, Slotine J J, Barabási A L. Control centrality and hierarchical structure in complex networks. PloS One, 2012, 7(9): e44459 doi: 10.1371/journal.pone.0044459 [30] Lu Z M, Li X F. Attack vulnerability of network controllability. PloS One, 2016, 11(9): e0162289 doi: 10.1371/journal.pone.0162289 [31] Pu C L, Cui W. Vulnerability of complex networks under path-based attacks. Physica A: Statistical Mechanics and its Applications, 2015, 419(1): 622-629 [32] Hopcroft J E, Karp R M. An $ n.{5/2}$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 1971, 2(4): 122-125[33] Erdos P, Renyi A. On random graphs. Publicationes Mathematicae, 1959, 6(1): 290-297 [34] Barabási A L, Albert R. Emergence of scaling in random networks. Science, 1999, 286(5439): 509-512 doi: 10.1126/science.286.5439.509 [35] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks. Nature, 1998, 393(6684): 440-442 doi: 10.1038/30918 [36] Coleman J S. Introduction to mathermatical sociology[Online], available: http://moreno.ss.uci.edu/data.html, September 10, 2020 期刊类型引用(3)
1. 葛耀东，李琰，宋晴，徐天奇，董哲源. 级联失效模型下电力信息物理系统鲁棒性与能控性分析. 科学技术与工程. 2024(19): 8127-8134 . 
百度学术2. 梁鹏玮，张万宏，张妍. 一种基于深度图卷积神经网络的可控性辨识方法. 青海大学学报. 2024(06): 105-112 . 百度学术3. 郭昊明，汪霜玲，燕雪峰，张科成. 基于复杂网络的军事通信网络建模与脆弱性分析. 西北工业大学学报. 2024(06): 1126-1134 . 百度学术其他类型引用(1)
-
下载:
计量
- 文章访问数: 1564
- HTML全文浏览量: 565
- PDF下载量: 222
- 被引次数: 4
