Quickest Detection of Markov Networks

Detecting correlation structures in large networks arises in many domains. Such detection problems are often studied independently of the underlying data acquisition process, rendering settings in which data acquisition policies and the associated sample size are pre-specified. Motivated by the advantages of data-adaptive sampling in data dimensionality reduction, especially in large networks, as well as enhancing the agility of the sampling process, this paper treats the inherently problems of data acquisition and correlation detection. Specifically, this paper considers a network of nodes generating random variables and designs the quickest sequential sampling strategy for collecting data and reliably deciding whether the network is a Markov network with a known correlation structure. By abstracting the Markov network as an undirected graph, in which the vertices represent the random variables and their connectivities model the correlation structure of interest, designing the quickest sampling strategy becomes equivalent to sequentially and data-adaptively identifying and sampling a sequence of vertices in the graph. Optimal sampling strategies are proposed and their associated optimality guarantees are established. Performance evaluations are provided to demonstrate the gains of the proposed sequential approaches.