A controlled sensing approach to graph classification

Jonathan G. Ligo, George K. Atia, Venugopal V. Veeravalli

Research output: Contribution to journalArticlepeer-review

Abstract

The problem of classifying graphs with respect to connectivity via partial observations of nodes is posed as a composite hypothesis testing problem with controlled sensing. An observation at a node is a subset of edges incident to the node on the complete graph drawn according to a probability model, which is a function of a fixed underlying graph. Connectivity is measured through average node degree and is classified with respect to a threshold. A simple approximation of the controlled sensing test is derived and simulated on Erdös-Rènyi graphs to characterize the error probabilities as a function of the expected stopping times. The test is also experimentally validated on a real-world example of the social structure of Long-Tailed Manakins. It is shown that the proposed test achieves favorable tradeoffs between the classification error and the number of measurements. Furthermore, the test outperforms existing approaches, especially at low target error rates. In addition, the proposed test achieves the optimal error exponent.

Original languageEnglish (US)
Article number6936380
Pages (from-to)6468-6480
Number of pages13
JournalIEEE Transactions on Signal Processing
Volume62
Issue number24
DOIs
StatePublished - Dec 15 2014

Keywords

  • Complex networks
  • controlled sensing
  • estimation theory
  • graph classification
  • social networks

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A controlled sensing approach to graph classification'. Together they form a unique fingerprint.

Cite this