Committee: Ambuj Singh (Chair), Xifeng Yan, Subhash Suri, Ananthram Swami

Title: Mining and Modeling Processes on Graphs

Abstract:

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.

In this talk, I will overview my recent work on the analysis of dynamic graph processes, which has connections with data mining, signal processing, and machine learning on graphs. More specifically, I will present two problems in the context of graph processes and describe their solutions using spectral graph theory. Both problems ask for compact and accurate representations for traces of graph processes. However, while the first focuses on a single snapshot, the second addresses the more general case of dynamic graphs. Furthermore, I will introduce two new problems in the same sub-area and discuss how they will be solved as part of my thesis.