Identifying structures of continuously-varying weighted networks

Time-varying networks describe a large number of systems whose constituents and interactions evolve over time1,2,3. This subject has attracted extensive attention from researchers in various fields. For instance, Starnini et al. proposed several immunization strategies for epidemic processes in time-varying networks2, Amritkar et al. studied the synchronization properties of coupled dynamics on time-varying networks and the corresponding time-average network4, and Nicola et al. explored the random walk process in a fairly general class of time-varying networks5. Indeed, complex systems taking the form of time-varying networks are ubiquitous. Some plausible representations of the relational information among entities in dynamical systems are time-varying networks that are topologically rewiring and semantically evolving over time6,7,8, such as a social community, living cells, e-mail messages, mobile telephone calls, functional brain networks, food webs and other networks of species. It is noteworthy that topological structures of complex networks play an important role in determining their evolutionary dynamics and functional behaviors, and may have significant consequences for many real-world applications9. However, in many practical situations, the precise structure of a complex dynamical network is unknown or uncertain. Therefore, to find a general solution to the structure identification problem of complex networks is of primary importance. Many achievements have been made on structure identification of complex networks10,11,12,13,14,15,16. For example, Zhang et al. constructed an auxiliary complex network in a very general form and designed some adaptive controllers to identify network structures based upon generalized outer synchronization10, Wu et al. used Granger causality test to infer network structures11,12, Wang et al. estimated network parameters based on compressive sensing13,14, Kolar et al. presented two new machine learning methods for estimating time-varying networks based on a temporally smoothed l1-regularized logistic regression formalism15, and Rao et al. used a state-space model to infer time-varying network topologies from gene expression data16. However, most if not all of these studies focus on the case that network structures are static, and those works regarding estimating time-varying structures of networks only care about topological changes in the structures, not about continuous changes of coupling weights. Yet, networks are not only specified by their structures but also by the dynamics of information taking place on the structure17. Examples include a social network where there exists stronger or weaker social ties between individuals, a metabolic network where there are more or less flux along particular reaction pathways, a food web where there are varying energy or carbon flow between predator-prey pairs18, among many others. Thus it is practical to assign varying weights for each edge of a complex network without changing the structure17. In this paper, we propose a method to identify structures of networks whose edge weights continuously vary with time. In many situations, the interactions among elements of a large system are rapidly changing and are usually characterized by processes whose timing and duration are defined on a very short temporal scale3. Since interactive weights among elements in a real-world network sometimes are varying continuously with time, the assumption of static structures or activity-driven varying structures is sometimes inappropriate. Continuously-varying structures should thus be taken into account for analysis of this kind of realistic complex networks. Furthermore, due to the fact that the structure of a real-world network normally is sparse and there is only a limited number of observations, we propose an optimization framework to identify the continuously-varying weights of a complex network. In designing the algorithm, a regularization technique is incorporated, which led to an efficient and robust scheme as finally verified by accurate or noisy data sets observed from a 6-node directed chaotic network, a 50-node undirected network, as well as a 50000-node small-world network.