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

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

• 批准号: 1633720
• 负责人: Gopal Pandurangan
• 金额: $ 54.99万
• 依托单位: University of Houston
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2022-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1633720&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还将开发这些算法的有效实现，并评估其在流行病学中产生的现实图表中的性能和解决方案质量。 这些应用程序中出现的图具有几个新颖的特征，这些特征将带来新的挑战以及分布式计算的机会。

项目成果

Efficient Distributed Algorithms in the k-machine model via PRAM Simulations

通过 PRAM 模拟的 k 机模型中的高效分布式算法

• DOI: 10.1109/ipdps49936.2021.00031
• 发表时间: 2021
• 期刊: 2021 IEEE International Parallel and Distributed Processing Symposium (IPDPS
• 作者: Augustine, John;Kothapalli, Kishore;Pandurangan, Gopal
• 通讯作者: Pandurangan, Gopal

Efficient Distributed Algorithms for the K-Nearest Neighbors Problem

K近邻问题的高效分布式算法

• DOI: 10.1145/3350755.3400268
• 发表时间: 2020
• 期刊: SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures
• 作者: Fathi, Reza;Molla, Anisur Rahaman;Pandurangan, Gopal
• 通讯作者: Pandurangan, Gopal

Efficient Distributed Community Detection in the Stochastic Block Model

随机块模型中的高效分布式社区检测

• DOI: 10.1109/icdcs.2019.00048
• 发表时间: 2019
• 期刊: 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS
• 作者: Fathi, Reza;Molla, Anisur;Pandurangan, Gopal
• 通讯作者: Pandurangan, Gopal

Byzantine Connectivity Testing in the Congested Clique

拥塞集团中的拜占庭连接测试

• 发表时间: 2022
• 期刊: Leibniz international proceedings in informatics
• 作者: Augustine, John;Molla, Anisur Rahaman;Pandurangan, Gopal;Vasudev, Yadu
• 通讯作者: Vasudev, Yadu

A Scalable Randomized Algorithm for Triangle Enumeration on Graphs Based on SQL Queries

• DOI: 10.1007/978-3-030-59065-9_12
• 发表时间: 2020
• 作者: A. Farouzi;Ladjel Bellatreche;C. Ordonez;Gopal Pandurangan;M. Malki