A controlled sensing approach to graph classification

Ligo, Jonathan

Permalink

https://hdl.handle.net/2142/46570 Copy

Description

Title

A controlled sensing approach to graph classification

Author(s)

Ligo, Jonathan

Issue Date

2014-01-16T17:54:23Z

Director of Research (if dissertation) or Advisor (if thesis)

Veeravalli, Venugopal V.

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

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

Abstract

Graphs are used to model dependency structures, such as communication networks, social networks, and biological networks. Observing the graph in its entirety may be undesirable due to size of the graph or noise in observations, especially if only a function of the graph structure is of interest, such identifying one of finitely many classes to which the graph belongs. In this thesis, we develop a framework for jointly classifying a graph and sampling a graph in order to maximize the decay of classification error probability with sample size by formulating the classification problem as a composite sequential hypothesis test with control. In contrast to prior work, posing the problem as a composite sequential hypothesis test with control provides provable performance guarantees through the controlled sensing framework and allows the classification problem to improve the quality of observations in the sampling procedure. The algorithm proposed in this thesis is demonstrated by classifying graphs with respect to average node degree as a measure of connectivity. Observations of the graph are collected by selecting a node to sample and observing some subset of possible edges in the complete graph incident to the node according to two probability models, where observations are conditionally independent given their neighborhoods in the graph. Simulations are provided for an Erdos-Renyi graph to show the trade-off between sample size and classification performance and show that the proposed algorithm outperforms a random walk-based technique.

Graduation Semester

2013-12

Permalink

http://hdl.handle.net/2142/46570

Copyright and License Information

Copyright 2013 Jonathan G. Ligo

Owning Collections