A Controlled Sensing Approach to Graph Classification

    Authors

    IEEE Trans. Signal Process.

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Publ. Astron. Soc. Pac.

    Keywords

    Complex networks; controlled sensing; estimation theory; graph; classification; social networks; SOCIAL NETWORK; Engineering, Electrical & Electronic

    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 Erdos-Renyi 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.

    Subjects

    J. G. Ligo; G. K. Atia;V. V. Veeravalli

    Volume

    62

    Issue/Number

    24

    Publication Date

    1-1-2014

    Document Type

    Article

    Language

    English

    First Page

    6468

    Last Page

    6480

    WOS Identifier

    WOS:000345516000010

    ISSN

    1053-587X

    Share

    COinS