Models and Inference with Network Structure

In this thesis, the focus is on data that has network structure and on problems that benefit from the application of network-based algorithms. We target four research problems of interest: scalable and realistic models for network valued data, graph-based estimation of information theoretic quantities, summarization of complex time-varying data using dynamic graphs, and finally community detection on large multi-layer networks. This work advances the state-of-the-art in several directions. First, it introduces a new framework for complex network interaction data using the concept of edge exchangability. Second, it obtains new tight bounds for the multi-class Bayes error rate based on a graph-based technique, specifically the minimal spanning tree. Third, it introduces a new estimation method for Henze-Penrose divergence, a quantity relevant for graph-based multi-class classification. Fourth, it introduces adaptive directed information for estimating directed interaction networks. Fifth, the thesis presents a comprehensive approach to multi-layer network community detection. Throughout, examples are provided using real datasets, such as the Enron email dataset, an arXiv dataset, and Twitter.PHDElectrical Engineering: SystemsUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttps://deepblue.lib.umich.edu/bitstream/2027.42/153433/1/boselio_1.pd