Doctor of Philosophy (PHD)
Electrical and Computer Engineering (Engineering)
Date of Defense
First Committee Member
Manohar N. Murthi
Second Committee Member
Third Committee Member
Fourth Committee Member
Fifth Committee Member
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.
Graph Signal Processing; Network Influence; Sensor Selection
Samarakoon Mudiyanselage, Buddhika, "Efficient Estimation of Signal States in a Graph with Application to Time Varying Conditions" (2018). Open Access Dissertations. 2153.