A controlled sensing approach to graph classification

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Ligo, Jonathan

Contributors dc:contributor

• Veeravalli, Venugopal V.

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

Statement dc:rights

• Copyright 2013 Jonathan G. Ligo

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/46570