Network Structure Identification using Corrupt Data-Streams

Abstract

Many complex systems lend themselves to effective modeling described by a network of dynamically interacting agents. Such modeling is prevalent in many application domains that include climate science, neuroscience, internet-of-things, power grids, and econometrics. The evolution of these systems is governed by the interdependencies and interactions between the agents that can contain feedback loops. Identification of the presence or absence of influence pathways among the agents is of primary importance that enables subsequent analytics in networked systems such as identifying central agents and clusters, devising control strategies in distributed systems, and resource allocation. In most application domains, the nature of the relationships and interdependencies cannot be easily modeled using first principles. Furthermore, in many such systems, it is not possible to deliberately affect the system, and thus passive or noninvasive methods are required. The existing methods of network identification do not account for the common ways through which data gets corrupted. In real-world systems, sensor readings can be inaccurate, clocks can get out of sync, and messages can get lost in transmission over a wireless network. The focus of this research is to incorporate realistic modeling assumptions on data streams and characterize the effects of data corruption on network identification using passive means. We show that identifying the structure of networked systems using corrupt measurements results in the inference of spurious links. The effects of data corruption on network reconstruction are characterized with provable guarantees on the quality of construction with respect to the generative models considered. A wide range of generative models that underlie the data streams are considered that include static interactions (Markov random fields), linear time-invariant dynamical systems, and nonlinear dynamical models. We examine both causal and non-causal inference methods. In both cases, we provide an exact characterization of the location of spurious links. Our results show that the spurious links are localized to the neighborhood of the corrupted node. All our solution methodologies utilize only the time-series observations without any knowledge of the system parameters. Our precise characterization of the erroneous links is further exploited when the network has special structural properties. There are several physical systems, especially flow-driven systems like power grids, heat transfer networks, and fluid flow networks, where every dynamic coupling between the agents/nodes is bi-directional. In such systems, identifying unidirectional links in reconstruction lead to the conclusion that such links arise from data corruption. We utilize our precise characterization of spurious links to detect and localize all corrupt nodes in the network. It is imperative that learning the exact network representation of such systems without spurious links is needed for performing accurate state estimation, control, and optimization. To this, we developed methods to remove all spurious links and identify the exact structure of bi-directed networks despite of data corruption.