程序代写代做代考 graph C clock Complex Networks: Lecture 7: Network Synchronization

Complex Networks: Lecture 7: Network Synchronization
EE 6605
Instructor: G Ron Chen
Most pictures on this ppt were taken from un-copyrighted websites on the web with thanks

Sync Video

Synchronization
(Christiaan Huygens, 1665)
Huygens invented the pendulum clock and observed their synchronization

DEMO

Fireflies Synchronization
Attitude Alignment
The attitude of each spacecraft is synchronized with its two adjacent neighbors via a bi-directional communication channel

Synchronization-based Laser
Astounding coherence of a laser beam comes from trillions of atoms pulsing in concert, all emitting photons of the same phase and frequency

Electric Currents
Through Josephson Junctions
Oscillate as One
Phase Sync
DEMO
Simulation

Pedestrians Make London’s Millennium Bridge Wobble
June 10, 2000
Video

Out of tumultuous applause:
Synchronized claps
Self-organization
in the concert-hall:
the dynamics of rhythmic applause
— Nature (2001)

Birds Flocking
Flocking: to congregate or travel in flock

Fish Swarming
 Swarming:
to move or gather in group

Consensus
A position reached by a group as a whole
Battle space management scenario

Useful Synchronization Examples:
 Secure communications
 Generation of harmonic oscillations
 Language emergence and development: Synchronization in conversations
common vocabulary
 Organization management: Agents’ synchronization
 work efficiency
 Biological systems (brain, heart)
……

Harmful 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-server models
Multiple clients can become synchronized as
they wait for services from a busy (or recovering) server
 Periodic message routing
 ……

Communication Networks

One Example
In mammals, a small group of neurons in the brain stem, named pre-Bötzinger complex, is responsible for generating a regular rhythmic output to motor calls that initiate a breath.
non-synchrous
synchrous

Euler discovered mechanical resonance in 1750
Leonhard Euler, “De novo genere oscillationvm”, Comm. Acad. Sci. Petrop, 11 (1139), 128-149, 1750.

Norbert Wiener
(1894-1964)
 Collective synchronization was first studied mathematically by Wiener, who recognized its ubiquity in the natural world, and speculated that it was involved in the generation of alpha rhythms in the brain.
 Unfortunately, Wiener’s mathematical approach based on Fourier integrals has turned out to be a dead end.
 N. Wiener, Nonlinear Problems in Random Theory, MIT Press, 1958
 N. Wiener, Cybernetics, MIT Press, 1st ed., 1948, 2nd ed., 1961.

Network Synchronization
 Network Synchronization versus Individual Dynamics  Typical networks: coupled map lattices, cellular
neural networks, complex networks
 Typical dynamics: Turing patterns, autowaves, spiral waves, spatiotemporal chaos
 Network topology and the dynamics of individual nodes determine the network dynamical behaviors  Synchronization

Dynamical Network Model
Example: (undirected)

A General Dynamical Network Model
Linearly and diffusively coupled:
xif(xi)c aH(x)
dynamics: f(.) – Lipschitz function coupling strength c > 0
couplingmatrices A[a ]
ij NN
x xi Rn i   
i1,2,…,N
x1  N i
 j1
2
xn  i
H1(xj ) H (x )
ij j
H(x ) 2 j 
j
   Hn (xj )

D  [dii ]  diag{k1,…, kN } Laplacian matrix L = D – A
(zero row sum: diffusive coupling)

N xif(xi)c aH(x)
 j1
ij j
3 1 1 0 1 
Examples
1 3 1 1 0
L  1 1 2 0 0 
0 1 0 1 0
1 0 0 0 1 
symmetrical, diffusive, irreducible, zero row-sum
eigenvalues of L:
0 5 5, 5 13
1 2,3 2 2 4,5 2 2
L1 1 1 1
eigenvaluesofL:  0  2 1 2

x  f ( x )  c ii
Complete state synchronization:
State tracking:
 j1
a H ( x ) x  R n i  1 , 2 , . . . , N ij j i
Network Synchronization
N
lim||x(t)x (t)||0,
i,j1,2,,N xi (t)  s(t) i  1,2,…, N
t
ij2

Network Synchronization
x  f ( x )  c ii
 j1
a H ( x ) x  R n i  1 , 2 , . . . , N ij j i
x[xT,xT,…,xT ]T 12N
N
Put all equations together with Then linearize it at equilibrium s :
x [IN [f (s)]]c[A[H(s)]]x f (.) Lipschitz, or assume: || f (s) ||  M
Only
cA or {ci } is important
After linearization, perform local analysis

Network Synchronization: Criteria x[I [f(s)]]c[A[H(s)]]x 0  
12N Master stability equation: (L.M. Pecora and T. Carroll, 1998)
N
y  [ [  f ( s ) ]   [  H ( s ) ] ] y , Maximum Lyapunov exponent
Lmax Lmax
  i n f { c  i ( s ) , i  2 , 3 , . . . , N } Lmax is a function of 
Lmax
Smax — sync region
or if S2 (2,3) 02 3 
Synchronizing: if S1 (1,)
01 

A Linearization Approach
Recall:Eigenvaluesof LDA 0   12N
Synchronizing: if
01c2 orif 022 3 N
Case I: Case II: No sync Sync region
S1 (1,)
2 bigger is better
Case III: Sync region
bigger is better
Case IV: Union of intervals
(X. F. Wang and G. Chen, 2002)
(M. Banahona and L. M. Pecora, 2002)
2 N
S2 (2,3)

/, 0 2N12N
c , 0   212N

Synchronization in Regularly Coupled Networks
Globallycouplednetwork: 2 N N
Usually, no matter how small the coupling strength c is, a global coupled network will synchronize if its size is sufficiently large
K/2 
j1
Usually, no matter how large the coupling strength c is, a locally coupled network will not synchronize if its size is too large
Locallycouplednetwork:  4 2
sin2j/N
Wang and Chen (2002)

Synchronization in Regularly Coupled Networks
Star-shaped network:
Usually, the size of the network does not matter:
2 N1 1, N N
When the coupling strength c is strong enough,
the coupled network will synchronize. Lattice:
S. Arora and M.S. Santhanam (J. Applied Nonl. Dynamics, 2014)

Synchronization in Small-World Networks
Synchronizability can be greatly enhanced by adding a tiny fraction of long-range connections, revealing an advantage of small-world network for synchronization
Wang and Chen (2002)

Synchronization in Scale-Free Networks
The synchronizability of an assortative SF network is about the same as that of a star-shaped network, mainly determined by the (one-to-one) relations between the central node and the neighboring nodes

Network Topology versus Synchronizability Connection Probability:
Synchronizability of small-world networks will increase as the small-world feature increases
Hong, et al. (2004)
Larger p /
Smaller N 2 (Criterion II)

Better synchrony
p = 1  fully connected

Network Topology versus Synchronizability Power-Law Exponent:
Synchronizability of scale-free networks will increase as the power-law exponent increases
Nishikawa, et al. (2003)


SmallerN /2 (Criterion II)

Better synchrony
Larger

Network Topology versus Synchronizability Betweenness Centrality:
Synchronizability of small-world will increase as the node betweenness decreases
p

Smaller
node betweenness

Better synchrony
(p = 1fully connected)
Hong et al. (2004)
Larger

Betweenness versus Synchronizability
Homogeneous Networks –
there is a clear correlation between betweenness and synchronizability

Betweenness versus Synchronizability
Heterogeneous Hetworks – there is no clear correlation between betweenness and synchronizability for scale-free networks with large exponents in power-law

Enhancing Network Synchronizability
Two examples:
 Perturbing the network structure To eliminate the maximal betweenness
 Modifying the coupling structure
To reduce the impact of the heterogeneity of degree and betweenness distributions

Perturbing Network Topology
(Zhao, et al. Phys. Rev. E 2005, 72: 057102)
The node with the largest betweenness is replaced by several connected nodes, so that the shortest paths that passed through the original node will now only pass one or two new nodes, which will reduce the maximal betweenness dramatically

Simulation Results
Fraction of divided nodes

Decoupling Method
(scale-free networks)
(CY Yin, et al., Phys. Rev. E 2006, 74: 047102)
Not only the nodes with large betweenness, but also the edges with large loads can cause data-traffic congestion
Hence, if such heavily-loaded edges are decoupled, the data-traffic will be redistributed so become more efficient

Simulation Results
For scale-free networks, smaller eigen-ratio R’/R0 implies better synchronizability, where m is the number of new edges in the scale-free networks generation

BREAK
10 minutes

Graph-Theoretic Approach
 Relationships between structural parameters and the synchronizability of complex networks
 Relationships between graph theory and the synchronizability of complex networks
 Enhancing network synchronizability

Structure versus Synchronizability  Network Model:
N
 j1
0   (2) 12N
 Synchronization of network (1) :
x i  f ( x i )  c
 Laplacian matrix L: symmetric, diffusive and irreducible,
with eigenvalues
a H ( x ) , ij j
i  1 , 2 ,  , N
( 1 )
lim||x(t)x (t)||0, i,j1,2,,N t i j 2
(3)

 Remark 2: Key factors influencing the synchronizability: (i) inner-coupling matrix H
(ii) eigenvalues of outer-coupling matrix A  Synchronizability in terms of (ii):
1. bounded region (M. Banahona and L. M. Pecora, 2002) /, 0
2N12N
2. unbounded region (X. F. Wang and G. Chen, 2002)
c , 0   212N
3. union of several disconnected regions (A. Stefanski, P. Perlikowski, and T. Kapitaniak, 2007)
(Z. S. Duan, C. Liu, G. Chen, and L. Huang, 2007)
Recall:
N
xi  f(xi)caijH(xj), i1,2,,N (1)
j1

 Structural parameters that may affect the synchronizability:
average distance, degree distribution, clustering coefficient, node betweenness, …
 Question:
How does synchronizability depend on various structural parameters?

Graph G1
Two simple graphs
Graph G2
 They have the same structural characteristics:
Graphs G1 and G2 have
 the same degree sequence: all node degrees: 3  the same average distance: 7/5
 the same node-betweenness centrality: 2

But they have different synchronizabilities:
eigenvalues of G1 are 0, 3, 3, 3, 3 and 6 eigenvalues of G2 are 0, 2, 3, 3, 5 and 5
 (G )3 (G )2 21 22
Let  2 /N Then
(G )0.5(G )0.4
12
About edge-adding:
Lemma 1: For any given connected undirected graph G , all its nonzero eigenvalues will not decrease with the number of added edges, i.e.,
by adding any edge e, one has i (G  e)  i (G). Z. Duan, G. Chen, and L. Huang (2007)

Lemma 1If the synchronized region is unbounded, then adding edges never decrease the synchronizability. Main reason: i (G  e)  i (G)
However, for bounded synchronized regions, this is not necessarily true because the eigen-ratio can either increase or decrease
Example: Adding an edge between red node
and pink node in the graph G1 : e{red, pink}
leads to a new graph G  e{red, pink}, whose 1
eigenvalues are 0, 2.2679, 3, 4, 5 and 5.7321, with (G e{red,pink})0.3956 ,smallerthan
 (G )  0.5 1
2 N
1
2 N


GG2 e{red,pink}e{blue,green}e{green,brown} 
The synchronizability may have other (yet unknown) relationships to the common network structural parameters

Complementary Graphs:
.
particularly when they are disconnected
 For a given graph G, the complement of G is the graph containing all the nodes of G , and the edges that are not in G, denoted by Gc
 The complements of G1 and G2 :
G c G Gc 1 G1 2 2

 Lemma 2: For any given graph G :
(i) the largest eigenvalue of G, N (G), satisfies N (G)  N
(ii) N (G)  N if and only if Gc is disconnected. Moreover,
if Gc has (exactly) q connected components, then the
multiplicity of N (G)  N as an eigenvalue of G is q 1
(iii)  (Gc )  N   (G), 2  i  N i Ni2
Recall: G1 has eigenvalues: 0, 3, 3, 3, 3, 6

 Remark 3: With the same number of edges, generally the synchronizability of a network built on graph G is better when Gc has three (or more) disconnected components than the case that Gc has only two disconnected components, since in the former case, the multiplicity of the largest eigenvalue of G is larger than 1. This implies that some edges there have no
c
G
contributions to the synchronizability.
 Remark 4: Better understanding and careful manipulation of complementary graphs are effective for enhancing network synchronizability

Disconnected Synchronized Regions
Typical types of synchronized regions:
 Type I: empty
 Type II: unbounded
 Type III: bounded
S1 (1,) S2 (1,2)
 Type IV: union of some of the above
(1,2 )(3,) (1,2)(3,4)(5,6) and so on
A. Stefanski, P. Perlikowski, and T. Kapitaniak, (2007) Z. Duan, G. Chen, and L. Huang, (2007)

 When the synchronous state is an equilibrium, the synchronized region problem reduces to a stability problem of the matrix pencil F H with respect to parameter .
(F is the Jacobian and H is the inner-linking matrix)
 Theorem: For any natural number n , there are two matricesFandHoforder2(n1) suchthatFH has n disconnected stable regions with respect to parameter .
 Recall:
i  i xi s
 j1
ij x s  i i 
x i  f ( x i )  c
 j1
a H x , i  1 , 2 ,  , N ( 1 ) ij j
N
N x[Df(x)] c a[DH] x
Z. Duan, G. Chen, and L. Huang (2007)

Examples of networks with disconnected synchronized regions
Example: Consider network
N
 j1
x i  f ( x i )  c
with third-order smooth Chua’s circuits, namely,
i  1 , 2 ,  , N each node is a Chua’s circuit described by
x kx kx k(ax3 bx ) i1 i1 i2 i1 i1
x kx kx kx i2 i1 i2 i3
x i 3   k  x i 2  k  x i 3
(2)
a H x , ij j
( 1 )

Chua’s Circuit:
dv1  1G(v v)f(v) dtC21 1
1
dv2  1 G(v v )i 
dt C 1 2 3  2
di3 1v2 R0i3 dt L
f ( v 1 )  G b v 1  12 ( G a  G b )  v 1  E  v 1  E 
v v R 1

Chua’s attractor
Leon O Chua
(1936 – )

Linearizing (2) at the zero equilibrium yields
  k  kb k 0  dxi /dtFxi, F k k k   0 kk
Take k1,0.1,1,1,a1,b25, and
 0.8348 H   0.1002
9.6619
2.6591 
0.0694  8.5837
0.1005   0.9042 
  0.3254
Then F H has a disconnected stable region:
S [0.0099,0][2.225,1)

 Suppose that the number of nodes of network (1) is
N  10 and the outer coupled matrix A is a globally coupled matrix. Then network (1) with the above data achieves local synchronization when the coupling strength c satisfies
c [0, 0.00099]
 Figures below visualize the synchronization and non-synchronization behaviors of this network
or
c(0.1,0.2225]

(b) c0.2(0.1,0.2225]. Fig. 1 Synchronization of network (1) with different coupling strengths.
(a) c0.0005[0,0.00099].
(d) c0.3(0.2225,).
Fig. 2 Non-synchronization of network (1) with different coupling strengths.
(c) c0.02(0.001,0.1).

 Example: An interesting example of the coexistence of unbounded and bounded synchronization regions in the
S (,1)(2,3)
Consider a linearly and diffusively coupled dynamical
form of
network with the state equations
where
N
 j1
x i  F x i  c
14 0 1 100
( 3 )
F0 7 1, H0 0 0. 16
2 3723 23 0 0 0  1616 16  
a H x , ij j
i  1 , 2 ,  , N ,


11
S, (3 2)(3 2),0
44
c [0, 0.07929) c  (0.22071,  ).

(a) c0.04[0,0.07929). (b) c0.14(0.07929,0.22071). (c) c1(0.22071,).
Fig. 3 Synchronization and non-synchronization of the first state variables of the five nodes in network (3) in the global coupling configuration: xi1(t),i1,,5.

More …

Phase Synchronization
Assume each node is a periodic oscillator
x  f ( x )
Examples: Van der Pol, Hodgkin-Huxley, Duffing oscillator…

A canonical model for periodic oscillator

where  is the phase and  is the frequency

Phase Synchronizations

Phase Synchronization
In-phase Anti-phase

Phase Synchronization
Shifted-phase

Winfree’s Pioneering Work
N
i i X(j)Z(i)
 j1 
 When the spread of natural frequencies is large compared to the coupling, the system behaves incoherently, with each oscillator running at its natural frequency.
 As the spread is decreased, the incoherence persists until a certain threshold is crossed —then a small cluster of oscillators suddenly freezes into synchrony.
A. T. Winfree, The Geometry of Biological Time, Springer, NY, 1980.

Kuramoto Model
KN
i i Nsin(j i)
j1

Order Parameter
 To visualize the dynamics of the phases, it is convenient to imagine a group of points running around the unit circle in the complex plane:
1N
rei  eij
N
j1
r~1
r~0

Synchronization Threshold
KN
i i Nsin(j i)
j1
r e i   1 N e i  j
N j1
J. A. Acebrón, et al: Rev. Mod. Phys. 77 (2005) 137

End