基于网络核心体的复杂网络控制分析*

王媛媛 袁正中 ，2，3† 赵琛

（1.闽南师范大学数学与统计学院，漳州 363000）（2.闽南师范大学数据科学与统计福建省高校重点实验室，漳州 363000）（3.闽南师范大学数字福建气象大数据研究所，漳州 363000）（4.河北师范大学计算机与网络空间安全学院，石家庄 050024）（5.河北省网络与信息安全重点实验室，石家庄 050024）

引言

复杂网络是将现实世界中各种大型复杂关联系统抽象成网络图进行研究的一种理论工具.现实生活中存在着各种各样的复杂网络，如生物网络[1]、交通网络[2]、社会网络[3]、信息网络[4]等 .这些复杂网络展现出丰富的动力学特性[5]，如同步、涌现等[6-8].认识复杂网络是一个重要而漫长的过程，这一领域的研究工作面临着诸多的挑战[9].目前，研究人员对复杂网络动力学的探索已经取得了一些进展，主要集中在复杂网络的传播[10]、搜索[11]、同步[12，13]、控制[14]等问题 .其中网络控制问题已经成为网络科学的一个重要研究方向.

复杂网络可控是指网络系统在适当的输入作用下，在有限时间内可以在任意两个状态之间传递的性质.其中，需要被独立输入作用的节点称为驱动节点.近年来，关于网络可控性的研究已经有了一些突出成果.2011年，Liu等[15]在Nature首次基于线性系统思想研究了复杂网络的结构可控问题.该文献利用Kalman可控条件从理论上证明了网络结构可控所需要的驱动节点为该网络最大匹配中的未匹配节点.但该理论只适用于边权可独立选取的有向复杂网络，在无向复杂网络或给定权重的网络中不适用.进而Yuan等[16]提出严格可控理论对结构可控理论进行了优化.严格可控理论将网络可控性问题转化为邻接矩阵特征值的问题，说明复杂网络驱动节点数等于该邻接矩阵特征值的最大几何重数[16，17]，并且通过对矩阵进行初等变换可以找到对应的驱动节点.特别地，对于稀疏网络，网络的驱动节点数由网络邻接矩阵的秩决定.然而，复杂网络系统含有成千上万的节点，直接运用上面的方法计算和寻找控制网络的驱动节点是非常困难的.

本研究关注无向无权网络的实际控制问题，设置完整的控制输入矩阵满足系统的严格可控条件.文中网络中的一度节点、它的邻居和连边共同组成的结构称为网络叶子.已有的研究表明，删除叶子以及与叶子的连边不会改变网络的零度（nullity）[18].从网络控制理论来说，这个结论表明对于无向的零特征值占优网络，删除叶子以及与叶子的连边不会改变网络的可控性能.那么，这种删除法是否也有利于控制输入矩阵的设置呢？本文基于线性系统的PBH可控性条件，给出网络核心体可控则整个网络可控的充要条件.利用该结论，我们可以持续删除网络叶子，直到网络中不存在叶子为止，得到一个子结构——网络核心体.其中，不同删除顺序得到的网络控制核心体中的节点数以及节点之间的连接关系相同[18].再对该网络核心体设置控制输入矩阵.然后逐步回溯验证网络可控条件，从而实现对网络控制核心体实施控制，即可完全控制原始网络.该方法适用于大量稀疏的无向网络，为网络控制输入矩阵的设置开辟了新的路径.

1 基础知识

考虑以下含有n个节点的无向网络动力学系统[19，20]：

式中，x=（x1，x2，…，xn）T表示n个节点的状态；A=（aij）∈Rn×n为系统的邻接矩阵，其中，aij=0表示节点i、j之间没有连接，aij=1表示节点i、j之间存在连接，aii=0；B∈Rn×m为列满秩输入矩阵，其中B的列数表示需要独立控制的节点个数.如果B不是列满秩矩阵，则说明整个控制系统有多余的控制输入，可以进一步简化[16].u=（u1，u2，…，um）T为m个独立的控制输入.系统（1）可控的充要条件为下列条件之一成立[19，20]：

其中，λ为矩阵A对应的特征值，In为n阶单位矩阵.

对于含有叶子结构的稀疏无向复杂网络，持续地删除网络叶子及其连边并保留孤立节点，直至整个网络不再包含度为1的节点，最终得到的所有连通集团和孤立节点共同构成了网络的核心体.不失一般性，可以将含有叶子结构的复杂网络邻接矩阵A表示为如下形式：

其中第一个节点的度为1，其邻居为第二个节点，它们及其之间的连边被称为网络的叶子.向量α表示叶子与其余节点的连接情况.矩阵A0是（n−2）×（n−2）阶方阵，表示删除叶子及其连接后所有剩余节点之间的连接情况.

2 主要工作

2.1 控制理论

通过持续删除网络叶子并保留孤立节点，网络的控制核心体中只包含孤立节点和一些规模较小的连通集团.显然，孤立节点一定需要直接的独立控制输入，所以必然是驱动节点.网络的其它驱动节点则包含在剩下的小规模的连通集团中，可以通过文献[16]中提出的对邻接矩阵进行初等变换的方法找到其对应的驱动节点，从而高效快速地完成对原始网络驱动节点的寻找.通过这种处理之后，一个无向复杂网络可控问题被拆分成多个小集团的可控问题，即网络核心体的可控问题.驱动节点可以从网络核心体中寻找，整个控制输入矩阵是否也可以从网络核心体中寻找呢？换句话说，如果完成了对网络核心体的控制，是否就可以控制整个网络？为此，我们通过以下定理回答了上述问题，该定理给出了对网络核心体实施控制即可完全控制原始网络的条件.

注：定理仅证明一次删除的情形.在实际使用中，我们需记录每次删除时的向量α，利用最终的控制核心对应的B0逐步回溯验证定理条件.

2.2 实例分析

考虑一个具有12个节点的无向稀疏网络，网络连接情况如图1所示.对该无向复杂网络，寻找网络中的1度节点，删除叶子并保留孤立节点，直至网络中不存在1度节点为止.删除过程为：第一次删除节点11，12和对应连边；第二次删除节点9，10和对应连边，产生孤立节点8；第三次删除节点6，7和对应连边，以及第四次删除节点4，5和对应连边，最终得到网络控制核心体.在图1中，空心节点表示将被删去的节点，被虚线圈起的实心节点和它们之间的连边构成网络的控制核心体.网络控制核心体的邻接矩阵为：

图1 通过控制核心使原始网络可控Fig.1 The original network is controlled by the control core

此时，对邻接矩阵A0进行初等变换可以很容易地找到对应的一组驱动节点为1，2和8节点，并且对它们实施独立的控制输入可以满足网络控制核心体的可控性，即控制1，2和8节点可以使网络控制核心体可控.接着，依次验证删除过程中网络是否满足控制条件（5）或条件（6）.

第四次删除节点（4，5）时，α4=(1，0，1，0)Τ，，条件（5）满足；第三次删除节点（6，7）时，α3=（0，0，1，0，1，0）Τ，，条件（5）满足；

第二次删除节点（9，10）时 ，α2=(0，1，0，0，0，0，0，1)Τ，，条件（5）满足；

第一次删除节点（11，12）时 ，α1=(0，0，1，0，0，0，0，0，0，0)Τ，，条件（5）仍然满足.

上面验证表明，仅通过控制含有4个节点的网络核心体即可控制整个原始网络.可见，该方法可以有效地简化对无向复杂网络控制输入的寻找过程，完成对大型复杂网络的实际控制.

3 结论

本文针对无向复杂网络寻找控制输入困难的问题，基于PBH可控条件和叶子节点删除法给出了对网络核心体实施控制即可控制原始网络的充要条件，得到了寻找无向网络中控制输入节点的方法：①持续删除叶子结构及其连边并保留孤立节点得到网络核心体；②利用可控条件寻找该核心体的一个控制输入；③回推验证每一次删除中相关条件是否满足并得出结论：若条件（5）或条件（6）满足，表明仅利用该网络核心体的控制输入即可完全控制原始网络.

由于条件（5）和条件（6）均为不等式，所以在大多数情况下该条件均可满足.这是因为条件（5）和条件（6）的否定式均为等式，等式的解一定是有限点集或者空集，这些集合测度均为0，所以条件（5）和条件（6）的否定形式成立的参数选择范围小，被选择的可能性不高.这样就可以得到条件（5）和条件（6）在大多数情况下均可满足.因此，对于绝大多数的无向复杂网络，只要我们完成了对网络控制核心体的控制，就能控制整个网络.该结论对解决大型稀疏网络的控制问题提供了非常简单的思路和具体的方法.