AF: Small: Graph Partitioning and Spectral Methods

AF：小：图划分和谱方法

• 批准号: 1540685
• 负责人: Luca Trevisan
• 金额: $ 28.97万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-01 至 2017-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1540685&HistoricalAwards=false
• 关键词: AF; Small; Graph; Partitioning; Spectral

Algorithms based on spectral techniques tend to be fast and to have a simple and elegant structure; their analysis helps explain the empirically good performance of related heuristics that are adopted in practice; and their analysis often uncovers useful mathematical relationships between algebraic and combinatorial graph invariants, which can have useful applications outside of algorithm design. The research supported by this grant explores new algorithms for cut and clustering problems, rigorous justifications for popular spectral clustering heuristics, and various relationships between the spectral profile of a graph and its combinatorial properties. The PI and his collaborators will study the use of multiple eigenvectors of the Laplacian matrix of a graph in the design of clustering algorithms, they will provide rigorous analyses of clustering heuristics based on multiple eigenvectors, and will explore combinatorial characterizations of eigenvalue near-multiplicities. New approaches to the use of random walks and other probabilistic processes will be explored in the design of graph partitioning algorithms.The PI is working on a monograph on the three related themes of sparsest cut approximation algorithms, constructions of expander graphs, and analysis of random walks in graphs. The three topics are closely related mathematically, but they are pursued by largely distinct community; the monograph will emphasize the connection and encourage researchers in each of the three areas to pursue research in the others.

基于谱技术的算法往往速度快，结构简单优雅；他们的分析有助于解释实践中采用的相关启发法在经验上的良好表现；他们的分析经常揭示代数和组合图不变量之间有用的数学关系，这些关系可以在算法设计之外有有用的应用。该资助支持的研究探索了用于切割和聚类问题的新算法、流行谱聚类启发式的严格论证，以及图谱轮廓与其组合属性之间的各种关系。 PI 和他的合作者将研究图的拉普拉斯矩阵的多个特征向量在聚类算法设计中的使用，他们将提供基于多个特征向量的聚类启发式的严格分析，并将探索特征值近重数的组合表征。在图划分算法的设计中将探索使用随机游走和其他概率过程的新方法。PI 正在编写一本关于稀疏割逼近算法、扩展图的构造和随机分析这三个相关主题的专着。走在图表中。这三个主题在数学上密切相关，但它们是由很大程度上不同的社区所追求的。该专着将强调相互联系，并鼓励这三个领域的研究人员在其他领域进行研究。