شناسایی ساختار مبتنی بر بهینه سازی شبکه های دینامیکی

The topological structure of a dynamical network plays a pivotal part in its properties, dynamics and control. Thus, understanding and modeling the structure of a network will lead to a better knowledge of its evolutionary mechanisms and to a better cottoning on its dynamical and functional behaviors. However, in many practical situations, the topological structure of a dynamical network is usually unknown or uncertain. Thus, exploring the underlying topological structure of a dynamical network is of great value. In recent years, there has been a growing interest in structure identification of dynamical networks. As a result, various methods for identifying the network structure have been proposed. However, in most of the previous work, few of them were discussed in the perspective of optimization. In this paper, an optimization algorithm based on the projected conjugate gradient method is proposed to identify a network structure. It is straightforward and applicable to networks with or without observation noise. Furthermore, the proposed algorithm is applicable to dynamical networks with partially observed component variables for each multidimensional node, as well as small-scale networks with time-varying structures. Numerical experiments are conducted to illustrate the good performance and universality of the new algorithm.

The last decade had witnessed the birth and explosive growth of the field of complex dynamical networks, triggered by the seminal works of Watts and Strogatz [1] on small-world networks in 1998 and of Barabási and Albert [2] on scale-free networks in 1999. Nowadays, dynamical networks have become ubiquitous as models of many real-world systems. Examples range from the Internet, the World Wide Web, power grids [3], transportation networks, social and economic networks [4] to a plethora of examples in systems biology like gene regulatory networks [5], metabolic networks [6] and so on. In the initial phase of the field’s development, the focus was mainly placed upon the study of statistical properties, collective behaviors and control of dynamical networks with predefined topological structures [7], which has provided a tremendous insight into the interplay between the structures and functions. As is known, the topological structure of a dynamical network plays a pivotal role in determining its properties, dynamics and control [8]. Thus, understanding and modeling the structure of a dynamical network will lead to a better knowledge of its evolutionary mechanisms, and to a better control on its dynamical as well as functional behaviors [9]. However, in reality, it is invariably the case that the topological structure of a dynamical network is unknown or uncertain. So it is very important to investigate the underlying topological structure of a network. Indeed, active research during recent years has resulted in various approaches for the identification of network structures. For interacting deterministic systems, some new approaches have been presented for topology identification [10], [11], [12], [13], [14] and [15] based on adaptive control and outer synchronization between two networks [16] and [17]. For simultaneously observed time series, some techniques based on measuring the cross correlation or partial correlation among time series have been proposed. For example, a method based on the dynamical correlation was proposed by Ren et al. [18] to predict the network structure. Granger causality is a widely employed technique based on linear regression for causal link detection, particularly in neuroscience and economics [19]. Many extensions have also been made to generalize the linear Granger causality to the nonlinear case [20]. Inferring directed connections among observed time series using Bayesian networks is also widely used, where the Bayesian models [21] represent probabilistic relationship between multiple interacting entities. Some interesting techniques based on the theory of recurrences [22] have been proposed. In 2007, Romano et al. introduced a method to uncover directional coupling between two interacting systems based on the mean conditional probabilities of recurrence, which is applicable to both weak and strong couplings [23]. Later on, by generalizing partial phase synchronization, Nawrath et al. proposed partial recurrence-based synchronization analysis for inferring the interactions of oscillators with multiple time scales [24]. Very recently, a permutation-based measure named inner composition alignment was introduced to identify relations between subsystems [25]. However, in the synchronization-based methods, the interacting systems and observed data have to be noise free, which usually does not conform to practical cases [10], [11], [12], [13], [14] and [15]. The correlation-based methods are incapable of distinguishing between direct and indirect interactions, which in many situations do not provide very satisfactory results [18]. Those techniques based on Granger causality [19] and [20] or Bayesian networks [21] are usually computationally expensive and require a huge amount of memory and time for computation. The methods based on recurrence properties [23] and [24] can only deal with very small-scale networks, while the performance of the permutation-based method [25] depends on the density of the considered network. Moreover, most of the approaches cannot tell the coupling strength among nodes [18], [19], [20], [21], [23], [24] and [25]. On the other hand, the structure identification problem is a typical parameter identification problem if the configuration matrix is taken as a parameter, and optimization methods are widely used in such parameter identification problems, see Refs. [26], [27] and [28]. Based on the above discussions, in this paper, a technique for inferring the topology of a weighted dynamical network topology is proposed based on optimization. The proposed optimization based algorithm is also robust to observation noise. In particular, the new algorithm works well when only some component variables of each multidimensional node are observable. Interestingly, the method is applicable to small-scale networks with time-varying topological structures as well. The rest of the paper is organized as follows. Theoretical modeling and mathematical analysis of network structure identification based on optimization are presented in Section 2. The detailed algorithm based on the projected conjugate gradient method is given in Section 3. Five illustrative examples are provided in Section 4 for verification and demonstration. Finally, some conclusions and an outlook are summarized in Section 5.

It is of practical importance to identify the topological structure of a dynamical network. By transforming the structure identification problem into an optimization problem through rigorous mathematical analysis, an optimization algorithm based on the nonlinear conjugate gradient method has been proposed to recover the underlying topological structure of a dynamical network from observed nodal data. Five numerical examples have been presented to illustrate the validity and robustness of the new algorithm. Particularly, the algorithm works effectively when there is observation noise or when only some component variables of each multidimensional node are observable. In addition, the proposed algorithm has been further employed on a small-scale time-varying network and good identification results have been rendered. The proposed algorithm is efficient for inferring the topological structures of small- and medium-scale networks. For a large-scale dynamical network, the adopted objective function tends to usually have a large number of local minima in the region of interest. Though the proposed algorithm is still effective to identify topological structures for large-scale networks by finding a global minimizer, it might be very computationally expensive by directly adopting this algorithm. Thus, an interesting topic for future work would be to probe into structure identification of large-scale dynamical networks. Furthermore, our result on a 3-node network with a time-varying structure demonstrates the applicability of the proposed method to small-scale time-varying networks. Therefore, another interesting aspect would be the application of optimization-based technique to identifying structures for medium- or large-scale time-varying dynamical networks, which has been known as a very challenging task. Our analysis and experiments have given some hints on how to do so, however, a more systematic approach is a part of our future work as well.