Title

A Controlled Sensing Approach To Graph Classification

Keywords

Complex Networks; Controlled Sensing; Estimation Theory; Graph Classification; Social Networks

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 are modeled as conditionally independent given their neighborhoods. 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 Model A graphs to characterize error probabilities as a function of expected stopping times. It is shown that the proposed test achieves favorable tradeoffs between the classification error and the number of measurements and further outperforms existing approaches, especially at low target error rates. Furthermore, the proposed test achieves asymptotically optimal error performance, as the error rate goes to zero. © 2013 IEEE.

Publication Date

10-18-2013

Publication Title

ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings

Number of Pages

5573-5577

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ICASSP.2013.6638730

Socpus ID

84890482974 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84890482974

This document is currently not available here.

Share

COinS