《5复杂网络的同步与控制.ppt》由会员分享，可在线阅读，更多相关《5复杂网络的同步与控制.ppt（123页珍藏版）》请在三一文库上搜索。
1、Complex Network Synchronization and Topology indentification 第5讲：复杂网络的动力学同步与控制,方 锦 清(Fang Jin-Qing) 中国原子能科学研究院 China Institute of Atomic Energy,内 容 提 要,主要讨论复杂网络同步的基本概念和若干复杂网络同步的研究进展 参考：陈关荣、陆君安教授等研究论文和会议报告,1.复杂动力网络的 一般同步概念 近年非线性、连接性、以及复杂性问题的研究已取得了重要的进展。如何把复杂网络理论、动力系统理论和現代控制理论三者密切結合,深入地研究复杂动力网络的动力学特性、
2、同步与控制是一个重要课题。,Chaos Communications Francis C M Lau, Michael C K Tse, PolyU Centre for Chaos Control and Synchronization,Synchronization Is one of the most Pervasive phenomena in the Universe,同步是复杂网络的集体行为. 耦合振子之間的同步運動,Network Synchronization,起源于钟摆的发明者 惠更斯(Huygens),The study of synchronous systems cut
3、s across the disciplines of modern science. But the underlying phenomenon was first documented over three centuries ago. In 1665, Dutch physicist Christiaan Huygens lay ill in bed, watching the motions of two pendulum clocks he had built. To his surprise, he detected an “odd kind of sympathy” betwee
4、n the clocks: regardless of their initial state, the two pendulums soon adopted the same rhythm, one moving left as the other swung right. Elated, Huygens announced his finding at a special session of the Royal Society of London, attributing this synchrony to tiny forces transmitted between the cloc
5、ks by the wooden beam from which they were suspended. In 1960s, Arthur Winfree, a theoretical biologist began to study coupled oscillators,Synchronization of Clocks,Biological Clock,Self-organization in the concert-hall: the dynamics of rhythmic applause, Nature, 2001,Pedestrians make Londons Millen
6、nium Bridge wobble,Tacoma Narrows Bridge Disaster,On November 7, 1940, at approximately 11:00 AM, the first Tacoma Narrows suspension bridge collapsed due to wind-induced vibrations. Situated on the Tacoma Narrows in Puget Sound, near the city of Tacoma, Washington, the bridge had only been open for
7、 traffic a few months.,2.复杂动力网络的 一般理论框架,复杂动力网络的一般理论模型,为内连矩阵,为t 时刻的耦合矩阵(反映连接强度) 。,即写成 其中c是耦合强度， 是0-1矩阵 如果设:A为耗散矩阵（行和为0： ), 且不可约矩阵(连通)，则经常写成 如果A是常数矩阵，内联是自治的,则动力网络是非时变的，否则是时变动力网络。,例：两个节点（Lorenz系统）的双向连接,网络同步定义: 首先定义同步流形为线性子空间 如果当 时，x趋近于M，则称网络同步. 即 对于所有的节点，在任意初始条件下,对于耗散耦合 ，则有特征值 零特征值对应的右特征向量为1,1,1，它对应同步流
8、形。 A为扩散矩阵时，同步流形一般是指孤立节点（动力系统）解，它满足 所谓同步也就是所有节点状态在横截同步流形的N-1维子空间上的投影渐近地趋于零。 研究同步关心：A 和 的特征值，动力系统f的Lipschitz条件,同步判定准则,主稳定函数方法(P-C，1998，Master stability function approach) 假定耦合矩阵A(t) = A 是一常量矩阵, 且耦合函数 是线性的且是自治的. 则在同步态s(t) 处作线性化处理, 经过等价的线性变换过程, 可以得到变分方程,注意到：耗散耦合的条件, = 0 总是耦合矩阵的一个特征值, 且其特征向量(1,1,1)对应了同步流
9、形的模式. 故判断同步流形的稳定性只需判断下 面N-1 个方程的稳定性即可 如果考虑到当耦合矩阵A 为非对称阵时，其特征值可能为复数, 令 , 这就定义了动力网络的主稳定方程(Master Stability Function (MSF).,由于计算节点数目巨大网络的横向Lyapunov 指数是一项艰苦的工作. 在比较具有相同动力学的网络的同步能力时, 提出最大横向Lyapunov 指数 的区域为同步化区域 （C为复平面）,它是由孤立节点上的动力学函数、耦合强度、以及外耦合矩阵和内耦合矩阵函数确定的. 根据同步域的不同, 可以把动力网络分为以下三类: 类型-A: 同步域无界; 类型-B: 同步
10、域有界; 类型-C: 同步域为空, 此时网络无论在什么参数条件下都不能实现同步.,如果耦合矩阵对称，则特征值在实轴： （1）同步域无界： 越接近于0，则同步能力越弱； （2）同步域有界：比值 越接近于1，则同步能力越强； （3）同步域为空集：则对于任意耦合强度和耦合矩阵都无法实现同步。,连接图稳定性方法(最近俄罗斯学者提出的一种新的研究网络同步的方法) 结合Lyapunov函数方法与图理论 优点: 1)避免计算Lyapunov指数与耦合矩阵的特征值; 2)可以估计网络中每条边的耦合强度; 3)适合时变网络; 缺点: 耦合强度下界估计保守,同步判定准则,定理 如果耦合网络中边的耦合强度 对于任意
11、t都有下式成立： 其中 为两个振子全局同步的耦合强度的两倍，N和m是节点和边数， 为网络中通过边k的满足j I 的所有最短路径（选择路径）Pij 的长度的总和，则系统的同步流形是全局渐近稳定的。,3.网络同步的主要问题 时变与非时变网络，不确定网络 同步类型：严格同步，投影同步，相同步，广义同步 耦合形式：线性耦合，非线性耦合，时滞耦合，脉冲耦合，Blinking模型； 同步方法：线性反馈，非线性反馈，自适应方法，脉冲反馈，变量替换驱动,混沌同步分类（Classification of Chaos Synchronization）,Identical Synchronization,Gener
12、alized Synchronization in Non-Identical Chaotic Systems,Dynamical Network Model,A network of N n-D dynamical nodes (oscillators) c0 coupling strength coupling matrix Synchronization state: The synchronizability of a network with respect to a specific coupling configuration is said to be strong if th
13、e network can synchronize with a small coupling strength c.,Dynamical Network Model,Consider a network consisting of N identical linearly and diffusively coupled nodes. Each node is a n-D (chaotic) dynamical system Network equations: state of node i; c0 coupling strength inner coupling matrix networ
14、k coupling matrix if there is a link between node i and j ki is the degree of node i,Network Synchronization,Network Synchronization Complex Dynamics Typical networks: coupled map lattice, cellular neural networks Typical dynamics: Turing patterns, autowaves, spiral waves, spatiotemporal chaos Netwo
15、rk Synchronization Synchronization in Small-World Networks Synchronization in Scale-Free Networks Robustness vs Fragility in Network Synchronization,Synchronization Theorem,Let be the eigenvalues of the coupling matrix A. The synchronization state is exponentially stable, if where is a constant dete
16、rmined by f and The synchronizability of a network with respect to a specific coupling configuration is said to be strong if the network can synchronize with a small coupling strength c. The synchronizability can be characterized by the second-largest eigenvalue of the coupling matrix A,Synchronizat
17、ion in regular coupled networks,Globally coupled network: No matter how small the coupling strength is, a global coupled network will synchronize if its size is sufficiently large. Locally coupled network: No matter how large the coupling strength is, a locally coupled network will not synchronize i
18、f its size is sufficiently large,Synchronization in small-world networks,Synchronizability can be greatly enhanced by just adding a tiny fraction of long-range connections, revealing an advantage of small-world network for synchronization,X.F.Wang and G.R.Chen: Int. J. Bifurcation & Chaos (2001),Add
19、 a few distant links,Small world model,Locally coupled model,Synchronization in scale-free networks,The synchronizability of a SF network is about the same as that of a star network. This is due to the extremely inhomogeneous connectivity distribution of a SF network: a few hubs in a SF network play
20、 a similar role as a single center in a star network.,X.F.Wang and G.R.Chen: IEEE T-CAS (2002),Synchronization in SF Networks: Robustness and Fragility,X.F.Wang and G.R.Chen: IEEE T-CAS (2002),Robust against random failures: Even when as many as 5% randomly chosen nodes are removed, the synchronizab
21、ility of the network is almost unchanged. Fragile to Intentional Attacks: The removal of only 1% of the most connected nodes would result in a drastic decrease in the synchronizability of network. This is due to the extremely inhomogeneous connectivity distribution of the SF network.,Synchronization
22、 in Globally Connected Networks,Observation: No matter how large the network is, a global coupled network will synchronize if its coupling strength is sufficiently strong Good if synchronization is useful,Synchronization in Locally Connected Networks,Observation: No matter how strong the coupling st
23、rength is, a locally coupled network will not synchronize if its size is sufficiently large Good - if synchronization is harmful,Synchronization in Small-World Networks,Start from a nearest-neighbor coupled network,Add a link, with probability p, between a pair of nodes,Small-World Model Good news:
24、A small-world network is easy to synchronize !,X.F.Wang and G.R.Chen: Int. J. Bifurcation & Chaos (2001),Synchronization in small-world networks,For any given N,2sw decreases to N as p increases from 0 to 1 Meaning: for any given N, there exists a critical p* such that the network will synchronize i
25、f pp*.,X.F.Wang and G.R.Chen: Int. J. Bifurcation & Chaos (2001),Synchronization in small-world networks,For any given p0, 2sw decreases to - as N Meaning: for any given p0, there exists a critical N* so that the network will synchronize if NN*,X.F.Wang and G.R.Chen: Int. J. Bifurcation & Chaos (200
26、1),Synchronization in small-world networks,In summary, the ability to achieve synchronization in a nearest-neighbor coupled network can be greatly enhanced by just adding a tiny fraction of long-range connections, revealing an advantage of small-world network for synchronization,X.F.Wang and G.R.Che
27、n: Int. J. Bifurcation & Chaos (2001),Synchronization in scale-free networks,Due to the self-organization process of a scale-free network, the synchronizability of a SF network will remain almost unchanged by the constantly adding of new nodes. The synchronizability of a SF network is about the same
28、 as that of a star network. This may be due to the extremely inhomogeneous connectivity distribution of a SF network: a few hubs in a SF network play a similar role as a single central node in a star network.,Synchronization in Scale-Free Networks,X.F.Wang and G.R.Chen: IEEE T-CAS (2002),Robust agai
29、nst random attacks and random failures Fragile to intentional attacks and purposeful removals of big nodes Both are due to the extremely inhomogeneous connectivity distribution of scale-free networks,Synchronization in SF Networks: robustness against random failures,X.F.Wang and G.R.Chen: IEEE T-CAS
30、 (2002),Even when as many as 5% randomly chosen nodes are removed, the synchronizability of the network is almost unchanged. This is due to the extremely inhomogeneous connectivity distribution of the SF network: If m removed nodes are randomly selected, then it is quite possible that m small nodes
31、are selected.,Synchronization in SF Networks: fragile to intentional attacks,X.F.Wang and G.R.Chen: IEEE T-CAS (2002),The removal of only 1% of the most connected nodes would result in a drastic decrease in the synchronizability of the network. This is also due to the extremely inhomogeneous connect
32、ivity distribution of the SF network.,Useful Synchronization in Engineering,Examples: Secure communication Harmonic oscillations generation Language emergence and development: Synchronization in conversations common vocabulary Organization management: Agents synchronization work efficiency ,Harmful
33、Synchronization in Internet,TCP window increase/decrease cycles Synchronization occurs when separate TCP connections share a common bottleneck router Synchronization to an external clock Two processes can become synchronized simply if they are both synchronized to the same external clock Client-serv
34、er models Multiple clients can become synchronized as they wait for services from a busy (or recovering) server Periodic routing messages Periodic routing messages from different routers can become synchronized,3.复杂网络同步方法的 若干进展,同步是复杂动力网络的一种基本的动力行为，如何定量刻画网络的同步能力,网络拓扑结构如何影响同步行为，什么样的网络拓扑结构最有利于同步,动力学行为如
35、何影响网络拓扑结构，这些问题无论在理论上还是在实际上都具有十分重要的意义。 复杂动力网络的同步成为当前国内外研究的一个热点和前沿领域。,3.1 不确定网络的 自适应同步方法 文献参考： Jin Zhou, Jun-an Lu, Jinhu L, Adaptive Synchronization of An Uncertain Complex Dynamical Network， IEEE Transactions on Automatic Control, 2006, 51（4）, 652-656,一般的不确定网络的自适应同步,同步的局部渐进稳定性,同步的全局渐进稳定性,数值试验： 50个Lo
36、renz系统耦合网络的误差图,3.2 含时滞复杂网络的 自适应同步方法 参考文献 Qunjiao Zhang, Junan Lu, Jinhu L, and Chi K. Tse，Adaptive Feedback Synchronization of a General Complex Dynamical Network with Delayed Nodes， IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMSII: 55( 2), 2008, 183-187 Qunjiao Zhang, Junan Lu, and Jinhu L，Synchronizati
37、on of a General Delayed Complex Dynamical Network via Adaptive Feedback, Proceedings of 2008 IEEE International Conference on Networking, Sensing and Control Sanya, China, April 6-8, 2008，1818-1822，获IEEE Best Student Paper Award Tu LL, Lu JA, Stability of a model for a delayed genetic regulatory net
38、work , DCDIS 13 (3-4):429-439 （含时滞基因调节网络渐近稳定性的充分条件）,矩阵C行和为0,3.3 牵制控制与同步 参考文献 Zhou Jin , Lu Jun-an, L Jinhu , Pinning adaptive synchronization of a general complex dynamical network , Automatica , 44, 2008, 996 1003 Jin Zhou , Xiaoqun Wu , Wenwu Yu , Michael Small , and Jun-an Lu，Pinning synchronizat
39、ion of delayed neural networks，Chaos ，2008.12 (in press),3.4 时变离散生态网络的同步（一致性） 参考文献 Liang Chen , Jinhu L, Jun-an Lu , and David John Hill，Local asymptotic coherence of time-varying discrete ecological networks， Automatica, in press,时不变离散生态网络的局部渐近一致性理论不能充分的说明真实的复合种群的实际情况. 因此需要提出一个时变的离散生态网络，获得局部和全局的渐进一
40、致性几个基本准则, 这对于生态系统的发展和湮灭过程的研究提供了一些新的观点. 时不变离散生态网络的渐近一致性是完全由种群动力系统和复合种群的耗散矩阵的特征值决定的. 而我们发现: 时变离散生态网络的渐近一致性除了依赖于单个种群动力系统的稳定性和复合种群的耗散矩阵的特征值两因素之外, 还依赖于其特征值对应的特征向量.,Xiao Fan Wang & Guanrong Chen Synchronization in Small-World dynamical networks (Int. J. Bifur. & Chaos, January2002) Synchronization in Scal
41、e-Free Networks: Robustness and Fragility (IEEE Trans. Circuits & Systems, January 2002) Pinning Control of Scale-Free Dynamical Networks (Physica A, June 2002),Dynamical Network Model,A network of N n-D dynamical nodes (oscillators) c0 coupling strength coupling matrix Synchronization state: The sy
42、nchronizability of a network with respect to a specific coupling configuration is said to be strong if the network can synchronize with a small coupling strength c.,Synchronization in regular coupled networks,Globally coupled network: No matter how small the coupling strength is, a global coupled ne
43、twork will synchronize if its size is sufficiently large. Locally coupled network: No matter how large the coupling strength is, a locally coupled network will not synchronize if its size is sufficiently large,Synchronization in small-world networks,Synchronizability can be greatly enhanced by just
44、adding a tiny fraction of long-range connections, revealing an advantage of small-world network for synchronization,X.F.Wang and G.R.Chen: Int. J. Bifurcation & Chaos (2001),Add a few distant links,Small world model,Locally coupled model,Synchronization in scale-free networks,The synchronizability o
45、f a SF network is about the same as that of a star network. This is due to the extremely inhomogeneous connectivity distribution of a SF network: a few hubs in a SF network play a similar role as a single center in a star network.,X.F.Wang and G.R.Chen: IEEE T-CAS (2002),Synchronization in SF Networ
46、ks: Robustness and Fragility,X.F.Wang and G.R.Chen: IEEE T-CAS (2002),Robust against random failures: Even when as many as 5% randomly chosen nodes are removed, the synchronizability of the network is almost unchanged. Fragile to Intentional Attacks: The removal of only 1% of the most connected node
47、s would result in a drastic decrease in the synchronizability of network. This is due to the extremely inhomogeneous connectivity distribution of the SF network.,Synchronization behavior in complex network environments Still many open problems,To what extent does the proposed model for synchronizati
48、on behavior capture the essential tradeoffs observed in real synchronization environments? Might there be such a thing as the “canonical“ model for synchronization behavior in complex networks? To what extent does network topology, specifically a small-world network structure, affect both the qualit
49、ative and quantitative synchronization behaviors?,CS is considered to be significant in social networks, communication engineering, biological sciences. Studied results imply that the approach to constructing coupling schemes can stabilize the selected CS patterns, but it largely depends on the choice of the coupling schemes. Different coupling schemes may results in different CS.,Clu