Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries

Using a discrete dynamical system model, many papers have addressedthe problem of learning the behavior (i.e., the local function ateach node) of a networked system through active queries, assumingthat the network topology is known. We address the problem ofinferring both the topology of the network and the behavior of adiscrete dynamical system through active queries. We consider twoquery models studied in the literature, namely the batch model(where all the queries must be submitted together) and the adaptivemodel (where responses to previous queries can be used in formulatinga new query). Our results are for systems where the state of eachnode is from {0,1} and the local functions are Boolean. We presentalgorithms to learn the topology and the behavior under both batchand adaptive query models for several classes of dynamical systems.These algorithms use only a polynomial number of queries. We alsopresent experimental results obtained by running our query generationalgorithms on synthetic and real-world networks.