Computational Methods and Consistency for Dirichlet Graph Partitions

狄利克雷图划分的计算方法和一致性

• 批准号: 1619755
• 负责人: Braxton Osting
• 金额: $ 18万
• 依托单位: University of Utah
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1619755&HistoricalAwards=false
• 关键词: Computational; Methods; Consistency; Dirichlet; Graph

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.

本计画将探讨一种特殊的图分割方法的理论性质、计算方法与应用。一般来说，图划分是将一个集合细分为具有所需属性的较小组件的数学问题。这个问题在图像分析（医学、卫星和材料）、监控、社交网络分析和主题建模等方面有着广泛的应用。该项目的结果可能会对这些领域产生重大影响，由于该活动的多学科性质，所有参与方都将获得各自领域以外的认识和知识。该项目为主要研究者提供了继续为学生提供咨询和指导的机会。这个项目将证明基本的理论结果，并开发计算方法的Dirichlet图分割问题，制定为最小化的总和的原则拉普拉斯-Dirichlet特征值为每个分区组件。这个图划分问题具有丰富的和可利用的数学结构：它是由一个几何问题的动机，并具有变分表征和相关的随机过程。该项目将有三个目标。第一个目标是证明，通过Gamma收敛与一个合适的度量，一致性的结果，几何图的Dirichlet分区，通过从概率空间采样，收敛到Dirichlet分区的概率空间的采样点的数量趋于无穷大。这一结果将产生一个更好的理解之间的关系图和连续划分问题，以及可能建议的子采样策略，非常大的数据集。第二个目标解决了Dirichlet图划分问题的重要计算方面。虽然已经确定了这个问题的两个不同的松弛，基于这些松弛的计算方法必然增加了计算复杂性。PI将寻求可证明收敛的新方法，结合联合收割机变分参数与几何，偏微分方程和马尔可夫过程的想法，以扩展和克服这些缺点。第三个目标是解决具体的现实问题，并将开发的算法应用于实际应用。