AF: Medium: Generalized Algebraic Graph Theory: Algorithms and Analysis

点击翻译按钮获取中文摘要

The PI will develop new methods for analyzing, reasoning about, and making predictions about graphs and networks. Graphs and networks appear throughout society and science. They include road and transportation networks, communication networks, power networks and social networks. They are one of the dominant abstractions of data in Computer Science, and are used to model abstract interactions in fields ranging from Genomics to Image Processing and Machine Learning.The project has two major research thrusts. The first is the development of faster algorithms for performing existing analyses. The second is the development of new approaches to understanding the structure of graphs and networks. During the project, the PI will also develop and distribute course materials to teach recent developments in the field, will give public lectures on related material, will train graduate and undergraduate students in research, and will develop software that others can use to perform these analyses.The fundamental object to be studied in this project are graph structured block matrices (GSBMs)---block matrices whose nonzero structure corresponds to the edges of a graph. The first part of the project will involve the development of fast algorithms for the solution of systems of linear equations in GSBMs that can be written as a sum of positive semindefinte matrices with each matrix corresponding to one edge of the graph. These GSBMs are generalizations of Laplacian matrices and arise in many application areas, including Optimization, Computational Science, and Image Processing. The second part of the project will involve the generalization of spectral graph theory to the study of the expected characteristic polynomials of GSBMs with randomly chosen block matrices. Spectral graph theory has been one of the most useful tools for analyzing graphs and networks. The extension of the theory to random GSBMs should enable analyses that are not possible with the standard approach.