Title :
Relations between structure and estimators in networks of dynamical systems
Author :
Materassi, Donatello ; Salapaka, Murti V. ; Giarrè, Laura
Author_Institution :
Lab. for Informations & Decision Syst., Massachusetts Inst. of Technol., Cambridge, MA, USA
Abstract :
The article main focus is on the identification of a graphical model from time series data associated with different interconnected entities. The time series are modeled as realizations of stochastic processes (representing nodes of a graph) linked together via transfer functions (representing the edges of the graph). Both the cases of non-causal and causal links are considered. By using only the measurements of the node outputs and without assuming any prior knowledge of the network topology, a method is provided to estimate the graph connectivity. In particular, it is proven that the method determines links to be present only between a node and its “kins”, where kins of a node consist of parents, children and co-parents (other parents of all of its children) in the graph. With the additional hypothesis of strictly casual links, a similar method is provided that allows one to exactly reconstruct the original graph. Main tools for determining the network topology are based on Wiener, Wiener-Hopf and Granger filtering. Analogies with the problem of Compressing Sensing are drawn and two greedy algorithms to address the problem of reducing the complexity of the network structure are also suggested.
Keywords :
computational complexity; filtering theory; greedy algorithms; network theory (graphs); time series; transfer functions; Granger filtering; Wiener filtering; Wiener-Hopf filtering; causal link; children node; compressing sensing problem; coparent node; dynamical system network; graph connectivity; graph edge; graph node; graphical model identification; greedy algorithm; interconnected entity; network structure complexity; network topology; noncausal link; parent node; time series data; transfer functions; Least squares approximation; Network topology; Random variables; Stochastic processes; Topology; Transfer functions; Vectors;
Conference_Titel :
Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on
Conference_Location :
Orlando, FL
Print_ISBN :
978-1-61284-800-6
Electronic_ISBN :
0743-1546
DOI :
10.1109/CDC.2011.6161380