# Synchronizability of Small-World Networks Generated from a Two-Dimensional Kleinberg Model

Authors: Yi Zhao; Jianwen Feng; Jingyi Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper investigates the synchronizability of small-world networks generated from a two-dimensional Kleinberg model, which is more general than NW small-world network. The three parameters of the Kleinberg model, namely, the distance of neighbors, the number of edge-adding, and the edge-adding probability, are analyzed for their impacts on its synchronizability and average path length. It can be deduced that the synchronizability becomes stronger as the edge-adding probability increases, and the increasing edge-adding probability could make the average path length of the Kleinberg small-world network go smaller. Moreover, larger distance among neighbors and more edges to be added could play positive roles in enhancing the synchronizability of the Kleinberg model. The lorentz oscillators are employed to verify the conclusions numerically.


---

## Body

## 1. Introduction

A complex network is a large set of nodes (or vertices) connected by a set of links (or edges) such as coupled biological and chemical system, neural networks, social interacting species, the Internet, and the World Wide Web. Recently, increasing interest has been devoted to the study of collective behaviors in complex networks for its widely applications in real world. Among the studies on the complex network, synchronization phenomena attract the interests of most scientists and engineers. Loosely speaking, synchronization is the process in which two (or more) dynamical systems seek to adjust a certain prescribed property of their motion to a common behavior in the limit as time tends to infinity either by virtue of coupling or by forcing. Synchronization of complex networks is an important mathematical problem in both the physical and biological sciences since it has potential applications to diverse fields such as communications security, seismology, and parallel image processing [1–6].Complex networks could be classified as many types. Among them, synchronization on small-world networks has attracted considerable attention since the pioneering work of Stanley Milgram in the 1960s [7]. A small-world network can be generated by either random edge-rewiring, which gives WS small-world network [8], or random edge-adding, which yields the NW small-world network [9]. The Kleinberg small-world network, in which the edge-adding probabilities are proportional to the length of the edge to be added, could be seen as a more general NW small-world network.Various literatures have already been devoted to the studies on synchronizability of small-world networks. In the research articles [10–13], the synchronizability of a small-world network generated by randomly adding a fraction of long-range shortcuts to a ring network is investigated. It can be deduced from the theoretical analysis and numerical simulation that the synchronizability of the small-world network becomes stronger as the edge-adding probability p grows larger. In [14], Tang et al. found that the synchronizability of the network as a function of the distance is fluctuant and there exist some distances that have almost no impact on the synchronizability when they investigated the impact of edge-adding number and edge-adding distance on both synchronizability and average path length of NW small-world networks generated from ring networks via random edge-adding. Moreover, the relationship between the synchronizability and the average path length of a small-world network is studied in [15–18]. The analysis and numerical simulations show that the synchronizability of the small-world network grows as p increases and the average path length becomes smaller as p goes larger. Therefore, it can be deduced that the decreasing in the average path length may result in the increasing synchronizability. These phenomena are interesting, and a natural question is that whether other small-world networks have similar properties, which motivates us to take a two-dimensional Kleinberg small-world network [19] as an example and investigate the impact factors of such network. It should be mentioned that the synchronizability of an undirected Kleinberg small-world network was investigated in [20]. However, the Kleinberg model is built as a directed network in [19]. Thus, the directions of the edge-adding in building the Kleinberg model are considered in this paper. Moreover, [20] only discussed the relationship between the edge-adding probability and the synchronizability of the small-world network, while in this paper the three parameters of the Kleinberg model, namely, the distance of neighbours, the number of edge-adding, and the edge-adding probability, would be analyzed for their impacts on its synchronizability and average path length. Actually, this paper improves the results in [20].In this paper, we investigate the impacts of the distance of neighbors, the number of edge-adding and the edge-adding probability on the synchronizability of the Kleinberg small-world network. The Kleinberg small-world network is anN×N two-dimensional one. We add  q edges on the nodes with certain probability Π. Then, we could get some conclusions about impact factor on the synchronizability and the average path length of the Kleinberg small-world network, which are complementary to the studies on the synchronizability of the small-world networks.


## 2. Preliminaries

First of all, we build a Kleinberg small-world network in the way introduced in [19]. Figure 1 also comes from [19], and we redraw it in our case to be studied. A Kleinberg small-world network is composed of the set of lattice points in an N×N square, which are denoted as {(i,j):i∈{1,2,…,N},j∈{1,2,…,N}}. The lattice distance between two nodes (i,j) and (k,l) is defined to be the number of “lattice steps,” which could be written as d((i,j),(k,l))=|k-i|+|l-j|. Let  p and q be positive integers. The node u is connected with every other node within lattice distance p, and we name it local contact. We also construct edges from u to q other nodes using independent random trials, which are called the long-range contacts. The probability of edge connected between u and v is proportional to [d(u,v)]-α, where α is a given constant. Precisely speaking, this probability of the connections between u and v is denoted as  Πuv, and
(1)Πuv=[d(u,v)]-α∑v‍[d(u,v)]-α.
Figure 1 shows basic structures of a 10×10 Kleinberg small-world network. In Figure 1(b), there are two long-rang contacts from a node “a” to a node “b” and a node “c”. Actually, two long-range contacts are added to every node in this network if q=2.(a) A two-dimensional Kleinberg network with10×10 nodes, the distance of local contacts p=1, and it has no long-range contacts thus q=0. (b) The contacts of a node “a” with the distance of local contacts p=1 and the number of long-range contacts q=2. “ab” and “ac” are the two long-range contacts.
(a)
(b)Actually, this model could be interpreted in the point of “geography” in [19]. Individuals live on a grid and know their neighbors for some number of steps in all directions; they also have some number of acquaintances distributed more broadly across the grid. If we fixed p and q and let the value of the exponent α vary, we would have a one-parameter family of network models. When α=0, the uniform distribution over long-range contacts could be obtained, which means long-range contacts are chosen independently of their position on the grid. In this sense, the Kleinberg small-world network could be seen as a kind of NW small-world network. As α increases, the long-range contacts of a node become more and more clustered in their vicinity on the grid. Thus, α could be seen as a basic structural parameter measuring how widely “networked” the underlying society of nodes is. Considering that α could reveal some basic properties of the Kleinberg network, in this paper, we investigate the effect of adding-edges probabilities, namely, the effect of the parameter α on the synchronizability of the Kleinberg small-world network. Moreover, two other parameters of the Kleinberg small-world network, namely, the distance of neighbors and the number of edge-adding, are also considered for their influences of synchronizability.Next, the synchronizability analysis of the complex dynamical system follows [21]. The complex dynamical system considered in this paper consists of coupled continuous-time nonlinear oscillators. Since chaotic behaviors are common since the intrinsic nonlinearity exists in each individual oscillator, chaotic synchronization is addressed by choosing the parameters of each oscillator such that it exhibits a chaotic attractor in order to be general. Then, the network of N×N identical dynamics nodes considered in this paper can be written as
(2)xi=F(xi)+c∑j=1N×N‍aijH(xj).
Here, if the node is located at (k,l) in the network, we denote the index i=N(k-1)+l, and thus, i∈{1,2,3,…,N2}. xi∈Rn is the state vector of the ith node in all N×N nodes. c is a positive constant coupling strength. F(·):Rn→Rn is a well-defined nonlinear function and H(·):Rn→Rn is a coupling function. A=(aij)N2×N2 is a coupling matrix determined by the connection topology. That is, aij=1 if the node i and j have connections, and aij=0 otherwise. Moreover, it is required that aii=-∑j=1,j≠iN2‍aij for any i∈1,2,…,N2. Note that A is not necessarily symmetric since our considered network is directed. Moreover, there is only one zero eigenvalue of the matrix A such that the eigenvalues can be sorted as
(3)0=λ1>Reλ2≥Reλ3≥⋯≥ReλN2.
Let ds/dt=F(s), and s(t) is automatically a solution of (2). Then, the synchronous state is defined as x1=x2=⋯=xN2=s. Let ξi=xi(t)-s. For the system described by (2), the variational equations governing the time evolution of the set of infinitesimal vectors about the synchronous solution ξi(t) are
(4)ξi=DF(s)ξi+c∑j=1N2‍aijDH(s)ξj,i=1,2,…,N2,
where DF(s) and DH(s) are the n×n Jacobian matrices of the corresponding vector functions evaluated at s(t), respectively. Let ξ={ξ1,ξ2,…,ξN2}. Then, (4) can be rewritten as
(5)ξ˙=DF(s)ξ+cDH(s)ξA.
By using Jordan transformation with respect to the coupling matrix A, we have
(6)Λ=P-1AP=(0B1⋱Bl),
where P is composed of the eigenvectors of  A. And Bi in (6) are blocks of the form
(7)Bi=(λ1λ⋱⋱1λ),
where λ is one of the eigenvalues of A.Lettingη={η1,η2,…,ηN2}=ξ(P-1)T and employing (6), (5) could also be written as
(8)η˙=DF(s)η+cDH(s)ηΛT.
Then, each block of the Jordan canonical form corresponds to a subject of these columns in  η, which obeys a subset of equations in (8). For instance, if block Bi is  m×m, and suppose the corresponding columns of  η are denoted by  η1,η2,…,ηm, which could be seen as the modes of perturbations in the generalized eigenspace associated with eigenvalue λi, then the equations have the following form
(9)η˙1=[DF(s)+kiDH(s)]η1,η˙2=[DF(s)+kiDH(s)]η2+cDH(s)η1,⋮η˙m=[DF(s)+kiDH(s)]ηm+cDH(s)ηm-1,
where ki=cλi. Each block of the previous decoupled equation (9) is structurally the same with only the factor of  ki being different [21].Definek as a normalized coupling parameter that takes values in the set {k=cλi:i=1,2,…,N2}. Denote L(k) as the largest Lyapunov exponent, which is determined from (9). In order to achieve the synchronization of the network, L(k) is required to be negative. It can be explained that a small disturbance from the synchronization state will diminish exponentially so that the synchronous solution is stable. On the contrary, the synchronous solution is unstable and cannot be realized physically if L(k) is positive because small perturbations from the synchronous state will lead to trajectories that diverge from the state. For the reasons mentioned above, in order to achieve the synchronization of the coupled oscillator network (2), all normalized coupling parameters k=cλi for i=2,…,N2 should fall in a region in which L(k) should be negative. This region is called the synchronized region. In case that the synchronized region is bounded, namely, k~<-Rek<k^, then from (3), we have
(10)k~<-cReλ2≤-cReλ3≤⋯≤-cReλN2<k^.
When the spread in the eigenvalue Reλi goes smaller, it becomes easier that all the numbers -cReλ3 fall into the bounded region k~<k<k^, which means that the synchronizability of the network is better. Thus, we need the ratio of eigenvalue satisfying
(11)R=ReλN2Reλ2<k^k~
to be smaller. In case that the synchronized region is unbounded, then k~<-cReλi<∞  for  i=1,2,…,N2. Thus, the synchronizability of the network is better if the eigenvalue Reλ2 is smaller. Thus, Reλ2 and ReλN2/Reλ2 are used as the measure to evaluate the synchronizability of the network.


## 3. Influencing Factors the Synchronizability of a Network

An extensive numerical analysis is employed to investigate the influences of the distance of neighbors, the number of edge-adding, and the edge-adding probability on the network synchronizability. The Kleinberg small-world networks we considered have10×10 nodes and 15×15 nodes, respectively. Identical dynamics are assumed for all the nodes in the Kleinberg small-world network.Letp=1,2, which means that each node in the Kleinberg small-world network is connected with its nearest neighbors in distance 1 or in distance 2. They form the local contacts. Then, q long-range contacts are added with the probability Π defined in (1). Thus, different q and α would result in different corresponding Laplacian matrix. The eigenvalues of such Laplacian matrix could be calculated. Since the nodes with long-range contacts added are chosen randomly, the Laplacian matrix would be different on each trial. Thus, in the simulation, 100 and 225 different realizations were performed and the results were averaged.Letq=1,2, respectively, for the network with 10×10 nodes and 15×15 nodes. The parameter α in (1) on the probability of adding the long-range contacts is chosen from 0.1 to 10 with step size 0.1. Their corresponding Laplacian eigenvalues Reλ2 and ReλN2/Reλ2 as a function of α are found, which was shown in Figures 2 and 3, respectively.The relationship betweenReλ2 and α for the Kleinberg small-world network with (a) 10×10 nodes and (b) 15×15 nodes.
(a)
(b)The relationship betweenReλN2/Reλ2 and α for the Kleinberg small-world network with (a) 10×10 nodes and (b) 15×15 nodes.
(a)
(b)Figures2 and 3 reveal that the values of Reλ2 and ReλN2/Reλ2 are continuously and monotonically increasing as α increases. It means that the synchronizability of the Kleinberg small-world network becomes stronger as the edge-adding probability increases. Note that when α=0, Kleinberg small-world network could be seen as the NW small-world network. This result corresponds with the observations in references [10–13]. Also, we can see from Figures 2 and 3 that the synchronizability is enhanced as the number of long-range contacts q and the distance of neighbours p increase. It could be explained that the average path length is reduced as more long-range contacts are built and more short-range contacts are constructed. We illustrate this relationship in Figure 4.The average path length as a function ofα with different values of p and q  for the Kleinberg small-world network with (a) 10×10 nodes and (b) 15×15 nodes.
(a)
(b)It is well known that as the distance of the edges added increases, the synchronizability of the network becomes stronger since the average path length is shortened. The probability of edge-adding betweenu and v is proportional to [d(u,v)]-α, which is to say that the shorter distance of the edge-adding has larger probabilities than the longer distance of edge-adding for any given α. Then, it can be concluded that if α is fixed, the synchronizability of the Kleinberg small-world network would be better though the probability of edge adding will become smaller. Figures 2, 3, and 4 show that if q is fixed, in other words, q edges would be added into the network, the synchronizability becomes weaker as we take a larger value of  α. Then, it means that if distance of the edge-adding and the number of edges are fixed, the synchronizability is enhanced as the probability of the edge-adding increases. Meanwhile, in the Kleinberg small-world network, the probabilities of the long-range contacts decrease as the distance between two nodes increases, especially for large α. As α increases, the long-range contacts of a node become more and more clustered in their vicinity on the grid.


## 4. Numerical Simulation for Lorentz Oscillators

The linearly coupled Kleinberg small-world network containing identical Lorentz oscillators is used for numerical simulations. Such oscillators can be written as(12)F(xi)={αs(xi2-xi1),γsxi1-xi1xi3-xi2,xi1xi2-βsxi3,
for i=1,2,…,N2. Here,  αs=10,  βs=8/3, and γs=28. Let
(13)H=[100100000].
In the simulation, we consider a network with N=10 (100 nodes). Define the error term as
(14)E(t)=2N2(N2-1)∑j>i‍∥xi(t)-xj(t)∥2.
If limt→∞E(t)=0, the complex network achieves synchronization. We consider that the synchronizability would be better if E(t) goes to zero faster.For the network (2), let the coupling strength c=70, the distance of local contacts p=1, the number of long-range contacts q=0,1,2, and the parameter α=0.1,5 in the probability of edge-adding (1), respectively. Figure 5 shows how E(t) evolved in network with the same initial values chosen randomly in the interval [-10,10]. It can be seen from Figure 5 that the synchronizability of the network is enhanced as the number of long-range contacts increases, and the synchronizability of the network becomes better as α goes smaller, which means that longer distance of the edge-adding could still enhance the synchronizability though the probabilities of longer distance of the edge-adding are small compared with the probabilities of shorter distance of edge-adding. Moreover, it can be seen that the synchronizability goes better as the number of edges added becomes larger.Figure 5
The errors of synchronization among10×10 different Lorentz dynamics oscillators over time for p=1, q=0,1,2, and α=0.1,5, respectively. The inset is an amplified figure on some time interval.


## 5. Conclusion

The impact factors of synchronizability of two-dimensional Kleinberg small-world network are investigated in this paper. Through mathematical analysis and numerical simulations, we show that the Kleinberg small-world network shares similar properties as NW small-world networks but Kleinberg small-world network is more general. Namely, we see that synchronizability of two-dimensional Kleinberg small-world network is enhanced as the edge-adding probability increases, and the average path length of the Kleinberg small-world network decreases with the increasing edge-adding probability. Moreover, larger distance among neighbors and more edges to be added could play positive roles in enhancing the synchronizability of the Kleinberg model. A network of Lorentz oscillators is taken to make numerical simulations in order to verify the observed phenomena.



---

*Source: 451960-2013-08-28.xml*