Math @ Duke

Publications [#235970] of Robert Calderbank
Papers Published
 Singh, A; Nowak, R; Calderbank, R, Detecting weak but hierarchicallystructured patterns in networks,
Journal of machine learning research : JMLR, vol. 9
(2010),
pp. 749756, ISSN 15324435
(last updated on 2017/12/14)
Abstract: The ability to detect weak distributed activation patterns in networks is critical to several applications, such as identifying the onset of anomalous activity or incipient congestion in the Internet, or faint traces of a biochemical spread by a sensor network. This is a challenging problem since weak distributed patterns can be invisible in per node statistics as well as a global networkwide aggregate. Most prior work considers situations in which the activation/nonactivation of each node is statistically independent, but this is unrealistic in many problems. In this paper, we consider structured patterns arising from statistical dependencies in the activation process. Our contributions are threefold. First, we propose a sparsifying transform that succinctly represents structured activation patterns that conform to a hierarchical dependency graph. Second, we establish that the proposed transform facilitates detection of very weak activation patterns that cannot be detected with existing methods. Third, we show that the structure of the hierarchical dependency graph governing the activation process, and hence the network transform, can be learnt from very few (logarithmic in network size) independent snapshots of network activity. Copyright 2010 by the authors.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

