We discuss recent work that begins bridging the gap between real-world network analysis and structural graph algorithms. In particular, we demonstrate that a form of structural sparsity known as bounded expansion is a deep structural property of networks that is simultaneously algorithmically useful, predicted by many mathematical models of complex networks, and observed in practice in real-world network data. We highlight results proving a dichotomy in generative network models with respect to this structure and give empirical evidence of bounded expansion in real network data. Finally, we will present the algorithmic pipeline giving efficient algorithms in bounded-expansion classes and an implementation for motif counting. This is joint work with E. Demaine, F. Reidl, P. Rossmanith, F. Sanchez Villaamil, and S. Sikdar.
Blair D. Sullivan is an Assistant Professor in the Department of Computer Science at North Carolina State University, and holds a Joint Faculty Appointment at Oak Ridge National Laboratory. Her current research focuses on enabling the application of structural graph algorithms to real-world challenges in the analysis of complex networks, including new methods for identifying and leveraging structural sparsity. Before joining NC State, Dr. Sullivan was a computational mathematician at ORNL, and a visiting researcher at the Renyi Institute in Budapest, Hungary. She received her Ph.D. in Mathematics at Princeton University as a Department of Homeland Security Graduate Fellow, and bachelor's degrees in Applied Mathematics and Computer Science at Georgia Tech. Dr. Sullivan is a Moore Investigator in Data-Driven Discovery and a 2014 National Consortium for Data Science Faculty Fellow.