AF: Small: Graph Partitioning and Spectral Methods

AF：小：图划分和谱方法

• 批准号: 1216642
• 负责人: Luca Trevisan
• 金额: $ 40万
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-10-01 至 2015-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1216642&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及其合作者将研究在聚类算法设计中使用图的拉普拉斯矩阵的多重特征向量，他们将提供基于多重特征向量的聚类算法的严格分析，并将探索特征值接近多重性的组合特征。新的方法来使用随机游走和其他概率过程将探讨在设计的图形分割algorithm.The PI是一个专着上的三个相关主题的稀疏割近似算法，建设的扩展图，并分析随机游走的图形。这三个主题在数学上是密切相关的，但它们在很大程度上是由不同的社区追求的;专著将强调这三个领域中的每一个的联系，并鼓励研究人员在其他领域进行研究。