AF: Small: Spectral Graph Theory, Point Clouds, and Linear Equation Solvers

AF：小：谱图理论、点云和线性方程求解器

• 批准号: 0915487
• 负责人: Daniel Spielman
• 金额: $ 49.69万
• 依托单位: Yale University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0915487&HistoricalAwards=false
• 关键词: AF; Small; Spectral; Graph; Theory

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).Two of the most important abstractions in Computer Science are graphs and point clouds. A graph abstracts relations between things: two vertices in a graph are connected by an edge if the objects associated with the vertices are related. Directed edges indicate a connection from one vertex to another. Both social networks and the web are modeled as graphs: vertices could represent people with edges between friends, or they may represent web pages with directed edges representing links. Point clouds are sets of vectors, each vector providing a list of numerical attributes. In many computer science applications, one associates a vector with each object being examined. For example, one may rate on a numerical scale different properties of a chemical, or how much a person likes movies from certain genres.This project will unify these two abstractions by translating point clouds into graphs. Each vector becomes a vertex in a graph, with the strength of the edge connecting two vertices indicating the degree of similarity of the corresponding vectors. This translation will enable the application of numerous techniques that have been developed in graph theory to the study of point clouds.Technical objectives of the project include the determination of the best graph to associate with a point cloud, the development of efficient algorithms for the construction of such a graph, and the development of new approaches to the analysis of graphs. In particular, a spectral analysis of directed graphs will be developed.Both graduate students and undergraduates will be trained in research while working on this project. Educational materials developed during the course of the project will be disseminated through the internet as well as incorporated into a book under development.

该奖项由2009年《美国复苏和再投资法案》（Public Law 111-5）资助。计算机科学中最重要的两个抽象概念是图形和点云。 图抽象了事物之间的关系：如果与顶点相关联的对象是相关的，则图中的两个顶点由边连接。 有向边表示从一个顶点到另一个顶点的连接。 社交网络和web都被建模为图：顶点可以表示朋友之间的边，或者它们可以表示具有表示链接的有向边的网页。 点云是一组矢量，每个矢量提供一个数值属性列表。 在许多计算机科学应用中，人们将向量与每个被检查的对象相关联。 例如，一个人可能会在一个数字尺度上评价一种化学物质的不同属性，或者一个人有多喜欢某些类型的电影。这个项目将通过将点云转换为图形来统一这两个抽象。 每个向量都成为图中的一个顶点，连接两个顶点的边的强度表示相应向量的相似程度。 该项目的技术目标包括确定与点云相关联的最佳图，开发用于构建这种图的有效算法，以及开发新的图形分析方法。 特别是有向图的频谱分析将被开发。研究生和本科生都将在这个项目工作的同时接受研究培训。 在项目执行过程中编写的教育材料将通过因特网传播，并将编入正在编写的一本书。