6533b7dcfe1ef96bd12729aa
RESEARCH PRODUCT
Relations between structure and estimators in networks of dynamical systems
Laura GiarreMurti V. SalapakaDonatello Materassisubject
Discrete mathematicsTheoretical computer scienceDirected graphStrength of a graphSettore ING-INF/04 - AutomaticaLeast squares approximation Network topology Random variables Stochastic processes TopologyGraph (abstract data type)Graph propertyNull graphRandom geometric graphComplement graphConnectivityMathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2011-12-01 | IEEE Conference on Decision and Control and European Control Conference |