BIGDATA: Collaborative Research: F: Efficient Distributed Computation of Large-Scale Graph Problems in Epidemiology and Contagion Dynamics

BIGDATA：协作研究：F：流行病学和传染动力学中大规模图问题的高效分布式计算

基本信息

批准号：
1931628
负责人：
Anil Kumar Vullikanti
金额：
$ 33.08万
依托单位：
University of Virginia Main Campus
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-02-27 至 2022-08-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1931628&HistoricalAwards=false
关键词：
BIGDATA Collaborative Research Efficient Distributed

项目摘要

A number of phenomena of societal importance, such as the spread of diseases andcontagion processes, can be modeled by stochastic processes on networks. The analysis and control of such network phenomena involve, at their heart, fundamental graph-theoretic problems. The graphs encountered are typically of large-scale (having tens of millions of nodes); further, typical experimental analyses involve large designs with a number of parameters, leading to hundreds of thousands of graph computations. Novel methods for solving these problemsare needed, since fast response times are critical to effective decision making.The overarching goal of this project is to develop efficient distributed algorithms and associated lower bounds for graph-theoretic problems that arise in computational epidemiology and contagion dynamics. This will have a significant impact on these specific applications, through more efficient algorithmic tools for enabling complex analyses. The project will also make fundamental contributions to the design and analysis of distributed algorithms for graph problems in large-scale networks, and willresult in an algorithmic toolkit with building blocks for performing large-scale distributed graph computation. The project will lead to significant curriculum development for undergraduate as well as graduate students, as well as public health analysts. Finally, the project will help in involving minority and underrepresented students in research. The technical focus of the project will be on distributed algorithms for fundamental topics in graph algorithms such as graph connectivity, distances, subgraph analysis, and differentkinds of centrality measures. These topics underlie some of the recurring problems in the modeling, simulation and analysis and control of different kinds of contagion processes. For all these problems, the project will focus on developing provably efficient distributed algorithms and showing lower bounds under a message-passing distributed computing model. The PIs will also develop efficient implementations of these algorithms, and evaluate their performance and solution quality in real-world graphs arising in epidemiology. The graphs that arise in these applications have several novel characteristics, which will present new challenges as well as opportunities for distributed computing.

许多具有社会重要性的现象，例如疾病的传播和传染过程，可以通过网络上的随机过程进行建模。对此类网络现象的分析和控制本质上涉及基本的图论问题。遇到的图通常是大规模的（有数千万个节点）；此外，典型的实验分析涉及具有多个参数的大型设计，导致数十万次图形计算。需要新的方法来解决这些问题，因为快速响应时间对于有效决策至关重要。该项目的总体目标是开发高效的分布式算法以及计算流行病学和传染动力学中出现的图论问题的相关下限。通过更高效的算法工具来实现复杂的分析，这将对这些特定应用产生重大影响。该项目还将为大规模网络中图问题的分布式算法的设计和分析做出基础性贡献，并将产生一个具有用于执行大规模分布式图计算的构建块的算法工具包。该项目将为本科生、研究生以及公共卫生分析师带来重大的课程开发。最后，该项目将有助于少数族裔和代表性不足的学生参与研究。该项目的技术重点将是图算法中基本主题的分布式算法，例如图连通性、距离、子图分析和不同类型的中心性度量。这些主题是不同类型传染过程的建模、模拟、分析和控制中一些反复出现的问题的基础。对于所有这些问题，该项目将专注于开发可证明有效的分布式算法，并显示消息传递分布式计算模型下的下界。 PI 还将开发这些算法的高效实现，并在流行病学中出现的真实世界图表中评估其性能和解决方案质量。这些应用程序中出现的图具有几个新颖的特征，这将为分布式计算带来新的挑战和机遇。

项目成果

期刊论文数量（10）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks

使用网络上的概率扩散模型控制流行病传播

DOI：
发表时间：
2022-01
期刊：
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics
影响因子：
0
作者：
Babay, Amy E.;Dinitz, Michael;Srinivasan, Aravind;Tsepenekas, Leonidas;Vullikanti, Anil
通讯作者：
Vullikanti, Anil

Generating Massive Scale-free Networks: Novel Parallel Algorithms using the Preferential Attachment Model

生成大规模无标度网络：使用优先附着模型的新型并行算法

DOI：
10.1145/3391446
发表时间：
2020-05
期刊：
ACM Transactions on Parallel Computing
影响因子：
1.6
作者：
Alam, Maksudul;Khan, Maleq;Perumalla, Kalyan S.;Marathe, Madhav
通讯作者：
Marathe, Madhav

Fair Disaster Containment via Graph-Cut Problems

通过图割问题实现公平的灾难控制

DOI：
发表时间：
2022-01
期刊：
Proceedings of The 25th International Conference on Artificial Intelligence and Statistic
影响因子：
0
作者：
Dinitz, Michael;Srinivasan, Aravind;Tsepenekas, Leonidas;Vullikanti, Anil
通讯作者：
Vullikanti, Anil

PREEMPT: Scalable Epidemic Interventions Using Submodular Optimization on Multi-GPU Systems

PREEMPT：在多 GPU 系统上使用子模块优化进行可扩展的流行病干预措施

DOI：
10.1109/sc41405.2020.00059
发表时间：
2020-11-01
期刊：
SC20: International Conference for High Performance Computing, Networking, Storage and Analysis
影响因子：
0
作者：
Marco Minutoli;Prathyush Sambaturu;M. Halappanavar;Antonino Tumeo;A. Kalyanaraman;A. Vullikanti
通讯作者：
A. Vullikanti

Mapping Network States using Connectivity Queries

使用连接查询映射网络状态

DOI：
10.1109/bigdata50022.2020.9378355
发表时间：
2020-12
期刊：
2020 IEEE International Conference on Big Data (Big Data
影响因子：
0
作者：
Rodriguez, Alexander;Adhikari, Bijaya;Gonzalez, Andres D.;Nicholson, Charles;Vullikanti, Anil;Prakash, B. Aditya
通讯作者：
Prakash, B. Aditya