Skip to main content
release_alert
Welcome to the new Scholars 3.0! Read about new features and let us know what you think.
cancel

Detecting weak but hierarchically-structured patterns in networks

Publication ,  Journal Article
Singh, A; Nowak, R; Calderbank, R
Published in: Journal of Machine Learning Research
December 1, 2010

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 network-wide aggregate. Most prior work considers situations in which the activation/non-activation 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 three-fold. 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.

Duke Scholars

Published In

Journal of Machine Learning Research

EISSN

1533-7928

ISSN

1532-4435

Publication Date

December 1, 2010

Volume

9

Start / End Page

749 / 756

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 17 Psychology and Cognitive Sciences
  • 08 Information and Computing Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Singh, A., Nowak, R., & Calderbank, R. (2010). Detecting weak but hierarchically-structured patterns in networks. Journal of Machine Learning Research, 9, 749–756.
Singh, A., R. Nowak, and R. Calderbank. “Detecting weak but hierarchically-structured patterns in networks.” Journal of Machine Learning Research 9 (December 1, 2010): 749–56.
Singh A, Nowak R, Calderbank R. Detecting weak but hierarchically-structured patterns in networks. Journal of Machine Learning Research. 2010 Dec 1;9:749–56.
Singh, A., et al. “Detecting weak but hierarchically-structured patterns in networks.” Journal of Machine Learning Research, vol. 9, Dec. 2010, pp. 749–56.
Singh A, Nowak R, Calderbank R. Detecting weak but hierarchically-structured patterns in networks. Journal of Machine Learning Research. 2010 Dec 1;9:749–756.

Published In

Journal of Machine Learning Research

EISSN

1533-7928

ISSN

1532-4435

Publication Date

December 1, 2010

Volume

9

Start / End Page

749 / 756

Related Subject Headings

  • Artificial Intelligence & Image Processing
  • 17 Psychology and Cognitive Sciences
  • 08 Information and Computing Sciences