Thesis
State detection from local measurements in complex networks: algebraic, spectral, and graph-theoretic results
Washington State University
Master of Science (MS), Washington State University
2012
Handle:
https://hdl.handle.net/2376/103958
Abstract
The research presented here is motivated by emerging problems in estimation and identification of complex network dynamics, from such diverse domains as sleep modeling and cyber-physical system security. Based on this motivation, the problem of detecting the initial state of a linear network dynamics from a sequence of noisy local observations is examined, from algebraic, spectral, and graph-theoretic perspectives. Specifically, a discrete-time linear synchronization process defined on an underlying graph is considered. The synchronization dynamics are modeled as being initiated by two possible initial conditions (or hypotheses) with certain a priori probabilities, to capture two possible evolutions of the network dynamics; an external agent is modeled as measuring the network dynamics at one network component, and is tasked with determining which hypothesis is more likely. The goals of the study are 1) to derive an algebraic expression for the minimum a posteriori error initial-condition detector, 2) to examine the performance of the decision criterion (detector) by determining the corresponding probability of error, and 3) to explore how the graph structure impacts detection performance, in part via a spectral analysis. We find that the detector performance can be classified into three cases, depending on the network's graph topology, the hypotheses, and the observation location. Specifically, the detector performance can be dichotomized into: 1) a no-improvement case, in which the measured data does not permit improved detection compared to an a priori detection; 2) an asymptotically-perfect case in which the error probability approaches 0 with increasing measurement horizon; and 3) an improved-but-imperfect estimation case in which measurements reduce error but do not eliminate it. In addition, the network's graph topology is shown to modulate the amount of data needed for low-error detection.
Metrics
6 File views/ downloads
15 Record Views
Details
- Title
- State detection from local measurements in complex networks
- Creators
- Chih Wei Chen
- Contributors
- Sandip Roy (Degree Supervisor)
- Awarding Institution
- Washington State University
- Academic Unit
- Electrical Engineering and Computer Science, School of
- Theses and Dissertations
- Master of Science (MS), Washington State University
- Publisher
- Washington State University; Pullman, Wash. :
- Identifiers
- 99900525113001842
- Language
- English
- Resource Type
- Thesis