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

AF：中：广义代数图论：算法与分析

• 批准号: 1562041
• 负责人: Daniel Spielman
• 金额: $ 77.41万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1562041&HistoricalAwards=false
• 关键词: AF; Medium; Generalized; Algebraic; Graph

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.

PI将开发用于分析，推理和对图形和网络的预测的新方法。 图和网络出现在整个社会和科学中。 它们包括道路和运输网络，通信网络，电力网络和社交网络。 它们是计算机科学中数据的主要抽象之一，用于模拟从基因组学到图像处理和机器学习等领域的抽象相互作用。该项目具有两个主要的研究推力。 首先是开发用于执行现有分析的更快算法。 第二个是开发新方法来理解图形和网络的结构。 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 tr​​ain 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. 该项目的第一部分将涉及为GSBMS中线性方程系统解的快速算法的开发，这些解决方案可以将其写入为正的semindefinte矩阵的总和，每个矩阵对应于图形的一个边缘。 这些GSBM是Laplacian矩阵的概括，在许多应用领域都会出现，包括优化，计算科学和图像处理。 该项目的第二部分将涉及光谱图理论的概括，以研究具有随机选择的块矩阵的GSBM的预期特征多项式。 光谱图理论一直是分析图和网络的最有用的工具之一。 该理论向随机GSBM的扩展应具有标准方法无法进行的分析。