Computational Methods and Consistency for Dirichlet Graph Partitions

这个项目将研究一种特殊的图划分方法的理论性质、计算方法和应用。一般说来，图划分是将一个集合细分为具有所需属性的较小组件的数学问题。这个问题在图像分析(医学、卫星和材料)、监视、社会网络分析和主题建模等方面有多种应用。该项目的结果可能对这些领域产生重大影响，而且由于这项活动的多学科性质，所有参与方都将获得各自领域以外的认识和识字。该项目为首席调查员提供了继续向学生提供建议和指导的机会。这个项目将证明基本的理论结果，并发展Dirichlet图划分问题的计算方法，该问题被表示为最小化每个划分分量的主要Laplace-Dirichlet特征值的和。这种图划分问题具有丰富和可开发的数学结构：它由几何问题驱动，具有变分特征和相关的随机过程。该项目将有三个目标。第一个目标是用适当的度量通过Gamma收敛证明几何图形的Dirichlet划分的相合性结果：当采样点的数目趋于无穷大时，从概率空间采样得到的几何图的Dirichlet划分收敛于该概率空间的Dirichlet划分。这一结果将更好地理解图和连续统划分问题之间的关系，并可能为极大的数据集提供次抽样策略。第二个目标是解决Dirichlet图划分问题的重要计算方面。虽然已经确定了这个问题的两种不同的松弛形式，但基于这些松弛形式的计算方法必然会增加计算复杂性。PI将寻求可证明收敛的新方法，这些方法将变分论点与几何、偏微分方程和马尔可夫过程的思想相结合，以扩展和克服这些缺点。第三个目标是解决具体的、现实世界的问题，并将开发的算法投入实际应用。

This project will investigate theoretical properties, computational methods, and applications for a particular method of graph partitioning. Generally speaking, graph partitioning is the mathematical problem of subdividing a set into smaller components with desirable properties. This problem has diverse applications in image analysis (medical, satellite, and material), surveillance, social network analysis, and topic modeling, among many others. The results of this project could significantly impact these areas and due to the multidisciplinary nature of this activity, all involved parties will gain awareness and literacy outside their own respective fields. The project provides opportunities for the principal investigator to continue advising and mentoring students. This project will prove fundamental theoretical results and develop computational methods for the Dirichlet graph partitioning problem, formulated as minimizing the sum of the principle Laplace-Dirichlet eigenvalues for each partition component. This graph partitioning problem has rich and exploitable mathematical structure: it is motivated by a geometric problem and has both a variational characterization and an associated stochastic process. The project will have three goals. The first goal is to prove, via Gamma convergence with a suitable metric, the consistency result that Dirichlet partitions of geometric graphs, obtained by sampling from a probability space, converge to Dirichlet partitions of that probability space as the number of sampled points tends to infinity. This result will yield a better understanding of the relationship between the graph and continuum partitioning problems as well as possibly suggest subsampling strategies for extremely large datasets. The second goal addresses important computational aspects of the Dirichlet graph partitioning problem. Although two different relaxations of this problem have been identified, computational methods based on these relaxations necessarily have increased computational complexity. The PI will seek provably convergent new methods that combine variational arguments with ideas from geometry, partial differential equations, and Markov processes in order to extend and overcome these shortcomings. The third goal is to address concrete, real-world problems and to engage the developed algorithms in practical applications.