Topology Identification of Coupling Map Lattice under Sparsity Condition

Abstract

Coupling map lattice is an efficient mathematical model for studying complex systems. This paper studies the topology identification of coupled map lattice (CML) under the sparsity condition. We convert the identification problem into the problem of solving the underdetermined linear equations. The [subscript]l1[/subscript] norm method is used to solve the underdetermined equations. The requirement of data characters and sampling times are discussed in detail. We find that the high entropy and small coupling coefficient data are suitable for the identification. When the measurement time is more than 2.86 times sparsity, the accuracy of identification can reach an acceptable level. And when the measurement time reaches 4 times sparsity, we can receive a fairly good accuracy.

Jiangni Yu 1, 2 and Lixiang Li 1, 2 and Yixian Yang 1, 2

Academic Editor:Florin Pop

1, Information Security Center, State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
2, National Engineering Laboratory for Disaster Backup and Recovery, Beijing University of Posts and Telecommunications, Beijing 100876, China

Received 30 July 2014; Accepted 20 September 2014; 5 July 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

The coupled map lattice with nonlocally coupling chaotic characteristic is widely observed and highly involved in many fields, which ranges from complex network [1-3] to neural network, from biological system to ecological system, and from physics to computer science [4-6]. Driven by some practical applications which benefit from the better controlling of CML, a great deal of current research of CML has focused on dynamical analysis, control, and modeling. However, the behavior of CML is largely influenced by the topology of the network which generally is invisible to us. Thus, its identification usually becomes the promise of application.

Up to now, various researches focus on identifying the patterns of coupled map lattice models [7, 8], such as the study of the formation and evolution of spatiotemporal patterns based on a reference model [7], and the identification of CML based on the wavelet [8]. However, few researches have discussed the topology identification of CML. There are two problems of topology identification: how we should get the result with less measurement time ( [figure omitted; refer to PDF] ) and what precondition the measured data need.

In this paper, as CML is discrete, for the facilitation of identification, we transform the CML equation so that the identification problem can be converted into a problem of solving the linear equation [figure omitted; refer to PDF] . The [figure omitted; refer to PDF] method is introduced to solve the topology identification of CML. In the process of identification, the relationship between the measurement time ( [figure omitted; refer to PDF] ) and the sparsity ( [figure omitted; refer to PDF] ) of [figure omitted; refer to PDF] is taken into consideration. In the experiment, through the analysis of entropy, we discuss the coupling coefficient and the solvability of the equation [figure omitted; refer to PDF] . We find that smaller coupling coefficient benefits the identification. Through further research, we study the influence of the measurement time on the identification precision; that is, when the measurement time [figure omitted; refer to PDF] , we can achieve a decent identification result, and when [figure omitted; refer to PDF] , the identification result is very good.

2. Analysis of Identification Process

Considering a CML with [figure omitted; refer to PDF] elements is as follows: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is the state of each node, [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] is the discrete time step. [figure omitted; refer to PDF] is the strength of the coupling. [figure omitted; refer to PDF] is the standard form of logistic nonlinear function. Also [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] . [figure omitted; refer to PDF] is the weighted topology connection from element [figure omitted; refer to PDF] to its neighbor elements [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , and the weighted topology connection obeys the periodic boundary condition. The schematic diagram is shown as in Figure 1.

Figure 1: Periodic boundary condition of element [figure omitted; refer to PDF] when neighbors [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

Normally, the weighted topology connections are composed by the known part [figure omitted; refer to PDF] and the unknown part [figure omitted; refer to PDF] . Our purpose is to identify this unknown part. In order to identify these unknown connections, the dynamical equation (1) can be transformed as the following equation: [figure omitted; refer to PDF]

Now, we expand the matrix [figure omitted; refer to PDF] to [figure omitted; refer to PDF] . In the expanded matrix [figure omitted; refer to PDF] , if [figure omitted; refer to PDF] , [figure omitted; refer to PDF] ; if [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . Under these circumstances, (2) can be expressed as [figure omitted; refer to PDF]

We set [figure omitted; refer to PDF] . If we put [figure omitted; refer to PDF] iterations together, then we get [figure omitted; refer to PDF] measurements. Its formula can be expressed as [figure omitted; refer to PDF]

Here, [figure omitted; refer to PDF] can be divided into two parts, that is, the known part [figure omitted; refer to PDF] and unknown part [figure omitted; refer to PDF] , which is [figure omitted; refer to PDF] . Thus, to get the solution [figure omitted; refer to PDF] , we have [figure omitted; refer to PDF] To simplify, the above equation set can be represented as [figure omitted; refer to PDF] where [figure omitted; refer to PDF] implies the left side of (5) and [figure omitted; refer to PDF] implies the left matrix of the right side.

Obviously, the elements in [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are decided by [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and the sampled value [figure omitted; refer to PDF] . The size of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are decided by [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . Thus, (6) can be expressed as [figure omitted; refer to PDF] where [figure omitted; refer to PDF] and [figure omitted; refer to PDF] are the columns of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] , respectively. Without loss of generality, we use [figure omitted; refer to PDF] instead of [figure omitted; refer to PDF] and use [figure omitted; refer to PDF] instead of [figure omitted; refer to PDF] . The equation set finally can be described as [figure omitted; refer to PDF]

Eventually, we transform the topology identification problem into a problem of solving the equation set. The vectors [figure omitted; refer to PDF] and [figure omitted; refer to PDF] can be computed by the sampled value [figure omitted; refer to PDF] (which is the state value of each element in the [figure omitted; refer to PDF] th iteration). The character of solutions [figure omitted; refer to PDF] depends on the matrix [figure omitted; refer to PDF] . When there are at most [figure omitted; refer to PDF] unknown connections of each element, which means the nonzero value of [figure omitted; refer to PDF] will be less than [figure omitted; refer to PDF] , in this case we defined [figure omitted; refer to PDF] as [figure omitted; refer to PDF] -sparse. In the following section, the influences of [figure omitted; refer to PDF] and [figure omitted; refer to PDF] will be taken into consideration in the identification problem.

3. The Analysis of [figure omitted; refer to PDF] and [figure omitted; refer to PDF]

Normally, when [figure omitted; refer to PDF] is full rank, which means [figure omitted; refer to PDF] is reversible, (5) has a unique solution, which implies that the measurement time [figure omitted; refer to PDF] should be larger than the element [figure omitted; refer to PDF] . However, when [figure omitted; refer to PDF] is smaller than [figure omitted; refer to PDF] , the identification of the unknown connections is an interesting problem. On account of the partial unknown connection, namely, [figure omitted; refer to PDF] is [figure omitted; refer to PDF] -sparse, the solution can be worked out by an underdetermined equation [figure omitted; refer to PDF] when [figure omitted; refer to PDF] . The solving of [figure omitted; refer to PDF] is related to two aspects: the construction of [figure omitted; refer to PDF] and the method to work out the solution [figure omitted; refer to PDF] .

3.1. The Solving Condition for [figure omitted; refer to PDF]

According to [9], the necessary and sufficient condition for the solution of the underdetermined problem is that, for any vector [figure omitted; refer to PDF] sharing the same sparsity [figure omitted; refer to PDF] , there exists a [figure omitted; refer to PDF] such that [figure omitted; refer to PDF] where [figure omitted; refer to PDF] implies that the columns of [figure omitted; refer to PDF] should be linearly independent. The property is generally satisfying the law of random matrix such as i.i.d Gauss and Bernoulli. Recently, owning to the pseudorandom property of chaotic system, the chaos sequence is used for the construction of [figure omitted; refer to PDF] . It was proved in [10] that when the sampling distance guarantees a certain value, the logistic system satisfies the RIP condition. In [11], a series of chaos systems, such as Lorenz system and Chuan's circuit, are used to produce [figure omitted; refer to PDF] . Thus, in the model of this paper, it was promising to identify the unknown connections.

3.2. The Solving Process of [figure omitted; refer to PDF]

As illustrated above, the unknown vector is [figure omitted; refer to PDF] -sparse; then the resolution problem can be transformed into an optimization problem which is to find the most sparse solution of (8). Thus the [figure omitted; refer to PDF] norm optimization is taken into consideration. However, to find a [figure omitted; refer to PDF] to satisfy [figure omitted; refer to PDF] is a NP hard problem that requires an exhaustive enumeration of all [figure omitted; refer to PDF] possible combinations for the locations of the nonzero entries in [figure omitted; refer to PDF] . Then the application of [figure omitted; refer to PDF] norm optimization is tried, which is to find a [figure omitted; refer to PDF] to satisfy [figure omitted; refer to PDF] . It is also denied for the lack of precision. After that, [figure omitted; refer to PDF] norm is considered; it is more efficient than [figure omitted; refer to PDF] and more precise than [figure omitted; refer to PDF] . The optimization method is expressed as follows: [figure omitted; refer to PDF]

The [figure omitted; refer to PDF] optimization problem can be transformed to a linear programming known as basis pursuit (BP). As [12] illustrated, the matrix [figure omitted; refer to PDF] can be shown to have the RIP, when the measurement time satisfies the condition as follows: [figure omitted; refer to PDF] where [figure omitted; refer to PDF] is a constant; we can exactly reconstruct [figure omitted; refer to PDF] -sparse vector [figure omitted; refer to PDF] via the BP method. Plenty of experimental results show that most of [figure omitted; refer to PDF] -sparse signals can be worked out when [figure omitted; refer to PDF] [13]. In this paper, we will discuss the relation between [figure omitted; refer to PDF] and [figure omitted; refer to PDF] in this identification circumstance by experimental analyses.

4. Experiments and Discussions

In the simulation, we set [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . The chaotic state trajectory of (1) by 100 iterations is shown in Figure 2.

Figure 2: The state trajectory of CML.

[figure omitted; refer to PDF]

The character of random likeness and boundedness of chaotic system can be observed from Figure 2, and for a better perceptual intuition the state of the 50th element is shown in Figure 3.

Figure 3: The state trajectory of the 50th element of CML.

[figure omitted; refer to PDF]

4.1. The Influence of [figure omitted; refer to PDF] on the Identification

The chaotic behavior is obvious when [figure omitted; refer to PDF] is low, while the system may exist in many states, such as chaos, periodicity, and synchronization. To observe the changing of the network state, we use the information entropy to describe the state as illustrated in [14], by which higher value of entropy implies better chaos character of each node and vice versa. The state of CML is influenced by the parameters [figure omitted; refer to PDF] and [figure omitted; refer to PDF] . With the changing of these factors, the information entropy is shown as Figure 4.

Figure 4: The diagram of entropy influenced by [figure omitted; refer to PDF] and [figure omitted; refer to PDF] .

[figure omitted; refer to PDF]

Figure 4 shows the entropy with different [figure omitted; refer to PDF] and [figure omitted; refer to PDF] ; it is obvious that the value of [figure omitted; refer to PDF] is the main influence factor to the entropy.

(i) When [figure omitted; refer to PDF] , the degree of coupling is low. It shows a high value of entropy, which means the high randomness of the network. CML system is under a nonsynchronous state, and the sampled sequence benefits the identification.

(ii) When [figure omitted; refer to PDF] , it shows a low value of entropy, and the CML system is under a complex state between the nonsynchronous state and the synchronous one. Some behavior such as periodicity, which indicates the randomness is weaker, may lead to a low entropy of the sequence. Thus, it is not the favorable condition for identification.

(iii): When [figure omitted; refer to PDF] , it arrives at a high value of entropy as chaos because of the synchronization of CML. Considering the synchronization of elements, the correlation between the columns of [figure omitted; refer to PDF] is high and does not conform to the RIP condition. Therefore, despite the high entropy, it is not suitable for identification.

Thus, for the requirement of identification, smaller [figure omitted; refer to PDF] is better for the identification.

4.2. Identification Result of Unknown Connections

Here we set [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , [figure omitted; refer to PDF] . Figure 5 shows the connections of an element to the others achieve a successful identification with accuracy [figure omitted; refer to PDF] .

Figure 5: The identification result of unknown connections of the 50th element.

[figure omitted; refer to PDF]

The optimization process is shown in Figure 6.

Figure 6: The optimization result of each iteration.

(a) [figure omitted; refer to PDF]

(b) [figure omitted; refer to PDF]

From Figure 6, the estimated value [figure omitted; refer to PDF] converges to the stable state, and the result is correct when [figure omitted; refer to PDF] is closed to zero. The experiment is implemented in Matlab 2013 on Windows 8 Service Pack 1 64-bit operation system. We use a desktop which has a 4-core Intel(R) Core (TM) i3-2120 processor running at 3.30 GHz and 2 GB of RAM. It can be observed that with 4 iterations the result can be almost accurate, and it only takes 0.073322 seconds in our experimental simulation.

According to the above experiments, the identification process works perfectly when [figure omitted; refer to PDF] . But does the algorithm work besides this value? As illustrated in Figure 4, higher coupling coefficient leads to a low entropy or a synchronized state as b and c. The algorithm works well when [figure omitted; refer to PDF] ; thus the premise for completing the identification progress smoothly depends on the coupling coefficient of the network. The result just corresponds with the conclusion that smaller [figure omitted; refer to PDF] benefits the identification.

4.3. The Influence of Measurement Time and Sparsity

As we discussed above, to solve the underdetermined equation, the measurement time and the solution sparsity should fulfill a certain condition. For a more detailed understanding of these correlations, the three-dimensional diagram was drawn and is shown in Figure 7.

Figure 7: The correlations among the measurement time, sparsity, and the identification accuracy.

[figure omitted; refer to PDF]

From Figure 7 we discover that with smaller measurement time and bigger sparsity the solution turns bad and vice versa. To be more detailed, we showed the aerial view in Figure 8.

Figure 8: The aerial view of Figure 7, which is divided into 4 areas.

[figure omitted; refer to PDF]

For Figure 8, we can divide the areas into four parts a, b, c, and d by the distribution of solution effect. The red line [figure omitted; refer to PDF] means the ratio [figure omitted; refer to PDF] and the green line [figure omitted; refer to PDF] means the ratio [figure omitted; refer to PDF] .

(i) For area a, when [figure omitted; refer to PDF] , it does not meet the solution conditions.

(ii) For area b, when [figure omitted; refer to PDF] , [figure omitted; refer to PDF] almost cannot be calculated by [figure omitted; refer to PDF] accurately.

(iii): For area c, when [figure omitted; refer to PDF] , [figure omitted; refer to PDF] can be calculated out with acceptable accuracy.

(iv) For area d, when [figure omitted; refer to PDF] , [figure omitted; refer to PDF] can be calculated out exactly.

The area d corresponds with the traditional condition [figure omitted; refer to PDF] discussed above. However, from the experiment we learn that the area c is regarded as the acceptable one. Such result may have a guiding significance in the identification process.

5. Conclusion and Future Work

In this paper, we propose a new approach for the identification of CML. We work out the unknown connections vector through the [figure omitted; refer to PDF] method. The requirement of sampling time and data characters are discussed in detail in this paper, and the identification result meets the precision of the experiment. Moreover, also some possibility of further researches exists.

On one side, assuming there is an undirected network, besides all the values of the nodes' state, we only know the total sparsity of all the connections (some nodes may have sparse connections, while some nodes' connections may be not sparse); how can we get the correct identification result? This problem may be solved by the following steps. Firstly, we should find the connections between two nodes with sparse unknown connections and estimate them. Secondly, owning to the symmetry characteristic of undirected network, with more and more unknown connections being identified, some of the connections of nodes which were not sparse become sparse; thus we should find these nodes and estimate the connections. Thirdly, continue the second step until we know that remaining nodes' connections cannot be estimated.

On the other side, comparing with traditional method of topology identification, [figure omitted; refer to PDF] method can finish the process of identification with lesser sampling time, but it requires knowing the whole states of the network. Its applications may be limited in the network which are able to know all the states of the nodes. Thus, in the future work, the topology identification with the deficiency of a part of nodes' state value may be discussed.

Acknowledgments

This paper is supported by the National Natural Science Foundation of China (Grant nos. 61170269, 61121061), the Beijing Higher Education Young Elite Teacher Project (Grant no. YETP0449), the Asia Foresight Program under NSFC Grant (Grant no. 61161140320), and the Beijing Natural Science Foundation (Grant no. 4142016).

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] D. Zhao, L. Li, H. Peng, Q. Luo, Y. Yang, "Multiple routes transmitted epidemics on multiplex networks," Physics Letters. A , vol. 378, no. 10, pp. 770-776, 2014.

[2] D. Zhao, L. Li, S. Li, Y. Huo, Y. Yang, "Identifying influential spreaders in interconnected networks," Physica Scripta , vol. 89, no. 1, 2014.

[3] S. Li, Z. Jia, A. Li, L. Li, X. Liu, Y. Yang, "Cascading dynamics of heterogenous scale-free networks with recovery mechanism," Abstract and Applied Analysis , vol. 2013, 2013.

[4] M. C. Cross, P. C. Hohenberg, "Pattern formation outside of equilibrium," Reviews of Modern Physics , vol. 65, no. 3, pp. 851-1112, 1993.

[5] V. Booth, T. Erneux, "Understanding propagation failure as a slow capture near a limit point," SIAM Journal on Applied Mathematics , vol. 55, no. 5, pp. 1372-1389, 1995.

[6] R. V. Sole, J. Valls, J. Bascompte, "Spiral waves, chaos and multiple attractors in lattice models of interacting populations," Physics Letters A , vol. 166, no. 2, pp. 123-128, 1992.

[7] D. Coca, S. A. Billings, "Identification of coupled map lattice models of complex spatio-temporal patterns," Physics Letters. A , vol. 287, no. 1-2, pp. 65-73, 2001.

[8] S. A. Billings, L. Z. Guo, H. L. Wei, "Identification of coupled map lattice models for spatio-temporal patterns using wavelets," International Journal of Systems Science , vol. 37, no. 14, pp. 1021-1038, 2006.

[9] D. L. Donoho, "Compressed sensing," IEEE Transactions on Information Theory , vol. 52, no. 4, pp. 1289-1306, 2006.

[10] L. Yu, J. P. Barbot, G. Zheng, H. Sun, "Compressive sensing with chaotic sequence," IEEE Signal Processing Letters , vol. 17, no. 8, pp. 731-734, 2010.

[11] V. Kafedziski, T. Stojanovski, "Compressive sampling with chaotic dynamical systems," in Proceedings of the 19th Telecommunications Forum (TELFOR '11), pp. 695-698, November 2011.

[12] R. G. Baraniuk, "Compressive sensing," IEEE Signal Processing Magazine , vol. 24, no. 4, pp. 118-124, 2007.

[13] E. J. Candes, T. Tao, "Decoding by linear programming," IEEE Transactions on Information Theory , vol. 51, no. 12, pp. 4203-4215, 2005.

[14] A. M. Hagerstrom, T. E. Murphy, R. Roy, P. Hövel, I. Omelchenko, E. Schöll, "Experimental observation of chimeras in coupled-map lattices," Nature Physics , vol. 8, no. 9, pp. 658-661, 2012.