E-mail: jalu@whu.edu.cn 基于自适应同步的网络结构识别 陆君安 School of Mathematics and Statistics, Wuhan University E-mail: jalu@whu.edu.cn （复杂网络论坛,北京,April.27-29th,2011)

Collaborators Dr. Wu Xiaoqun, Dr.Zhou Jin, Dr. Chen Juan, Wuhan University Dr. Liu Hui, University of Groningen, Netherlands Dr. Chen Liang, Guangxi University Dr. Zhao Junchan ,Wuhan Textile University Prof. Lü Jinhu, Academy of Mathematics and Systems Science, Chinese Academy of Sciences Prof. David John Hill, Australian National University, Australia Prof. C. K. Tse, Hong Kong Polytechnic University

Abstract 复杂动力网络的结构识别是目前复杂网络研究中的一个前沿重要方向。本文主要介绍基于自适应同步的网络动力学参数和拓扑识别方法，指出动力学信息对于结构识别并非充分的，如果需要同时识别网络拓扑结构和动力学参数，则需要满足经内连映射和节点动力学映射后的两簇函数组在同步流形上线性无关的条件。进一步分析了阻碍网络拓扑识别的因素，并介绍了网络拓扑识别的某些最新的工作。其中包括我们自己的一些工作。

Outline 1. 导言 2. 基于自适应同步的网络结构识别方法 3. 影响结构识别的因素 4. 某些新的识别方法和待研究的问题

1. 导 言

导 言 已有研究大多是基于网络结构已知的动力学的控制和同步。然而现实世界中的复杂网络存在各种不确定性的信息，网络的结构包括网络的拓扑连接、节点动力学参数等，往往只有部分已知，并且还不断地变化，例如基因表达网络、蛋白质的DNA结构、能量网络、生物神经网络。因此，如何利用观测到的节点动力学的信息来辨识网络的结构，具有重大的理论和应用价值，它也是分析、控制和预测真实的复杂网络动力学行为的先决条件。因此，目前网络的拓扑识别得到研究者的广泛关注。

导 言 如果说已知网络拓扑结构条件下网络动力学的控制和同步问题是复杂动力网络正问题的话，则网络拓扑结构的识别属于复杂动力网络的反演问题（或者反问题），显然，反问题比正问题困难，而且一般来说反问题的解是不唯一的，解反问题是需要附加补充条件的。 类似：CT-计算机x光断层造影术，地球物理反演（geophysical inversion）

导 言 对于单个非线性或混沌系统的未知参数的估计问题已经有不少研究。对于复杂动力学网络的结构识别问题，目前已经获得一些重要进展，例如 [1] D. Yu, M. Righero, L. Kocarev. Estimating topology of network[J].Phys. Rev. Lett., 2006,97: 188701. [2] W.K.S. Tang, M. Yu and L. Kocarev. Identification and monitoring of biological neural network[C]. IEEE International Symposium on Circuits and Systems, 2007. [3] W. Lin, H. Ma. Failure of parameter identification based on adaptive synchronization techniques[J]. Phys. Rev. E, 2007, 75: 066212. [4] W. Yu, G. Chen, J. Cao, J. Lü, U. Parlitz. Parameter identification of dynamical systems from time series[J]. Phys. Rev. E, 2007, 75(6): 067201. [5] J. Zhou, J. Lu. Topology identification of weighted complex dynamical networks[J]. Physica A, 2007, 386(1): 481-491. [6] X. Wu. Synchronization-based topology identification of weighted general complex dynamical networks with time-varying coupling delay[J]. Physica A, 2008, 387: 997-1008.

导 言 [7] Hui Liu, Jun-an Lu, and Jinhu Lü , David John Hill.Structure Identification of Uncertain General Complex Dynamical Networks with Time Delay[J].Automatica-REGULAR PAPERS, 2009 ，45 ：1799－1807. [8] Liang Chen, Jun-an Lu, and Chi K. Tse. Synchronization: An Obstacle to Identification of Network Topology[J].IEEE Transactions on Circuits and Systems—II: EXPRESS BRIEFSI.，2009， 56（ 4）：310－314. [9] Hui Liu, Jun-an Lu, Jinhu Lü. Topology identification of an uncertain general complex dynamical network[C]. Proc. of the 2008 IEEE International Symposium on Circuits and Systems.USA, 2008: 109-112. [10] 刘慧, 复杂动力网络的同步与拓扑识别[D]，武汉大学博士论文, 2010. [11] Junchan Zhao, Qin Li, Jun-An Lu and Zhong-Ping Jiang，Topology Identification of complex dynamical networks, CHAOS ,2010,20(2):023119-7 [12] Jin Zhou, Wenwu Yu, Xiumin Li, Michael Small, and Jun-an Lu. Identifying the Topology of a Coupled FitzHugh–Nagumo Neurobiological Network via a Pinning Mechanism[J].IEEE TRANSACTIONS ON NEURAL NETWORKS, 2009，20(10)：1679-1684

2. 基于自适应同步的网络结构 识别方法

考虑如下含有N 个不同节点动力学的未知拓扑结构和未知系统参数的复杂动力学网络模型， 这里 是第i个节点的状态向量, 是耦合矩阵. 如果存在从节点 i 到节点j (j ≠ i) 的一条边, 那么aij ≠ 0; 否则,aij = 0. 耦合矩阵A不需要是对称和耗散。参数c>0表示耦合强度。 (1)

第i个节点动力学方程为 ,记为 , 这里 ( 为非负整数) 是节点动力学的参数向量. 对每个 是 向量, 是 阶矩阵. 显然, 能写成 这里 . 如果参数向量 在模型(1)中是已知的, 该问题就是文献[2,5,6] 中所研究的情形。因此，我们这里所研究的问题是一个更一般的模型。

假设节点动力学的参数向量 和网络的连接矩阵 是未知的. 假设节点动力学的参数向量 和网络的连接矩阵 是未知的. 识别的目的：基于网络中N 个节点 的演化信息来识别节点动力学的参数向量和网络的连接矩阵。 为此，将(1)式作为驱动网络, 构造辅助网络作为响应网络（外同步）如下 是控制输入, 是对 的估计, 参数向量 是对未知的拓扑参数向量 的估计, 这里 . (2)

以下给出一些假设条件 假设1(重要假设). 对任意给定的 两簇向量函数组 在同步流形 上线性无关. 注：证明中由误差方程的0点稳定性得到，对于任意给定i＝1,2,…,N

假设2. 对于节点动力学 ,假设存在一个非负常数 满足 假设2. 对于节点动力学 ,假设存在一个非负常数 满足 假设3. 对于内连耦合函数 ,假设存在非负常数 满足 (3) (4)

我们将设计自适应控制器让响应网络(2)和驱动网络(1)（外）同步，并根据如下定理1同时识别未知的网络拓扑结构和系统参数。 记 我们将设计自适应控制器让响应网络(2)和驱动网络(1)（外）同步，并根据如下定理1同时识别未知的网络拓扑结构和系统参数。 定理1. 如果假设1,2,3 成立, 通过如下响应网络及自适应控制器 这里 , 并且 为正常数. 那么复杂动力网络(1)中未知的耦合矩阵A和节点动力学的系统参数 能分别被估计值 和 识别. (5)

注释1.假设1要求两簇向量函数组在同步流形 上线性无关，这个同步流形是指驱动网络和响应网络之间的（外）同步。 注释2.如果没有经内连耦合动力学和节点动力学映射后的两簇函数组在同步流形 上线性无关条件, 我们只能够得到当 时, 驱动网络和响应网络同步 。同时, 和 渐进趋于常数值，但该值有可能不是实际值 和 ,从而出现伪收敛的情况。

推论1. 考虑含有N 个相同节点的复杂动力学网络 在类似于假设1,假设2和假设3的条件下, 复杂动力学网络(6)的未知网络拓扑结构A及系统参数 能通过以下响应网络及自适应控制器识别 这里 , 为正常数. 当 时,有 及 . (6) (7)

推广到节点动力学含时滞和网络耦合含时滞的情况下系统参数和拓扑结构的识别.见 [7,10]。

数值例子1: 参数识别中线性无关条件 考虑一个四维的系统 b=-100,c=-1已知，只识别参数 右边写成

建立响应系统,自适应方法使得两系统达到同步

则参数识别的条件为：在原系统和响应系统的同步流形上成立

由于 在同步流形上近似 线性相关(见图)，所以由 得不到 和 x4随时间的变化 在同步轨道上随时间的变化.

所以只能识别p11,p31,但不能识别p21,p22,即

数值例子2 由5个相同的吕系统构成的动力学网络， 参数向量 耦合矩阵 耦合强度c=1

数值例子2 假设2和3满足，假设1中的线性无关条件不满足, 有 其中 线性无关， 得到 因此能够识别参数，但拓扑识别失败！

图1

数值例子3 图2 由20个节点构成的无向网络.节点取为不同参数的吕系统.(36,20 +0.25i,3) ,耦合强度为c = 1. 假设耦合矩阵A的第一排元素未知, 吕系统的参数向量 未知. 利用定理1的控制器和自适应法则识别.由于不同混沌系统耦合,假设1的条件满足.图3给出了识别结果.

图3

含时滞的结构识别 在现实网络中，时滞（包括状态变量的时滞和耦合 作用的时滞）总是出现在各种复杂网络中，比如通信网络、神经网络、生物网络等等.时滞大小通常是由有限的信号传输速度或容量所引起。因此，对时滞的未知网络进行拓扑识别和系统参数识别具有重要的理论意义和实际意义。

含耦合时滞的结构识别 驱动网络 响应网络

含耦合时滞的结构识别 定理2 注：假设3也是线性无关条件： 在同步流形 上线性无关

含节点时滞的结构识别 驱动网络 响应网络

含节点时滞的结构识别 定理3 注：假设4也是相应的线性无关条件

含时滞的结构识别 注释3.由于时滞的引入, 网络动力学方程组由自治 方程组变为非自治方程组. 推导比不含时滞的情形要更为复杂. 同时, 我们在处理收敛问题上,采用了非自治系统的Barbalat 引理（因为LaSalle不变原理不能直接使用 ）. 注释4. 以上分别讨论了含耦合时滞和节点时滞的未知复杂动力学网络的结构识别. 对于同时含有耦合时滞和节点时滞的情形,从证明方法上看,其结果不难推广到同时含耦合时滞和节点时滞的情形.

数值例子4 图4. 由20个相同节点构成的含时滞的结构识别

图4. 由20个相同节点构成的含耦合时滞的结构识别

一致激励条件在结构识别中的应用 证明了一致激励条件在网络拓扑结构识别中的关键作用，可以用于非自治系统（特别适用于时滞问题），克服了LaSalle不变原理不能适用一般的非自治系统的局限性。 经内连映射后的函数组满足一致激励条件，则网络拓扑结构可以识别。 [11] Junchan Zhao, Qin Li, Jun-An Lu and Zhong-Ping Jiang，Topology Identification of complex dynamical networks, Chaos ,2010,20(2):023119-7

3. 影响结构识别的因素

同步阻碍结构识别 为了分析起来方便，我们不考虑系统参数的识别，同时假定各节点动力学和内联耦合函数都相同。这时驱动网络为 响应网络为 类似地设计自适应律。这时候，如果驱动网络内各节点动力学同步，即 ,则在同步流形 上有 ,由此得到 ,所以识别失效。

同步阻碍结构识别 如果驱动网络部分同步(m<N个同步)： 于是得到 进一步假设 和 线性无关，能够得到 和 即只能得到部分识别：

同步阻碍结构识别 结论:网络内各节点同步是阻碍拓扑识别，网络内部分节点同步则部分不能识别。也就是说当网络的节点之间存在很强的同步化情况下, 所有节点的动力学行为就与单个节点动力学行为几乎一样了, 从而即使知道所有节点动力学也无法导出节点之间的动力学耦合和传递关系, 于是造成由动力学识别拓扑的失败。

同步阻碍结构识别 拓扑识别的自适应方法导出的线性无关条件在数学上是非常重要的。那么，人们自然要问，“在同步流形上线性无关”怎么检验？现在，我们在这个线性无关条件基础上，进一步提出“同步是阻碍网络拓扑识别的”，“完全同步就完全不能识别”，“部分同步就部分不能识别”，“削弱同步有利于识别”[8－10]。由于同步是可以检验的，因此“在同步流形上线性无关”这个条件就变得可以具体操作的了。由于同步是阻碍识别的，所以为了识别拓扑结构，必须削弱节点之间的一致性（同步性）。

同步阻碍结构识别 过去人们主要研究同步的条件以及如何加强同步的问题，很少有人研究削弱同步、变同步为失同步的问题。“同步阻碍识别”告诉我们，原来削弱同步有时候也很有意义,如如同步造成拥塞。就像人们研究混沌控制，后来发现混沌在某些场合是有用的，因此才有“混沌反控制”的概念[13]。因此我们在“同步阻碍识别”的基础上，不妨提出“反同步”和复杂动力网络“反同步”的概念，也许能够发现一些新的现象和新的机理。 [13] G Chen, D. Lai ， Feedback anticontrol of discrete chaos ,Int. J. Bifurcat. Chaos ,1998,8,1585（建立混沌反控制的基本理论,Chen-Lai算法)

耦合强度对拓扑识别的影响 根据主稳定函数方法得到驱动网络内部的信号同步的区域： 第一类同步区间是有界的，耦合强度在某一区间能够保证驱动网络内部信号同步. 第二类同步区间是无界的，耦合强度大于某一值能够保证驱动网络内部信号同步。 第三类同步区间是空集,无论多大的耦合强度都无法让驱动网络同步。

数值例子5 图5 耦合强度对拓扑识别的影响 这是第二类情形,表明小的耦合强度(0,0.6]对拓扑识别是有利的;当耦合强度大于0.7时识别失败. 第一类情形会有什么现象？耦合强度对Rossler系统的网络的拓扑识别的影响比较复杂。

节点差异性对识别效率的影响 从上面的分析中, 可以看到当节点动力学没有差异的时候, 是不利于拓扑识别的，而节点动力学的差异是有利于识别的。节点的差异性越大, 拓扑识别的时间越短, 效率越高。节点动力学方程为吕系统。当系统参数相差为1时，拓扑与参数识别所需时间为154.8171s；当系统参数相差为0.2时，拓扑与参数识别所需时间为1026.9s。可以看出第一组参数下的识别速度要大大快于第二组参数下的识别速度，这说明节点差异性越大，越容易满足线性无关的条件，识别的速度就越快。说明拓扑识别的效率与网络中各节点的差异性是正相关的.

系统平衡点是常数向量情况 如果系统平衡点是常数向量 考虑识别拓扑情况，只有N不大于n时，才可能识别。 这是因为当N大于n时， 在同步流形 上一定线性相关。譬如节点动力学维数n＝3，则多于3个节点就不能保证识别了。所以这种情况的拓扑识别几乎没有什么意义！

4. 某些新的识别方法和 待研究的问题

基于自适应同步的识别方法的不足 这个方法是从整体的动力学来反演动力学参数和网络所有边权，而实际问题常常并不涉及动力学方程，只是观测到部分节点的时间演化，如何反演网络拓扑结构，或者如何反演网络的部分拓扑结构。这方面工作还很少，如[12]对于具体的生物神经元网络，设计出只接收部分节点的部分状态分量（神经元模电压）的识别网络拓扑的方法 。 计算量大：需要构造响应网络和自适应律。 [12] Jin Zhou, Wenwu Yu, Xiumin Li, Michael Small, and Jun-an Lu. Identifying the Topology of a Coupled FitzHugh–NagumoNeurobiological Network via a Pinning Mechanism[J]. IEEE TRANSACTIONS ON NEURAL NETWORKS, 2009，20(10)：1679-1684

噪声诱导动力学相关性识别网络结构 文献[14]发现,在噪声的作用下,节点的时间序列的动力学相关矩阵与网络的连接矩阵存在一一对应的关系, 计算动力学相关性矩阵, 能够识别网络的连接情况。也就是说，噪声是动力学相关性与网络拓扑之间的桥梁。这个发现让我们能够通过噪声时间序列来识别网络的拓扑结构. [14] Jie Ren, Wen-Xu Wang, Baowen Li and Ying-Cheng Lai. Noise Bridges Dynamical Correlation and Topology in Coupled Oscillator Networks[J]. Phys. Rev. Lett., 2010 ，104(5): 058701-058704.

噪声诱导动力学相关性识别网络结构 考虑N个不同振子的耦合 为噪声， 为Laplacian矩阵，在无噪声解上作变分，由于噪声的存在，力学相关矩阵与连接矩阵之间存在一一对应的关系。这样根据节点的时间序列可以很容易地计算动力学相关矩阵。由于动力学相关矩阵与网络的Laplacian矩阵成反比，所以根据节点的时间序列来预测网络的拓扑结构。

噪声诱导动力学相关性识别网络结构 [14]识别的正确率依赖于阈值的选择，而阈值又与耦合强度和噪声强度的选取有关，因此如果阈值选的不合适的话,可能有些边就不能正确的被识别出来。[15]引进医学上的ROC曲线方法来选择合适的阈值,并且讨论耦合强度以及噪声强度对拓扑识别的影响.根据ROC曲线(真阳性高－有边都识别出来，假阴性低－无边不说成有边)分析方法,发现太大或者太小的耦合强度都会降低拓扑识别的准确率,而改变噪声强度却对拓扑识别没多大影响。 我们将进一步研究这三者之间的关系。 [15]Juan Chen, Jun-an Lu. Topology Identification of Complex Networks from Noisy Time Series Using ROC Curve Analysis. Chaos, in revision.

噪声有利于结构识别 含有随机噪声的复杂动力网络的识别具有重要的实际意义，基于随机微分方程的LaSalle不变原理, 设计自适应控制器。 由于系统含有随机噪声,更有利于满足在同步轨道上线性无关的条件，发现噪声有利于结构识别。 [16]吴晓群, 赵雪漪, 吕金虎，节点动力学含随机噪声的复杂动力网络拓扑结构识别，第30届中国控制会议 (CCC’2011)

格兰杰因果探测网络结构 因果分析的思想首先是Wiener提出的,他说如果加入第二个变量能使得第一个变量的预测精度提高,则第二个变量是第一个变量的因,否则不是。格兰杰因果关系（1969，Granger causality）指出,如果第一个时间序列现在的值由第一个时间序列过去的值和第二个时间序列过去的值来估计，比仅由第一个时间序列过去的值来估计使得误差项方差减小,则第二个时间序列是第一个时间序列的因,否则不是。 吴晓群提出分片格兰杰因果方法探测网络结构，效果优于传统的格兰杰因果方法。 [17] N. Wiener. The theory of prediction[M]. In: E. F. Beckenbach (Ed) Modern Mathermatics for Engineers,. McGraw-Hill, New York,1956:Chap 8. [18] C. W. J. Granger. Investigating causal relations by econometric models and cross-spectral methods[J].Econometrica,1969, 37:424-438.

其它方法 演化和增长网络的拓扑的检测和识别，目前刚刚开始研究[19]； 网络存在耦合时滞以及存在噪声和干扰情况的结构辨识问题； 如何提高结构识别的效率，即利用尽量少的节点和边的信息达到结构识别的效果，这些都是非常重要且有广泛应用前景的问题。 难免挂一漏万 [19] Zhaoyan Wu，Xinchu Fu，Guanrong Chen. Monitoring the Topology of Growing Dynamical Networks[J]. International Journal of Modern Physics C，2010，21（8）：1051-1063.

有待进一步研究的问题 为了更好地识别真实网络的拓扑结构，亟待解决: （1）如何减少网络结构辨识对节点动力学、耦合函数、时延分布等信息的依赖？ （2）如何解决每个节点只有部分状态变量甚至单一状态变量可测并且噪声存在的问题？ （3）当网络节点数据庞大，而我们只关心其中子网络的结构的时候，如何处理？

欢迎批评指正  Thank You !