  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.
