Enhancing synchronization by directionality in complex networks
An Zeng1,3 , Seung-Woo Son2 , Chi Ho Yeung3 , Ying Fan1 and Zengru Di1∗
1
arXiv:1012.0203v1 [cond-mat.dis-nn] 1 Dec 2010
Department of Systems Science, School of Management and Center for Complexity Research,
Beijing Normal University, Beijing 100875, China
2
Complexity Science Group, Department of Physics and Astronomy,
University of Calgary, Calgary, AB, Canada T2N 1N4
3
Department of Physics, University of Fribourg, Chemin du Musee 3, 1700 Fribourg, Switzerland
(Dated: November 3, 2018)
We proposed a method called residual edge-betweenness gradient (REBG) to enhance synchronizability of networks by assignment of link direction while keeping network topology and link weight
unchanged. Direction assignment has been shown to improve the synchronizability of undirected
networks in general, but we find that in some cases incommunicable components emerge and networks fail to synchronize. We show that the REBG method can effectively avoid the synchronization
failure (R = λr2 /λrN = 0) which occurs in the residual degree gradient (RDG) method proposed in
Phys. Rev. Lett. 103, 228702 (2009). Further experiments show that REBG method enhance
synchronizability in networks with community structure as compared with the RDG method.
PACS numbers: 89.75.Hc, 05.45.Xt, 89.75.Fb
Synchronization is an important phenomenon in various fields including biology, physics, engineering, and
even sociology [1]. In particular, synchronization in complex networks has been intensively studied in the past
decade [2–10]. One important objective in these studies is
to enhance the synchronizability [7–10], i.e., the ability to
coordinate oscillators in synchronization. Many related
methods based on node properties and link weight have
been proposed. For example, some researchers took into
account the degree centrality [7, 8], the betweenness [9]
and the node age [10, 11], and assigned weight on links
to enhance synchronizability. Nishikawa and Motter proposed to assign zero weight to particular links which lead
to an oriented tree with normalized input strength and
no directed loop [12, 13]. Moreover, they proved that
tree is the optimal structure on which synchronizability
is highest. Recently, the shortest oriented spanning tree
is shown to be the optimal structure for both synchronizability and the convergence time [14, 15]. However, these
methods are all based on assigning weights to links, where
the influences of link direction on synchronization have
not been intensively considered [1].
How to improve synchronization in directed network
is still an unsolved problem. Though previous works
suggest that hierarchical structure and the absence of
feed-back loop can enhance synchronizability, the underlying mechanism is not clear. On the other hand, the
directionality plays a significant role in the dynamic of
networks [16–19]. With the understanding of relations
between link direction and synchronization, a lot of applications can be made [1]. For example, simply regulating the direction of the phase signal of alternating current can facilitate phase match in power grids without
additional construction cost in the topology. With this
∗ Email:
zdi@bnu.edu.cn
in mind, the authors in Ref. [20] proposed the residual
degree gradient (RDG) method to enhance directed networks’ synchronizability by assigning only the direction
of links without changing the entire topology and link
weights. They also claimed that RDG method can enhance the network synchronization, contrary to the randomly assigned directional method.
However, instead of enhancing synchronizability, we
find that the RDG method results in incommunicable components in some particular cases, which lead to
graphs incapable of complete synchronization. Incommunicable components of a network correspond to the
components on which information cannot be transmitted
from one to the other in either direction. Under these circumstance, the networks can never reach complete synchronized state. In this paper, we propose the so-called
residual edge-betweenness gradient (REBG) method to
resolve the problem of incommunicable components in
the RDG method. By evaluating the betweenness on
all edges, we devise an algorithm to assign link direction. The effectiveness of the algorithm lies in the use
of edge betweenness, which embeds global information,
as compared to the node degree which reflect only local
information. We find that REBG is effective in enhancing synchronizability without leading to incommunicable
components in most network topologies.
To begin our analysis, we make use of the Master
Stability Function which allows us to use the eigenratio R = λmin /λmax of the Laplacian matrix to represent
the synchronizability of a network, with λmin and λmax
denote respectively the smallest nonzero eigenvalue and
the largest eigenvalue [21–23]. Specifically, 0 ≤ R ≤ 1,
the larger the value of R, the stronger the synchronizability of networks. According to Ref. [10, 20], we use the
real part of eigenvalues from the Laplacian matrix to investigate the propensity for synchronization in directed
networks. However, instead of setting R = λrmin /λrmax
(superscript r denotes the real part of complex number),
2
9
6
8
7
1
2
5
3
4
2
5
3
4
(a)
9
6
8
7
1
(b)
FIG. 1: (a) A simple example of RDG network with resultant
R = 0 and original R = 0.039 (b) The REBG network from
the same original network with θ = 1, and resultant R = 0.4.
(b) 1
1
β=0.6
β=0.8
β=1
Failure rate
0.8
0.6
RDG method
0.4
γ=3
γ=4
γ=5
0.8
Failure rate
(a)
0.2
0.6
RDG method
0.4
0.2
0
0
0
0.2
0.4
α
0.6
0.8
1
(c) 1
α=1
RDG
REBG (θ=0.01)
REBG (θ=0.2)
REBG (θ=1)
0.6
0
0.2
0.4
α
0.6
0.8
1
α=1
RDG
REBG (θ=0.01)
REBG (θ=0.2)
REBG (θ=1)
0.8
0.4
0.2
(d) 1
Failure rate
0.8
Failure rate
we set R = λr2 /λrN , with λr2 to be the second smallest
eigenvalue. It is because λr2 = 0 in cases when incommunicable components emerge, which is not reflected by
λrmin . In the subsequent analysis, we use R to characterize synchronizability.
As the known fact, when there is isolated node or community in an undirected network, the network can never
reach complete synchronization since there is no information flow between the isolated components. Under this
circumstances, the synchronizability index R = λ2 /λN =
0. We call this phenomenon (R = 0) synchronization failure. Generally speaking, synchronization failure is more
likely in directed networks as isolated components are
not necessary. We first denote the cut-vertex as the only
node through which two or more components communicate with each other. In directed networks, the synchronization failure happens whenever cut-vertex have
only incoming links. In this case, there is absolutely no
communication between those components and the cutvertex becomes an information sink. Hence, synchronization cannot be achieved among the incommunicable components.
In order to examine synchronization failure, we first describe briefly the RDG method [20]. The RDG method is
proposed to enhance the synchronizability of undirected
networks by simply assigning the link direction. They
refer links without yet assignment of direction as residual edges, and the number of connected residual edges
as the residual degree of a node. In each step, they select the node with the smallest residual degree and set
a maximum of ⌈hki/2⌉ of its residual edges pointing to
it[24], where hki is the average degree in the original network. Once a node has been selected, it will not be chosen again. Nodes have not yet been selected are called
residual nodes. In addition, there is a directionality α to
control the final fraction of links with direction assignment. When α = 0, all links remain undirected. When
α = 1, all links are assigned direction. The RDG assignments are finished when there is no residual node left in
the network.
The RDG method may lead to directed graph with synchronization failure, i.e., cut-vertex with only incoming
links. A simple example is given in Fig. 1 (a). According
to the rule of RDG, node 1 (k = 2) will be selected first
and the two remaining communities will be left incommunicable. As we have discussed, this RDG network can
never reach complete synchronized state.
According to [20], RDG was supposed to provide a
practical way for the synchronization improvement in
power grid networks, which have exponential degree distribution [25]. So we first study the RDG method in
random exponential networks [26]. Random exponential networks in our context refer to random networks
with exponential degree distribution. We also tested the
RDG method in random scale-free networks since powerlaw degree distributions are widely observed in empirical data [26]. The degree distribution are respectively
given by P (k) ∼ e−βk and P (k) ∼ k −γ . For each β
0.6
0.4
0.2
0
0
0
0.2
0.4
β
0.6
0.8
1
2
2.5
3
3.5
γ
4
4.5
5
FIG. 2: (Color online) The synchronization failure rate as a
function of α by the RDG method in (a) random exponential
networks (P (k) ∼ e−βk , N = 500, kmin = 2, β = 1) and (b)
random scale-free networks (P (k) ∼ k−γ , N = 500, kmin = 2,
γ = 5). Given α = 1, the failure rate as a function of β in (c)
random exponential network and the failure rate as a function
of γ in (d) random scale-free networks when RDG and REBG
(θ = 0.01, θ = 0.2 and θ = 1) methods are used.
and γ, we tested the RDG method on 100 network realizations. To examine synchronization failure, we make
sure that there is no isolated nodes or communities in the
original networks which masks the effect of incommunicable components. We find that many resultant RDG
networks are with R = 0. The failure rate, i.e. the fraction of realization incapable of complete synchronization,
is reported in Fig. 2. As shown in Fig. 2(a) and (b),
when α increase (i.e., more links are assigned direction),
failure rate increases for both exponential and powerlaw networks. These results imply that synchronization
failure is common in both power-grid-like and scale-free
networks, given RDG is used as the method for direction assignment. We further tested the case of α = 1,
which leads to the largest synchronization improvement
as reported in [20]. By varying β and γ, we find that
failure is high when β and γ are large. We also remark
that failure rate decreases with kmin but increases with
3
(a)
1
0.3
0.8
1
0.3
0.8
0.2
(b)
0.2
0.1
0.1
0.6
0.6
θ
θ
0
0
0.4
−0.1
0.4
0.2
−0.2
0.2
−0.1
−0.2
−0.3
0
0
0.2
0.4
β
0.6
0.8
−0.3
0
2
1
2.5
3
3.5
4
γ
4.5
5
FIG. 3: (Color online) The difference D = RREBG − RRDG
in (a) random exponential networks and (b) random scalefree networks with N = 500 and kmin = 2. The results are
obtained by averaging 10 independent realizations.
(a) 1
0.6
θ=0
θ=0.2
θ=1
0.8
Loop rate
Loop rate
(b) 1
θ=0
θ=0.2
θ=1
0.8
0.4
0.6
0.4
0.2
0.2
0
0
0
0.2
0.4
β
0.6
0.8
2
1
2.5
3
3.5
γ
4
4.5
5
FIG. 4: (Color online) The fraction of realizations with directed loop as obtained by the REBG and RDG method in (a)
random exponential networks and (b) random scale-free networks. The results are obtained by average 100 realizations.
The abrupt jumps in random exponential networks come from
the discontinuity in the assignment constraint ⌈hki/2⌉.
N . All these suggest that synchronization failure is not
a rare phenomenon and therefore a new method of direction assignment is required to prevent failure.
We thus introduce the residual edge-betweenness gradient (REBG) method to solve the problem of synchronization failure. Instead of the node degree, we take the
edge-betweenness into account. First of all, we define si
for node i as
si =
N
X
θ
aij lij
,
(1)
j=1
where aij = 1 when there exists an undirected link between i and j and otherwise 0. lij is the betweenness of
the link between i and j evaluated on the original undirected networks, subjected to a power θ with 0 ≤ θ ≤ 1.
To assign link direction, we select the node with the
smallest residual si in each step and assign an incoming direction for a maximum of ⌈hki/2⌉ of its residual
links. As more directed links are assigned, the residual
si has to be updated at every step. If there are multiple
nodes of the smallest si , we choose the node with the
smallest initial si first. The REBG method stops when
there is no residual node left in the network. We remark
that when the parameter θ = 0, si = ki and the REBG
reduces to the RDG method. When θ > 0, the REBG
method contains the global information delivered from
the edge betweenness.
An shown in Fig. 1 (b), the REBG method can effec-
tively avoid the problem of synchronization failure. In
this simple network, whenever node 1 is chosen before
node 3 and 7, synchronization failure occurs. We note
that node 1 is the cut-vertex connecting the two communities, its edges are of high betweenness. To see how
failure is avoided, we evaluate the initial si before any
direction assignment, as given by s1 = 20θ + 20θ , sx =
1θ +1θ +6θ for x = 2, 4, 5, 6, 8, 9 and sy = 6θ +6θ +6θ +20θ
for y = 3, 7. By tracing all the possibilities of subsequent
direction assignment, we find that synchronization failure does not occur provided that node 1 is not selected at
the first assignment. In this case, s1 > sx which implies
θ & 0.18. We denote this value as θc which marks the
value of θ from which failure ceases. We remark that the
value of θc is different for different topology.
We then examine the failure rate in the random exponential networks and the random scale-free networks.
As shown in Fig. 2(c) and (d), failure rate vanishes for
both networks when θ = 0.01, 0.2 and 1. These results
suggest θc ≈ 0, i.e., failure ceases when edge betweenness
is considered in direction assignment. It implies that θ
in Eq. (1) should be positive to make complete synchronized state possible.
Finally, we compare the synchronizability index R between REBG and RDG methods. Both random exponential networks and random scale-free networks are examined. For better illustration, we report the difference
D = RREBG − RRDG as a function of θ and β in Fig.
3(a), and θ and γ in Fig. 3(b). The positive D shows
that the REBG method results in higher synchronizability as compared to the RDG method. This enhancement
is mainly resulted from the prevention of the synchronization failure. One may question the validity of indicating
synchronizability by R with only real part of eigenvalues.
We show in Fig. 4 that for the regime when β and γ is
large, the resultant networks are free of directed loops,
which support the validity of positive D (as obtained by
R) in this regime. These results also explain the negative
D observed with intermediate value of β and γ. From the
lines of θ = 0 and θ = 1, we see that the number of networks with directed loops is higher when θ = 1, which
hinders synchronization and lead to unfavorable results
from REBG. We further show that the REBG method
with θ = 0.2 are similar to the RDG in terms of the
fraction of loopy realizations, suggesting θ = 0.2 is an
effective value for direction assignment, and at the same
time avoids synchronization failure. Hence, one can use
the REBG method with small θ to enhance synchronizability effectively.
We further compare the RDG and the REBG methods
in graphs where failure does not occur. Here, we study
the two methods in Girvan Newman benchmark (GNbenchmark) network which consists of 128 nodes and
is divided into 4 communities [27]. In GN-benchmark,
kinter + kouter = 16, where kinter is the average node degree in each community and kouter is the average node
degree among different communities. We show in Fig. 5
the results of kouter = 1 from which the GN-benchmark
4
1.5
21
r
2
(a) λ
1.4
r
N
(b) λ
20.9
20.8
1.3
20.7
RDG
REBG
20.6
1.2
20.5
1.1
0
0.25
0.5
θ
0.75
1
20.4
0
0.25
0.5
θ
0.75
1
0.08
r
1
r
(c) λ2/λN
(d)
0.8
0.07
0.6
RDG
REBG
0.4
0.06
0.2
0.05
0
0.25
0.5
θ
0.75
1
0
0
25
50
75
100
t
FIG. 5: (Color online) The synchronizability of the REBG
method and the RDG method in GN-benchmark(kouter = 1)
as measured by (a) λr2 , (b) λrN and (c) R = λr2 /λrN as a function of θ. (d) The order parameter r(t) of Kuramoto model
(σ = 10) on the RDG networks and REBG networks(θ = 1).
The results are obtained by averaging 100 independent realizations.
networks are highly clustered. We can see from Fig.
5(a) that the synchronization enhancement comes mainly
from λr2 . Moreover, we tested the Kuramoto model
on the resultant RDG networks and REBG networks.
The oscillator onPnode i of the networks is described
N
by θ˙i = ωi + σ j Aij sin(θj − θi ) in which A is the
[1] A. Arenas, A. Diaz-Guilera, J. Kurths, Y. Moreno, and
C.-S. Zhou, Phys. Rep. 469, 93 (2008).
[2] T. Nishikawa, A. E. Motter, Y.-C. Lai, and F. C. Hoppensteadt, Phys. Rev. Lett., 91, 014101 (2003).
[3] H. Hong, B. J. Kim, M. Y. Choi, and H. Park, Phys. Rev.
E, 69, 067105 (2004).
[4] P. N. McGraw and M. Menzinger, Phys. Rev. E, 72,
015101(R) (2005).
[5] J. Gomez-Gardenes, Y. Moreno, and A. Arenas, Phys.
Rev. Lett., 98, 034101 (2007).
[6] T. Nishikawa, and A. E. Motter, Proc. Natl. Acad. Sci.
U.S.A. 107, 10342 (2010).
[7] C.-S. Zhou, A. E. Motter, and J. Kurths, Phys. Rev.
Lett., 96, 034101 (2006).
[8] A. E. Motter, C.-S. Zhou, and J. Kurths, Phys. Rev. E,
71, 016116 (2005).
[9] M. Chavez, D.-U. Hwang, A. Amann, H. G. E. Hentschel,
and S. Boccaletti, Phys. Rev. Lett., 94, 218701 (2005).
[10] D.-U. Hwang, M. Chavez, A. Amann, and S. Boccaletti,
Phys. Rev. Lett., 94, 138701 (2005).
[11] Y.-F. Lu, M. Zhao, T. Zhou, and B.-H. Wang, Phys. Rev.
E, 76, 057103 (2007).
[12] T. Nishikawa and A. E. Motter, Phys. Rev. E, 73, 065106
(2006).
[13] T. Nishikawa and A. E. Motter, Physica D, 224, 77
(2006).
[14] A. Zeng, Y. Hu, and Z. Di, Europhys. Lett., 87, 48002
(2009).
adjacency matrix and Aij denote the information flow
from j to i, and the collective phase synchronization
can be investigated by the order parameter defined as
PN
r(t) = h|( j=1 eiθj (t) /N )|i. From Fig. 5(d), it is obvious that r(t) of the REBG networks converges faster
than that of the RDG networks. These results show that
the REBG method lead to greater improvement in synchronizability than the RDG method in highly clustered
networks, despite the absence of failure in RDG networks.
In summary, we introduced the residual edge betweenness gradient (REBG) method for direction assignment,
which overcomes the problem of emergence of incommunicable components in the residual degree gradient
(RDG) method. The effectiveness of our method lies in
the use of edge betweenness, which reflects global network information when compared to the node degree in
RDG. Further tests of REBG and RDG in highly clustered networks show that REBG can lead to greater synchronizability improvement in networks despite the absence of failure problem. For daily applications, such
incommunicable components brings huge loss to the electrical systems when power grids are unable to reach complete synchronization. Hence, the REBG method is effective in improving synchronizability which may lead to
wide applications.
This work was supported by NSFC under Grant No.
60974084 and No. 70771011. CHY is partially supported
by the QLectives projects (EU FET-open Grants 213360
and 231200).
[15] T. Zhou, M. Zhao, and C.-S Zhou, New J. Phys., 12,
043030 (2010).
[16] G. Bianconi, N. Gulbahce, and A. E. Motter, Phys. Rev.
Lett. 100, 118701 (2008).
[17] A. Zeng, Y.-Q. Hu, and Z. Di, Phys. Rev. E, 81, 046121
(2010).
[18] G. Zamora-Lopez, V. Zlatic, C.-S. Zhou, H. Stefancic,
and J. Kurths, Phys. Rev. E 77, 016106 (2008).
[19] S. M. Park and B. J. Kim, Phys. Rev. E 74, 026114
(2006).
[20] S.-W. Son, B. J. Kim, H. Hong, and H. Jeong, Phys. Rev.
Lett. 103, 228702 (2009).
[21] M. Barahona and L. M. Pecora, Phys. Rev. Lett., 89,
054101 (2002).
[22] L. M. Pecora and T. L. Carroll, Phys. Rev. Lett., 80,
2109 (1998).
[23] K. S. Fink, G. Johnson, T. Carroll, D. Mar, and L. Pecora, Phys. Rev. E, 61, 5080 (2000).
[24] Different from [20], please note that the edge direction
here is the direction of information flow.
[25] R. Albert, I. Albert, and G. L. Nakarado, Phys. Rev. E
69, 025103(R) (2004).
[26] M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys.
Rev. E 64, 026118 (2001).
[27] M. E. J. Newman and M. Girvan, phys. Rev. E 69,
026113 (2004).