# Learning the Topology and Behavior of Discrete Dynamical Systems

arXiv: https://arxiv.org/abs/2402.11686 · HTML: https://mlsanity.com/paper/2402.11686/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 40 references that are in the map.
- First posted on arXiv 18 Feb 2024.

## Builds on (most cited first, 9 of 9)

- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [Catch'Em All: Locating Multiple Diffusion Sources in Networks with Partial Observations](https://mlsanity.com/paper/1611.06963/) (2016)
- [Learning Mixtures of Linear Dynamical Systems](https://mlsanity.com/paper/2201.11211/) (2022)
- [Inferring Graphs from Cascades: A Sparse Recovery Framework](https://mlsanity.com/paper/1505.05663/) (2015)
- [Network Inference and Influence Maximization from Samples](https://mlsanity.com/paper/2106.03403/) (2021)
- [Trace Complexity of Network Inference](https://mlsanity.com/paper/1308.2954/) (2013)
- [Reconstructing parameters of spreading models from partial observations](https://mlsanity.com/paper/1608.08698/) (2016)
- [Prediction-Centric Learning of Independent Cascade Dynamics from Partial Observations](https://mlsanity.com/paper/2007.06557/) (2020)
- [Diffusion Source Identification on Networks with Statistical Confidence](https://mlsanity.com/paper/2106.04800/) (2021)

## Built on by (most cited first, 1 of 1)

- [Predicting Time Series of Networked Dynamical Systems without Knowing Topology](https://mlsanity.com/paper/2412.18734/) (2024)

## Abstract (arXiv)

Discrete dynamical systems are commonly used to model the spread of contagions on real-world networks. Under the PAC framework, existing research has studied the problem of learning the behavior of a system, assuming that the underlying network is known. In this work, we focus on a more challenging setting: to learn both the behavior and the underlying topology of a black-box system. We show that, in general, this learning problem is computationally intractable. On the positive side, we present efficient learning methods under the PAC model when the underlying graph of the dynamical system belongs to some classes. Further, we examine a relaxed setting where the topology of an unknown system is partially observed. For this case, we develop an efficient PAC learner to infer the system and establish the sample complexity. Lastly, we present a formal analysis of the expressive power of the hypothesis class of dynamical systems where both the topology and behavior are unknown, using the well-known formalism of the Natarajan dimension. Our results provide a theoretical foundation for learning both the behavior and topology of discrete dynamical systems.