AF: Small: Graph Partitioning and Spectral Methods

点击翻译按钮获取中文摘要

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.