UC Santa Barbara

Graphs are a powerful tool for the study of dynamic processes, where a set of interconnected entities change their states according to the time-varying behavior of an underlying complex system. For instance, in a social network, an individual's opinions are influenced by their contacts; while, in a traffic network, traffic conditions are spatially localized due to the fact that vehicles are often constrained to move along roads. Understanding the interplay between structure and dynamics in networked systems enables new models, algorithms, and data structures for managing and learning from large amounts of data arising from these processes.

This dissertation is focused on recent work on the analysis of dynamic graph processes. More specifically, we will show how sampling and spectral graph theory can be applied to effectively represent data from such processes. We also present efficient algorithms for learning Interleaved Markov Models (IHMMs). These are powerful latent variable models that enable the clustering of discrete sequences without training data and lead to interesting challenges in terms of inference. Furthermore, we also discuss how graphs can be modified in order to control a process of interest via network design and introduce three ongoing projects on the subject of this dissertation. The statement of the thesis is that mining and modeling processes on graphs leads often to problems that are not not only hard computationally but also in terms of inference. They can be solved using spectral, probabilistic, and combinatorial optimization algorithms, and must take into account the graph structure and also large amounts of data traces from these processes.