{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/46570"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/46570","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"A controlled sensing approach to graph classification","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ligo, Jonathan"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Veeravalli, Venugopal V."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-01-16T17:54:23Z","date_published":"2014-01-16T17:54:23Z","updated_at":"2026-07-22T22:25:36Z","subjects":["Graph Classification","Controlled Sensing","Complex Networks","Social Networks","Estimation Theory"],"languages":["en"],"rights":["Copyright 2013 Jonathan G. Ligo"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/46570","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Veeravalli, Venugopal V."]},{"key":"dc:creator","label":"Author","values":["Ligo, Jonathan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-01-16T17:54:23Z","2013-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Graph Classification","Controlled Sensing","Complex Networks","Social Networks","Estimation Theory"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2013 Jonathan G. Ligo"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/46570"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-12-04T21:07:00Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Ligo_Jonathan.pdf: 1147688 bytes, checksum: 950f31adec8a6a4d713b230039cce6da (MD5)","Made available in DSpace on 2014-01-16T17:54:23Z (GMT). No. of bitstreams: 2 Jonathan_Ligo.pdf: 1147688 bytes, checksum: 950f31adec8a6a4d713b230039cce6da (MD5) license.txt: 4060 bytes, checksum: 3c19a26065239fadc417d0d39e20dca9 (MD5)"]},{"key":"dc:title","label":"Title","values":["A controlled sensing approach to graph classification"]}]}],"canonical_facts":{"dc:contributor":["Veeravalli, Venugopal V."],"dc:creator":["Ligo, Jonathan"],"dc:date":["2014-01-16T17:54:23Z","2013-12"],"dc:description":["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.","Item withdrawn by Laura Spradlin (lspradl2@illinois.edu) on 2013-12-04T21:07:00Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Ligo_Jonathan.pdf: 1147688 bytes, checksum: 950f31adec8a6a4d713b230039cce6da (MD5)","Made available in DSpace on 2014-01-16T17:54:23Z (GMT). No. of bitstreams: 2 Jonathan_Ligo.pdf: 1147688 bytes, checksum: 950f31adec8a6a4d713b230039cce6da (MD5) license.txt: 4060 bytes, checksum: 3c19a26065239fadc417d0d39e20dca9 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/46570"],"dc:language":["en"],"dc:rights":["Copyright 2013 Jonathan G. Ligo"],"dc:subject":["Graph Classification","Controlled Sensing","Complex Networks","Social Networks","Estimation Theory"],"dc:title":["A controlled sensing approach to graph classification"],"dc:type":["text"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:36Z"}