Publication Date

2018-08-02

Availability

Open access

Embargo Period

2018-08-02

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PHD)

Department

Electrical and Computer Engineering (Engineering)

Date of Defense

2018-06-01

First Committee Member

Manohar N. Murthi

Second Committee Member

Kamal Premaratne

Third Committee Member

Xiaodong Cai

Fourth Committee Member

Odelia Schwartz

Fifth Committee Member

Jie Xu

Abstract

Developing efficient models for analyzing data generated in networks is of great importance in the modern world. Compared to conventional datasets, modeling network based datasets present certain unique challenges. These include but are not limited to building models of interactions among nodes and modeling temporal variations in data. These models and other relevant algorithms for such datasets should also be scalable to large networks that are prevalent in current scientific fields. Furthermore, any of these models and algorithms should be able to incorporate time varying network structures, a problem that has received limited attention within the research community. The research work presented in this thesis addresses these challenges using three approaches. First, a probabilistic model is presented for modeling hidden states of the nodes in a network. Then, an efficient inference algorithm is developed in order to infer these hidden variables based on the observable signals of these nodes. Finally, an efficient node selection algorithm is derived for the purpose of selecting subset of nodes in a large time varying network such that we can make the inference process more efficient. The probabilistic model developed in this thesis demonstrates that, by modeling neighbor interactions and temporal variations in a graph based dataset one can accurately infer the hidden states compared to conventional probabilistic models. This method models the joint distribution of both observed and hidden variables of the nodes thereby allowing us to infer latent states of all the nodes by observing only a subset of nodes in a large network. Experiments show that this model has better generalizing ability for real word data compared to the other models. From the node selection algorithms presented in this thesis, it is evident that while it is suboptimal, we can make greedy random variable selection methods more efficient under certain selection criteria. In particular, this thesis presents greedy algorithms that takes O(n^3) time to select random variables in a multivariate Guassian under two criteria compared to the O(n^4) time for the existing algorithms. The two selection criteria considered in this thesis are, minimizing mean squared error (MMSE) and the minimizing uncertainty volume of the estimation. Based on this initial greedy random variable selection method, this thesis develops algorithms to select nodes in a graph based Gaussian Markov random field (GMRF) in time varying conditions. The node selection algorithms for time varying graphs presented in this thesis shows us how one can achieve O(n^2) time performance in the best case by using the previous time step's computations for the greedy optimization. Finally, this research work also examine how the node selection method based on MMSE criterion for a graph based GMRF can be related to an absorbing random walk on that graph.

Keywords

Graph Signal Processing; Network Influence; Sensor Selection

Share

COinS