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

王媛媛; 袁正中; 赵琛; Wang Yuanyuan; Yuan Zhengzhong; Zhao Chen

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

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

- ORCID：
王媛媛 ¹
- ORCID：
袁正中 ^1,2,3
✉
- ORCID：
赵琛 ^4,5

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

最近更新：2021-11-08

DOI：10.6052/1672-6553-2020-097

摘要

针对无向网络实际控制问题，提出了一种有效设置控制输入矩阵，从而完成网络控制的方法.该方法表明，在一定条件下，对网络控制核心体实施控制即可控制整个网络. 实例检验了理论分析的结果，表明该理论的正确性和可行性. 该项研究揭示了无向网络中重要结构对整个网络的支配作用，为控制大型复杂网络提供了一个有效的方法.

关键词

无向网络; 网络叶子; 网络可控性

2020-07-31 收到第1稿，2020-10-16收到修改稿.

引言

复杂网络是将现实世界中各种大型复杂关联系统抽象成网络图进行研究的一种理论工具.现实生活中存在着各种各样的复杂网络，如生物网络^［

1］、交通网络^{［参考文献 2

百度学术}2］、社会网络^{［参考文献 3

百度学术}3］、信息网络^{［参考文献 4

百度学术}4］等.这些复杂网络展现出丰富的动力学特性^{［参考文献 5

百度学术}5］，如同步、涌现等^{［参考文献 6-8}6-8］.认识复杂网络是一个重要而漫长的过程，这一领域的研究工作面临着诸多的挑战^{［参考文献 9

百度学术}9］.目前，研究人员对复杂网络动力学的探索已经取得了一些进展，主要集中在复杂网络的传播^{［参考文献 10

百度学术}10］、搜索^{［参考文献 11

百度学术}11］、同步^{［参考文献 12

百度学术}12，13］、控制^{［参考文献 14

百度学术}14］等问题.其中网络控制问题已经成为网络科学的一个重要研究方向.

复杂网络可控是指网络系统在适当的输入作用下，在有限时间内可以在任意两个状态之间传递的性质.其中，需要被独立输入作用的节点称为驱动节点.近年来，关于网络可控性的研究已经有了一些突出成果.2011年，Liu等^［

15］在Nature首次基于线性系统思想研究了复杂网络的结构可控问题.该文献利用 Kalman 可控条件从理论上证明了网络结构可控所需要的驱动节点为该网络最大匹配中的未匹配节点.但该理论只适用于边权可独立选取的有向复杂网络，在无向复杂网络或给定权重的网络中不适用.进而Yuan等^{［参考文献 16

百度学术}16］提出严格可控理论对结构可控理论进行了优化.严格可控理论将网络可控性问题转化为邻接矩阵特征值的问题，说明复杂网络驱动节点数等于该邻接矩阵特征值的最大几何重数^{［参考文献 16

百度学术}16，17］，并且通过对矩阵进行初等变换可以找到对应的驱动节点.特别地，对于稀疏网络，网络的驱动节点数由网络邻接矩阵的秩决定.然而，复杂网络系统含有成千上万的节点，直接运用上面的方法计算和寻找控制网络的驱动节点是非常困难的.

本研究关注无向无权网络的实际控制问题，设置完整的控制输入矩阵满足系统的严格可控条件.文中网络中的一度节点、它的邻居和连边共同组成的结构称为网络叶子.已有的研究表明，删除叶子以及与叶子的连边不会改变网络的零度（nullity）^［

18］.从网络控制理论来说，这个结论表明对于无向的零特征值占优网络，删除叶子以及与叶子的连边不会改变网络的可控性能.那么，这种删除法是否也有利于控制输入矩阵的设置呢？本文基于线性系统的PBH可控性条件，给出网络核心体可控则整个网络可控的充要条件.利用该结论，我们可以持续删除网络叶子，直到网络中不存在叶子为止，得到一个子结构——网络核心体.其中，不同删除顺序得到的网络控制核心体中的节点数以及节点之间的连接关系相同^{［参考文献 18

百度学术}18］.再对该网络核心体设置控制输入矩阵.然后逐步回溯验证网络可控条件，从而实现对网络控制核心体实施控制，即可完全控制原始网络.该方法适用于大量稀疏的无向网络，为网络控制输入矩阵的设置开辟了新的路径.

1 基础知识

考虑以下含有n个节点的无向网络动力学系统^［

19，20］：

\dot{x} = A x + B u

（1）

式中，x=（x₁，x₂，⋯，x_n）^T表示n个节点的状态； A=（a_ij）∈Rⁿ^×ⁿ为系统的邻接矩阵，其中，a_ij=0表示节点i、j之间没有连接，a_ij=1表示节点i、j之间存在连接，a_ii=0；B∈Rⁿ^×^m为列满秩输入矩阵，其中B的列数表示需要独立控制的节点个数.如果B不是列满秩矩阵，则说明整个控制系统有多余的控制输入，可以进一步简化^［

16］.u=（u₁，u₂，⋯，u_m）^T为m个独立的控制输入.系统（1）可控的充要条件为下列条件之一成立^{［参考文献 19

百度学术}19，20］：

①Kalman条件

r a n k [B, A B, A^{2} B, \dots, A^{n - 1} B] = n

（2）

②PBH条件

\forall λ, r a n k (λ I_{n} - A, B) = n

（3）

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

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

A = (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & α^{T} \\ 0 & α & A_{0} \end{matrix})

（4）

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

2 主要工作

2.1　控制理论

通过持续删除网络叶子并保留孤立节点，网络的控制核心体中只包含孤立节点和一些规模较小的连通集团.显然，孤立节点一定需要直接的独立控制输入，所以必然是驱动节点.网络的其它驱动节点则包含在剩下的小规模的连通集团中，可以通过文献［

16］中提出的对邻接矩阵进行初等变换的方法找到其对应的驱动节点，从而高效快速地完成对原始网络驱动节点的寻找.通过这种处理之后，一个无向复杂网络可控问题被拆分成多个小集团的可控问题，即网络核心体的可控问题.驱动节点可以从网络核心体中寻找，整个控制输入矩阵是否也可以从网络核心体中寻找呢？换句话说，如果完成了对网络核心体的控制，是否就可以控制整个网络？为此，我们通过以下定理回答了上述问题，该定理给出了对网络核心体实施控制即可完全控制原始网络的条件.

定理：设A为网络的邻接矩阵，A₀为（n-2）×（n-2）阶方阵，表示删去一个叶子后得到的子网络对应的邻接矩阵.若子网络A₀是可控的，即存在B₀B₀，使得（A₀，B₀B₀）可控.则原始网络在B₀B₀所对应的控制输入B₀B₀的作用下也是可控的，如果以下不等式之一成立：

（i）

α^{T} V_{2} (λ) \neq 0

（5）

（ii）

\frac{λ}{- 1} \neq \frac{- 1}{λ - α^{T} V_{1} (λ) α}

（6）

式中，α为n-2维的向量，表示叶子与其余节点的连接情况.为矩阵A₀的特征值.V₁（λ）、V₂（λ）满足以下等式：

(λ I_{n - 2} - A_{0}, B_{0}) (\begin{matrix} V_{1} (λ) & V_{2} (λ) \\ V_{3} (λ) & V_{4} (λ) \end{matrix}) = (I_{n - 2}, 0)

（7）

证明：不失一般性，将A改写为等式（4）的形式.由于矩阵A₀对应的系统可由B₀控制，由PBH条件（3）式可得

r a n k (λ I_{n - 2} - A_{0}, B_{0}) = n - 2

于是，一定存在可逆 $V (λ) = (\begin{matrix} V_{1} (λ) & V_{2} (λ) \\ V_{3} (λ) & V_{4} (λ) \end{matrix})$ ，使得等式（7）成立.令

B = (\begin{matrix} 0 \\ B_{0} \end{matrix})

，

S (λ) = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & α^{T} V_{1} (λ) \\ 0 & 0 & 1 \end{matrix})

，

U (λ) = (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & V_{1} (λ) α & V_{1} (λ) & V_{2} (λ) \\ 0 & V_{3} (λ) α & V_{3} (λ) & V_{4} (λ) \end{matrix})

，

则得到G（λ）与V（λ）的关系式：

\begin{array}{l} G (λ) = S (λ) (λ I_{n} - A, B) U (λ) \\ = (\begin{matrix} λ & - 1 & 0 & 0 \\ - 1 & λ - α^{Τ} V_{1} (λ) α & 0 & - α^{Τ} V_{2} (λ) \\ 0 & 0 & I_{n - 2} & 0 \end{matrix}) \end{array}

此时，若条件（5）或者条件（6）成立，则

r a n k (G (λ)) = n - 2 + 2 = n

又因为S（λ），U（λ）均为可逆矩阵，乘法运算不影响（λI_n-A，B）的秩.因此rank（λI_n-A，B）=n，由PBH可控条件，原始网络在控制输入 $B = (\begin{matrix} 0 \\ B_{0} \end{matrix})$ 的作用下是可控的.

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

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

A_{0} = (\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix})

，

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

第四次删除节点（4，5）时， $α_{4} = {(1,0, 1,0)}^{Τ}$ ， $α_{4}^{T} V_{2_{4}} (λ_{4}) = (λ_{4} + 1, - 1,0) \neq 0$ ，条件（5）满足；

第三次删除节点（6，7）时，α³=（0，0，1，0，1，0）^Τ， $α_{3}^{T} V_{2_{3}} (λ_{3}) = (1,1, 0) \neq 0$ ，条件（5）满足；

第二次删除节点（9，10）时， $α_{2} = {(0,1, 0,0, 0,0, 0,1)}^{Τ}$ ， $α_{2}^{Τ} V_{2_{2}} (λ_{2}) = (- λ_{2}^{2} - 2 λ_{2}, λ_{2}^{3} + 2 λ_{2}^{2} - λ_{2} - 1,1) \neq 01,1) \neq 0$ ，条件（5）满足；

第一次删除节点（11，12）时， $α_{1} = {(0,0, 1,0, 0,0, 0,0, 0,0)}^{Τ}$ ， $α_{1}^{T} V_{2_{1}} (λ_{1}) = (- 1, {λ_{1}}^{2} - 1,0) \neq 0$ ，条件（5）仍然满足.

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

3 结论

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

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

参考文献

Bullmore E T，Sporns O. The economy of brain network organization.Nature Reviews Neuroscience，2012，13（5）：336~349 [百度学术]

Li D，Fu B，Wang Y，et al. Percolation transition in dynamical traffic network with evolving critical bottlenecks. Proceedings of the National Academy of Sciences of the United States of America，2015，112（3）：669~672 [百度学术]

Borgatti S P， Mehra A， Brass D J，et al. Network analysis in the social sciences. Science，2009，323（5916）：892~895 [百度学术]

Peterson L C，Kwiatkowski S E.Electronic information network for inventory control and transfer.United States：US6324522B2，2001-11-27 [百度学术]

乔磊，茅晓晨.时滞诱发的忆阻型Hopfield神经网络的复杂动力学.动力学与控制学报，2019，17（4）：384~390 [百度学术]

Qiao L，Mao X C.Delay-induced complicated dynamics of a memristive Hopfield neural network. Journal of Dynamics and Control，2019，17（4）：384~390 （in Chinese） [百度学术]

Newman M E. The structure and function of complex networks. Society for Industry and Applied Mathematics Review，2003，45（2）：167~256 [百度学术]

汪小帆，李翔，陈关荣.复杂网络理论及其应用.北京：清华大学出版社，2006：194~238 （Wang X F，Li X，Chen G R. Complex network theory and its application.Beijing：Tsinghua University Press，2006：194~238 （in Chinese）） [百度学术]

何大韧，刘宗华，汪秉宏.复杂系统与复杂网络.北京：高等教育出版社，2009（He D R，Liu Z H，Wang B H.Complex systems and complex networks.Beijing：Higher Education Press，2009 （in Chinese）） [百度学术]

陈关荣.复杂动态网络环境下控制理论遇到的问题与挑战. 自动化学报，2013，39（4）：312~321 [百度学术]

Chen G R.Problems and challenges in control theory under complex dynamical network environments. Journal of Automatica Sinica，2013， 39 （4）：312~321 （in Chinese） [百度学术]

Doerr B，Fouz M，Friedrich T.Why rumors spread so quickly in social networks. Communications of the ACM，2012，55（6）： 70~75 [百度学术]

Patti F D，Fanelli D，Piazza F，et al. Optimal search strategies on complex multi-linked networks. Scientific Reports，2015，5（1）：9869～9869 [百度学术]

刘田，杨晓丽.离散混沌网络系统中共同噪声诱导同步的条件.动力学与控制学报，2019，17（1）：27~34 [百度学术]

Liu T， Yang X L. Condition of common noise induced synchronization in discete chaotic network systems. Journal of Dynamics and Control，2019，17（1）：27~34（in Chinese） [百度学术]

柴元，吴泉军.时滞社团网络联合同步.动力学与控制学报，2019，17（3）：258~263 [百度学术]

Chai Y，Wu Q J. Combined synchronizationtime-delay community networks. Journal of Dynamics and Control，2019，17（3）：258~263（in Chinese） [百度学术]

Liu Y Y， Barab´asi A L.Control principles of complex systems.Reviews of Modern Physics，2016，88（3）：035006~035064 [百度学术]

Liu Y，Slotine J E，Barabasi A，et al. Controllability of complex networks. Nature，2011，473（7346）：167~173 [百度学术]

Yuan Z Z，Zhao C，Di Z R，et al.Exact controllability of complex networks. Nature Communications，2013，4（1）：2447~2447 [百度学术]

Cai N. Controllability improvement for linear time-invariant dynamic multi-agent systems. International Journal of Innovative Computing，2012，8：3315~3328 [百度学术]

Bauer M， Golinelli O. Core percolation in random graphs：a critical phenomena analysis. European Physical Journal B，2001，24（3）：339~352 [百度学术]

Kalman R E. Mathematical description of linear dynamical systems. Journal of the Society for Industrial and Applied Mathematics，1963，1（2）：152~192 [百度学术]

Hautus M. Controllability and observability conditions of linear autonomous systems.Nederlandse Akademie van Wetenschappen. Proceedings. Series A， 1969，72：443~448 [百度学术]

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

摘要

关键词

引言

1 基础知识

2 主要工作

2.1　控制理论

2.2　实例分析

3 结论

参考文献

微信公众号二维码

手机版网站二维码

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

摘要

关键词

引言

1 基础知识

2 主要工作

2.1 控制理论

2.2 实例分析

3 结论

参考文献

微信公众号二维码

手机版网站二维码

2.1　控制理论

2.2　实例分析