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:
xif(xi)c aH(x)
dynamics: f(.) – Lipschitz function coupling strength c > 0
couplingmatrices A[a ]
ij NN
x xi Rn i
i1,2,…,N
x1 N i
j1
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 xif(xi)c aH(x)
j1
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
L1 1 1 1
eigenvaluesofL: 0 2 1 2
x f ( x ) c ii
Complete state synchronization:
State tracking:
j1
a H ( x ) x R n i 1 , 2 , . . . , N ij j i
Network Synchronization
N
lim||x(t)x (t)||0,
i,j1,2,,N xi (t) s(t) i 1,2,…, N
t
ij2
Network Synchronization
x f ( x ) c ii
j1
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 {ci } 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) 02 3
Synchronizing: if S1 (1,)
01
A Linearization Approach
Recall:Eigenvaluesof LDA 0 12N
Synchronizing: if
01c2 orif 022 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
j1
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
sin2j/N
Wang and Chen (2002)
Synchronization in Regularly Coupled Networks
Star-shaped network:
Usually, the size of the network does not matter:
2 N1 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)
SmallerN /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 = 1fully 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
j1
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,j1,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
xi f(xi)caijH(xj), i1,2,,N (1)
j1
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 1If 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
GG2 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 Ni2
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(n1) suchthatFH has n disconnected stable regions with respect to parameter .
Recall:
i i xi s
j1
ij x s i i
x i f ( x i ) c
j1
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
j1
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 kx kx 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 1G(v v)f(v) dtC21 1
1
dv2 1 G(v v )i
dt C 1 2 3 2
di3 1v2 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 kb k 0 dxi /dtFxi, F k k k 0 kk
Take k1,0.1,1,1,a1,b25, 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) c0.2(0.1,0.2225]. Fig. 1 Synchronization of network (1) with different coupling strengths.
(a) c0.0005[0,0.00099].
(d) c0.3(0.2225,).
Fig. 2 Non-synchronization of network (1) with different coupling strengths.
(c) c0.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
j1
x i F x i c
14 0 1 100
( 3 )
F0 7 1, H0 0 0. 16
2 3723 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) c0.04[0,0.07929). (b) c0.14(0.07929,0.22071). (c) c1(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),i1,,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)
j1
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 Nsin(j i)
j1
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 eij
N
j1
r~1
r~0
Synchronization Threshold
KN
i i Nsin(j i)
j1
r e i 1 N e i j
N j1
J. A. Acebrón, et al: Rev. Mod. Phys. 77 (2005) 137
End