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