# Topology Identification of Complex Network via Chaotic Ant Swarm Algorithm

Authors: Haipeng Peng; Lixiang Li; Jürgen Kurths; Shudong Li; Yixian Yang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Nowadays, the topology of complex networks is essential in various fields as engineering,
biology, physics, and other scientific fields. We know in some general cases that there may be
some unknown structure parameters in a complex network. In order to identify those
unknown structure parameters, a topology identification method is proposed based on
a chaotic ant swarm algorithm in this paper. The problem of topology identification is
converted into that of parameter optimization which can be solved by a chaotic ant algorithm.
The proposed method enables us to identify the topology of the synchronization
network effectively. Numerical simulations are also provided to show the effectiveness
and feasibility of the proposed method.


---

## Body

## 1. Introduction

So far, most researches on complex networks are based on their exact structure dynamics. However, there is often various unknown or uncertain information in complex networks of the real world. This information including the topology connection of networks, and dynamical parameters of nodes, is always partially known and also changes continuously in many real complex networks such as gene networks, protein-DNA structure network, power grid networks, and biological neural networks [1–4]. Knowledge about the identification of the topology of complex networks is the prerequisite to analyze, control, and predict their dynamical behaviors. Therefore, this topic has drawn great attention of many researchers, since it is of great theoretical and practical significance to use the dynamics of observed nodes for the identification of the network structure [5–7].The problem of topology identification can be formulated as a gray box model. From this viewpoint, a basic mathematical model of the topology for the complex network can be constructed, although its exact structure peculiarities are not entirely known. In the model of a complex network, there are often some unknown structure parameters which can be completed via topology identification. Therefore, if the basic mathematical model of its topological structure is built, then we only need to identify the unknown structure parameters of this network. Recently, some research on topology identification of complex networks has emerged to identify some complex networks and some time-delay networks [8]. These researchers mainly used an adaptive feedback control algorithm to solve the problem of topological identification. But this algorithm may fail if the network is in a synchronous regime. In [9], an improved adaptive feedback control method was proposed to make it identifiable in synchronous complex networks. However, this improved method should change the coupling mode of its topology. In addition, to adapt this improved adaptive feedback control method, the dynamical parameter of each node must be observable, which is especially difficult to realize in most real networks such as metabolic networks and power grid networks.In this paper, a method of topology identification for complex networks is proposed which is based on a chaotic ant swarm (CAS) algorithm. The problem of topology identification is converted into that of parameter optimization which could be solved by the CAS optimization algorithm [10]. The CAS algorithm was inspired by biological experiments of single ant’s chaotic behavior. This CAS method is different from those of ant colony optimization (ACO), since the CAS algorithm combines chaotic and self-organizing behaviors of ants with the advantages of swarm-based algorithms. The CAS algorithm is a global optimization algorithm, and it can deal with topology identification of complex networks effectively when they are in a nonsynchronous and even when they are in a synchronous regime.The remainder of this paper is organized as follows. In Section2, the problem formulation of topology identification for complex networks is presented. In Section 3, the chaotic ant swarm algorithm is introduced. In Section 4, results of numerical simulations are given. Finally, some conclusions about the proposed method are drawn in Section 5.


## 2. Problem Formulation

To demonstrate the topology identification of complex networks, in this paper, we consider a general complex dynamical network as in [1] with each node being an n-dimensional dynamical system, and it is described by a differential equation of the following form
(1)X˙i=Fi(Xi)+∑j=1N‍cijHXj,i=1,2,…,N,
where N denotes the number of nodes in the dynamical network and Xi=(xi1,xi2,…,xin)∈Rn is the state vector associated with the ith node. The function Fi is the corresponding nonlinear vector field. H is the inner-coupling matrix. C=(cij)N×N is the coupling topology of the network. If there exists a coupling connection between node i and node j(i≠j), cij≠0; otherwise, cij=0. In this paper, C does not need to be symmetric or irreducible.The coupling matrixC fully represents the topological information of the complex network. Consequently, the problem of topology identification for a complex network can be converted into that of identification of the unknown coupling matrix C. To identify the coupling matrix C, here, we assume that H and Fi can be experimentally measured in advance. Next, a drive-response network should be built. Equation (1) is taken as the driving network. Then, the response network can be designed as
(2)η˙i=Fi(ηi)+∑j=1N‍c^ijHηj,
where c^ij is the estimated parameter of cij. ηi is obtained by simulating the network (1) with the estimated coupling matrix element c^ij.To identify the topology of the complex network, the following objective function is introduced as(3)V=∑k=0M‍∑i=1N‍∑d=1D‍(xid(k)-ηid(k))2,
where M is the termination time of numerical simulation, N indicates the number of nodes, D denotes the dimensions of each node’s dynamical system, and k is the discrete time. xij is the state vector of the driving network. ηij is the state vector of the response network with initial value ηij=xij and the estimated coupling matrix element c^ij.Hence, the problem of topology identification is converted into that of a parameter optimization by the search of the minimal value ofV. The topology matrix C can be well identified through the method of objective function.


## 3. Chaotic Ant Swarm Algorithm

In recent years, a swarm intelligent optimization algorithm called chaotic ant swam (CAS) algorithm is proposed to solve the optimization problem based on chaos theory [10]. The mathematical model of CAS algorithm is described as follows:
(4)yi(t)=yi(t-1)(1+ri),zid(t)=Δexp((1-exp(-ayi(t)))(3-ΨdΔ))-7.5Ψd×Vi+exp(-2ayi(t)+b)×(pbestd(t-1)-zid(t-1)),
where yi(t) is the organization variable of the CAS model and Δ=zid(t-1)+7.5/(Ψd×ϕi). It controls the chaotic behavior of an individual ant. In this paper, yi(0)=0.999. ri is the organization parameter of individual ant which is a positive constant less than 1. a is a very large positive constant; here, a is set to be 200. b is a positive constant, where 0≤b≤2/3. Ψi determines the searching range of the ith ant in dth dimension. ϕi controls the moving proportion of the ith ant searching space. pbest(t-1) is the best position that the individual ant and its neighbors have ever found within t-1 time steps. Here the neighbors are set to be global neighbors; that is, all the ants are the neighbors of each other.The ants usually exchange information via certain direct or indirect communication methods. As a result of effective communication, the impact of the organization becomes stronger as time evolves. Finally, all the ants walk through the best path to forage food. Equation (4) shows the foraging process of CAS model. As time increases, the effect of the organization variable yi(t) on the behavior of each ant is becoming stronger via the organization parameter ri. Finally, by the effect of both pbestd(t-1) and yi(t), the state of zid(t) will converge to the best global position.r
i and Ψd are two important parameters. ri has an effect on the converging speed of the CAS algorithm. If ri is very large, then the converging speed of the CAS algorithm will be very fast so that the optimal solution might not be found. If ri is very small, then the converging speed of the CAS algorithm will be very slow and the runtime will be longer. If ri is set to be zero, then the behavior of one ant will be chaotic all the time and the CAS algorithm cannot converge to a fixed position. Furthermore, since small changes of organization effect are desired, ri is set to be 0≤ri≤0.5. The concrete formula of ri depends on the specific problem as well as runtime. In order to enable each ant to have a different organization parameter, we set ri=0.1+0.2×rand, where rand is a uniformly distributed random number in the interval [0,1]. Ψd has an effect on the searching range of the CAS algorithm. If the value of Ψd is very large, then the searching range will be small. If Ψd is very small, then the searching range will be very large. The searching range is set to be [-wd/2,wd/2], and then wd≈7.5/Ψd.Based on the above discussions about the CAS algorithm, the detailed procedure for identifying the topology structure of a complex network is described as follows.Step 1.
To identify the topology parameter of a complex network, some important parameters of the CAS algorithm should be firstly initialized. In this paper, the positive constanta is set to be 200; the organization factor ri of each node is set as ri=0.1+0.2×rand, where i is the ith ant in the whole Q ants; ϕi is set properly to control the moving proportion. The organization variable of each node yi is set to be 0.999. Ψd is set properly to control the searching range of zid, where d is the dth dimension of the ant local position.Step 2.
Generate the initial position of theith ant zi(k=0)=(zi1,zi2,…,zid)T randomly in the searching space. k=0 denotes the initial time point.Step 3.
By setting the initial time state vectorxi(0)=(xi1,xi2,…,xin), the fourth-order Runge-Kutta algorithm is used in the driving network (1) to obtain a series of xi(k).Step 4.
By setting the initial time state vectorηi(0)=xi(0), i=1,2,…,N, the well-known fourth-order Runge-Kutta algorithm is used in the response network (2) to obtain a series of ηi(k), i=1,2,…,N. The coupling matrix C can be estimated by the ant colony zi(t),i=1,2,…,Q.Step 5.
Computeyi for each ant. Then, update the position of each ant via (4).Step 6.
Compute the value of objective function for each antzi, and compare each value with previous fpbest of each ant. If the current value is smaller than the previous fpbest, then it is updated by the current value, and set the value of pbest to be the current individual location. Finally, compare each fpbest with fgbest. If the value of fpbest is smaller than fgbest, then fgbest is updated by fpbest of this ant. Then, the pgbest=(pgbest1,pgbest2,…,pgbestd) is replaced by the current global best position.Step 7.
Go to Step5 until the ending condition is satisfied. Then output the global best location of each ant, which means the coupling matrix C can be identified by the CAS algorithm.


## 4. Numerical Simulation

In this section, we present several numerical simulation results to illustrate the effectiveness of the proposed method. Lorenz chaotic equation is taken as the node dynamical system of theith node, which is described as
(5)x˙1=θ1(x2-x1),x˙2=(θ2-x3)x1-x2,x˙3=x1x2-θ3x3,
where x1, x2, and x3 are the state variables; θ1=10, θ2=28, θ3=8/3 are positive constants. For the CAS algorithm model (4), we set a=200, b=2/3, and ϕi=0. To calculate the objective function V, M=20 successive vectors are set in both driving and response networks. In order to show the effectiveness and feasibility of the proposed method, two examples are provided as follows to identify the topology structure of complex networks.Note. There is an interesting phenomenon. Let φ be the golden ratio, which is approximately equal 1.618. Then, b approximately equals 1/φ, and θ3 approximately equals to φ2. Why such an interesting phenomenon exist? We should give further study in our future work. The basic concept of the golden ratio is given in [11–13] and [14] for the spectra used in [11, 12].Example 1.
First of all, a nonsymmetric and non-synchronous diffusive network is considered, which includes three nodes with the topology matrixC. The elements of the topology matrix C are c1,2=4, c2,1=5, c2,3=3, and c3,2=2. The other elements are ci,j=0(i≠j) and ci,i=-∑‍ci,j. H is an identical matrix I3. Here, the initial state is set to be X(0)=[-6,3,7;-14,3,-4;5,-3,4]. The population size is 40. The maximum time step is set as 200. Obviously, there are 6 independent variables, so the dimension of each ant position is set to be 6. We set Ψ1=Ψ3=1.25, Ψ2=1, Ψ4=1.85, and Ψ5=Ψ6=10. ηid is in the interval [0,7.5]. The estimated process is shown as follows.Figure1 shows that the coupling matrix C can be well identified as the time increases. When the time step is approximately 200, the estimated coupling matrix converges to the true value where the population size is 40. To compare the CAS algorithm with the QPSO algorithm, we also use the definition of [15] to identify the topology of Example 1. Then, the evolution curve of the objective function against the time can be obtained, and their comparative result between these two algorithms is shown in Figure 2. We can see that the objective function V converges rapidly to the global optima as time evolves. Besides, the converging speed and the precision of the CAS algorithm are much better than those of the QPSO algorithm.Figure 1
(Color online) Estimation of nonsynchronous network topology showing the valuec^(t) against time step t.Figure 2
Estimation of nonsynchronous network topology showing the objective function valueV against time step t.Example 2.
In this example, a symmetric synchronous network is introduced to show the effectiveness of the proposed method. The parameters of the topology structure are set asc1,2=c2,1=3, c1,3=c3,1=6, c1,4=c4,1=2, c2,3=c3,2=4, c3,4=c4,3=5, and the other ci,j=0(i≠j) and ci,i=-∑‍ci,j. H is an identical matrix I3. Here, the initial state is X(0)=[-6,3,7;-14,3,-4;-3,4,5;-5,6,1]. The population size is 30. The maximal time step is set as 300. Obviously, there are 6 independent variables, so the dimension of each ant position is set to be 6. Ψ1 is set to be 1.875. Ψ2 is set to be 0.75. Ψ3 is set to be 1.875. Ψ4 is set to be 1.25. Ψ5 is set to be 0.9375, and Ψ6 is set to be 10. Figure 3 shows the identification results.Figure 3
(Color online) Estimation of a synchronous network topology showing the valuec^(t) against time step t.We can see that the topology matrixC can be identified precisely as the time increases. To compare CAS algorithm with QPSO algorithm, we use the definition of [15] to identify the topology of Example 2. The comparative result is shown in Figure 4. From Figure 4 and Table 1, we can see that although the converging speed of QPSO algorithm is a little faster than that of CAS algorithm, the converging precision of QPSO is much less than that of CAS algorithm. Obviously, the CAS-based topology identification method is more effective than the QPSO-based topology identification method. Compared with the adaptive synchronization identification approach, the CAS algorithm does not need to change the coupling modes of the network topology, which has advantages in some real identification cases, for example, the biological neural network.Table 1
Comparison between two algorithms.
Algorithms
Objective value
CAS
0.317
QPSO
2.082Figure 4
Estimation of nonsynchronous network topology showing the objective function valueV against time step t.


## 5. Conclusion

In this paper, a topology identification method is proposed based on the CAS algorithm. The problem of topology identification is converted into that of parameter optimization. Compared with the constraints of identifying synchronous complex networks via adaptive feedback control method and the relatively poorer converging precision via QPSO-based topology identification method, the proposed method based on CAS algorithm can identify the topology structure of complex network effectively.



---

*Source: 401983-2013-10-24.xml*