Source-linked AI summary
Topological identification in networks of dynamical systems
Donatello W. Materassi, Giacomo W. Innocenti
TL;DR
The paper tackles reconstruction of an unknown topology in networks of dynamical systems. It defines a process-distance measure and proves topology-recovery results for linear systems with tree structure. An application to high-frequency stock-market data illustrates the approach in a complex setting.
Problem
Reconstructing an unknown network topology from process data, a problem with few theoretical results and no formal treatment of dynamical-node networks.
Method
Define a coherence-based distance between processes and recover the tree topology by evaluating the corresponding minimum spanning tree.
Results
For a well-posed Linear Cascade Model Tree, the estimated minimum spanning tree converges to the unique minimum spanning tree associated with the coherence metric as observation time approaches infinity.
Takeaways & Limitations
The procedure provides a theoretically justified way to identify tree-structured dynamical networks and captures useful information in complex financial stock-price data.
Takeaways & Limitations
The financial application acknowledges that stock markets may involve multiple inputs, nonlinear relations, and feedbacks beyond the linear SISO tree model.
Abstract
from arXiv · showhide
The paper deals with the problem of reconstructing the topological structure of a network of dynamical systems. A distance function is defined in order to evaluate the "closeness" of two processes and a few useful mathematical properties are derived. Theoretical results to guarantee the correctness of the identification procedure for networked linear systems with tree topology are provided as well. Finally, the application of the techniques to the analysis of an actual complex network, i.e. to high frequency time series of the stock market, is illustrated.
I. INTRODUCTION
The paper addresses the largely unresolved problem of reconstructing unknown network topology from data, focusing on tree-structured networks of dynamical systems. It proposes applying this problem to high-frequency financial-stock data.
- Very few theoretical results address reconstructing an unknown topology from data, motivating the paper’s focus on tree topology networks.
- Existing tree-reconstruction methods such as UPGMA guarantee exact recovery only when the node relationships form an ultrametric.
- The paper identifies reconstructing unknown networks of dynamical systems as a formally uninvestigated problem.
- The proposed techniques are applied to high-frequency real data from a portfolio of financial stocks.
II. PROBLEM SET UP
The paper models noisy linear dynamical systems connected as a tree and uses Wiener-filter-based prediction errors and coherence to quantify process dependence. These quantities support a distance whose triangle inequality and tree-identification properties enable topology recovery through a minimum spanning tree.
- System model: The model consists of time-discrete SISO linear dynamical systems with additive, zero-mean wide-sense stationary noises.
- System model: A Linear Cascade Model Tree represents systems interconnected in a rooted tree, with each node driven by another process and mutually uncorrelated noises.
- Dependence measure: The Wiener filter minimizes a filtered quadratic prediction error, whose residual is uncorrelated with the predicting process.
- Dependence measure: Choosing the weighting function through spectral factorization makes the minimized cost depend explicitly on coherence and independent of process energy.
- Distance properties: The coherence-based distance satisfies the triangle inequality, making it a mathematical distance for comparing processes.
III. MAIN RESULT
The paper derives coherence inequalities showing that the coherence-based distance is minimized between directly connected nodes in a well-posed LCMT. Consequently, the unique minimum spanning tree recovers the network topology as the observation horizon grows, while the root remains non-identifiable.
- III. MAIN RESULT: The coherence inequalities compare ancestor, descendant, and non-descendant nodes, becoming strict when the LCMT is well-posed.These lemmas establish the ordering needed to distinguish adjacent from non-adjacent nodes using process coherence.
- III. MAIN RESULT: For any node and a non-neighbor, some directly linked node has smaller coherence-based distance.The inequality is strict for well-posed LCMTs, making direct links identifiable through distance minimization.
- III. MAIN RESULT: With sufficiently long observations, the minimum spanning tree of estimated coherence distances converges to the unique LCMT topology.The result relies on spectral and cross-spectral density estimates converging as the observation horizon approaches infinity.
- III. MAIN RESULT: The recovered tree structure does not identify the root, because the same processes and tree can be represented with another node as root.The root can be shifted iteratively along paths, and the modeling choice is arbitrary for non-causal transfer functions.
IV. NUMERICAL EXAMPLES
Numerical simulations test coherence-based topological identification on randomly generated tree networks, using finite time series and extracting an MST from coherence distances. The real topology is correctly recovered across repeated ten-node and fifty-node simulations, while finite-horizon computation motivates sufficiently long observations.
- Numerical considerations: Finite observation intervals introduce numerical error, so the examples use sufficiently long time spans because the coherence function is computed only over limited intervals.The procedure must be performed offline because the processes are evaluated over their entire time span.
- Simulation setup: The simulations generate random causal transfer functions of at most second order on randomly chosen tree topologies with equal noise-to-signal ratios.Networks are simulated over 1000 time steps with pseudorandomly generated noises.
- Identification procedure: Coherence-based distances are computed from the simulated signals and used to extract the MST defining the estimated link topology.
- Ten-node networks: Repeated ten-node simulations correctly identify the real topology in every considered network configuration.One configuration is shown in Figure 1, with its coherence-based distance matrix reported in Table I.
- Fifty-node networks: Repeated fifty-node simulations also successfully identify the real network topology in every performed simulation under the same assumptions.Figure 2 shows one representative fifty-node configuration.
V. STOCK MARKET ANALYSIS
The paper applies its topology-identification technique to high-frequency stock data, using averaged daily coherence-based distances to extract a minimum spanning tree. The resulting structure groups many stocks by business sector while also revealing finer industry clusters and exceptions.
- Application to financial data: The method is applied to a nonlinear stock-market network with multiple dependencies to identify its strongest links.The authors frame the tree model as a way to detect important linear dependencies despite the market’s nonlinear, multiply dependent structure.
- Data and preprocessing: The dataset contains 100 New York Stock Exchange stocks sampled every 2 minutes over twenty market days from 03/03/2008 to 03/28/2008.Stocks were selected from the 100 highest-trading-volume companies according to the Standard & Poor Index on the first observation day.
- Data and preprocessing: Daily coherence-based distances are averaged across sessions before extracting the minimum spanning tree, reducing trend and seasonal effects without an additional detrending phase.The authors process each day separately because the full price series is nonstationary and discontinuities occur between trading days.
- Results: The extracted tree satisfactorily groups stocks by business sector, with Financial, Consumer, Basic Materials, Energy, and Transportation sectors perfectly grouped.The sector organization is treated as an external classification rather than a requirement that every stock match its assigned sector exactly.
- Results: The tree also reveals subclusters within Financial, Consumer, and Energy sectors, while Verizon, AT&T, and Sprint form an isolated telephone-company group within Services.Utilities/Electricity companies form a distinct group, and Services separate into Retail and Information Technology clusters alongside the isolated telephone companies.
VI. CONCLUSIONS
The paper presents a distance-based procedure for identifying tree structures in networks of linear dynamical systems and supplies theoretical guarantees for its correctness. Its stock-price application indicates that a tree topology can capture information in a complex financial setting.
- Conclusions: The paper proposes a procedure that uses a distance function to identify the structure of linear dynamical networks with tree topology.The distance evaluates whether a direct link exists between two nodes.
- Conclusions: Theoretical results are provided to guarantee the correctness of the identification procedure.
- Conclusions: Application to real stock-price data shows that a tree topology can capture information in a complex financial setting.