[PAST EVENT] Inference Problems on Dynamic Networks: Fundamental Limits and Efficient Algorithms
Speaker: Abram Magner (University of Michigan)
Title: Inference Problems on Dynamic Networks: Fundamental Limits and Efficient Algorithms
Networks in the wild are dynamic -- nodes and edges are added and removed over time, and time-varying processes (such as epidemics) run on them. This time-varying aspect of networks leads to a wealth of data scientific questions requiring novel algorithmic and statistical methodology to answer them. I will describe some of my recent work on statistical inference and compression problems to address these questions. I will focus on two related lines of work: (i) network archaeology -- broadly concerning problems of dynamic graph model validation (goodness of fit testing) and inference about previous states of a network given a snapshot of its current state, and (ii) structural compression -- exploit graph structural statistics to produce a short bit string encoding of a graph's structure. For both classes of problems, I give both statistical limits and efficient algorithms for achieving those limits. I will present applications to networks from various domains.
Abram Magner received his Ph.D. in Computer Science from Purdue University in December of 2015. He was then an NSF Center for the Science of Information postdoctoral research fellow in the Coordinated Science Lab at the University of Illinois at Urbana-Champaign. As of October 2018, he is a research fellow in the EECS department at the University of Michigan. His research is in the foundational statistical, information-theoretic, and computational problems arising in data science and machine learning for networks. He has also worked on the analysis of random structures arising in computer science applications and information-theoretic models of biological processes such as protein folding and genome sequencing technologies.