On Systems of Dynamic Graphs: Theory and Applications

Abstract

Graphs are powerful mathematical structures that pose deep theoretical questions and adapt to fascinating applications. Simple graphs have a rich history and many important open problems, but contemporary research in graphs now involves a wide range of extensions: hypergraphs, attributed graphs, graph neural networks, graph algorithms, network analysis, and more. Each of these topics is its own active research area. This dissertation focuses on dynamic graphs, namely graphs whose structure depends on time. We will study traditional simple graphs, as well as some of these extended graph structures, but all through the lens of dynamical systems, where our state space is of graphs or their many variations. To properly study dynamic graphs, we have to leverage techniques from graph theory, algorithms, probability, machine learning, topology, geometry, and other mathematical and computational disciplines. Part of the excitement of dynamic graphs comes from the seemingly unlimited connections to other important areas of study. As an opus of applied mathematics, this work will cover dynamic graphs that arise naturally from a wide range of applications in virology, sociology, sports, biology, electrical engineering, satellite communication, and more. While no document can be complete, this dissertation furnishes a survey on innovative ongoing research in dynamic graphs, insight into their key constructions, a presentation of our contributions to this area with collaborators, strong evidence for their utility in a wide range of applications, and a hint at possible future directions for these elegant structures.