Computational Methods and Consistency for Dirichlet Graph Partitions
Computational Methods and Consistency for Dirichlet Graph Partitions
批准号:
1619755
负责人:
Braxton Osting
金额:
$18.0万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2016
资助国家:
美国
项目状态:
已结题
起止时间:
2016-07-01 至 2020-06-30
中文摘要
这个项目将研究图划分的理论性质、计算方法和应用。一般来说,图划分是将一个集合细分为具有理想属性的更小的组件的数学问题。这个问题在图像分析(医疗、卫星和材料)、监视、社会网络分析和主题建模等方面有不同的应用。这个项目的结果可能会对这些领域产生重大影响,由于这项活动的多学科性质,所有有关各方都将获得各自领域以外的认识和知识。该项目为首席研究员提供了继续为学生提供建议和指导的机会。该项目将证明狄利克雷图划分问题的基本理论结果并开发计算方法,该问题被表述为最小化每个划分分量的主要拉普拉斯-狄利克雷特征值的总和。这种图划分问题具有丰富的可开发的数学结构:它是由一个几何问题驱动的,既有变分表征,又有相关的随机过程。该项目将有三个目标。第一个目标是通过Gamma收敛和一个合适的度量,证明从一个概率空间中采样得到的几何图的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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
CAREER: Variational and Geometric Methods for Data Analysis
-
批准号:1752202
-
项目类别:Continuing Grant
-
资助金额:$40.0万
-
财政年份:2018
-
负责人:Braxton Osting
-
依托单位:
Geometric Methods for Graph Partitioning
-
批准号:1418812
-
项目类别:Standard Grant
-
资助金额:$7.9万
-
财政年份:2014
-
负责人:Braxton Osting
-
依托单位:
Geometric Methods for Graph Partitioning
-
批准号:1461138
-
项目类别:Standard Grant
-
资助金额:$7.9万
-
财政年份:2014
-
负责人:Braxton Osting
-
依托单位:
PostDoctoral Research Fellowship
-
批准号:1103959
-
项目类别:Fellowship Award
-
资助金额:$13.5万
-
财政年份:2011
-
负责人:Braxton Osting
-
依托单位:
国内基金
海外基金
Computational Methods for Analyzing Toponome Data
-
批准号:60601030
-
项目类别:青年科学基金项目
-
资助金额:17.0万元
-
批准年份:2006
-
负责人:Axel Mosig
-
依托单位: