Timezone: »

Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries
Daniel Rosenkrantz · Abhijin Adiga · Madhav Marathe · Zirou Qiu · S. S. Ravi · Richard Stearns · Anil Vullikanti

Tue Jul 19 03:30 PM -- 05:30 PM (PDT) @ Hall E #1316

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.

Author Information

Daniel Rosenkrantz (University of Virginia)
Abhijin Adiga (Biocomplexity Institute & Initiative, Univ. of VA)
Madhav Marathe (Biocomplexity Institute & Initiative, University of Virginia)
Zirou Qiu (University of Virginia)
S. S. Ravi (University of Virginia and University at Albany -- SUNY)
Richard Stearns (University at Albany -- SUNY)
Anil Vullikanti (University of Virginia)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors