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

PI将开发分析、推理和预测图形和网络的新方法。图表和网络出现在整个社会和科学领域。它们包括道路和交通网络、通信网络、电力网络和社会网络。它们是计算机科学中主要的数据抽象之一，并用于从基因组学到图像处理和机器学习等领域的抽象交互建模。该项目有两个主要的研究重点。首先是开发更快的算法来执行现有的分析。第二是发展了理解图和网络结构的新方法。在项目期间，PI还将开发和分发课程材料，教授该领域的最新发展，将对相关材料进行公开讲座，将培训研究生和本科生进行研究，并将开发其他人可以用来执行这些分析的软件。本课题研究的基本对象是图结构块矩阵（GSBMs）——其非零结构对应于图的边的块矩阵。该项目的第一部分将涉及开发用于求解GSBMs中线性方程组的快速算法，这些方程组可以写成正半不定矩阵的和，每个矩阵对应于图的一条边。这些gsbm是拉普拉斯矩阵的推广，出现在许多应用领域，包括优化、计算科学和图像处理。该项目的第二部分将涉及将谱图理论推广到随机选择块矩阵的gsbm的预期特征多项式的研究。谱图理论一直是分析图和网络最有用的工具之一。将该理论扩展到随机gsbm应该能够进行标准方法无法进行的分析。

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.