| NSF Org: |
IIS Division of Information & Intelligent Systems |
| Recipient: |
|
| Initial Amendment Date: | August 30, 2016 |
| Latest Amendment Date: | June 22, 2019 |
| Award Number: | 1633720 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Sylvia Spengler
sspengle@nsf.gov (703)292-7347 IIS Division of Information & Intelligent Systems CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2016 |
| End Date: | August 31, 2022 (Estimated) |
| Total Intended Award Amount: | $549,877.00 |
| Total Awarded Amount to Date: | $565,877.00 |
| Funds Obligated to Date: |
FY 2019 = $16,000.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
4300 MARTIN LUTHER KING BLVD HOUSTON TX US 77204-3067 (713)743-5773 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
TX US 77204-2015 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Big Data Science &Engineering |
| Primary Program Source: |
01001920DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
A number of phenomena of societal importance, such as the spread of diseases and
contagion 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 problems
are 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 will
result 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 different
kinds 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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The results of this project has significantly advanced our ability to design provably good distributed algorithms for processing large-scale data, especially graph data. It has also led to applying these algorithms to networked epidemiology which can help in understanding and containing the spread of diseases.
Intellectual Merit:
The project has resulted in the design and analysis of new distributed algorithms for various fundamental algorithmic problems in the k-machine model, a model for large-scale distributed computation. These problems include PageRank, triangle enumeration, community detection, K-nearest neighbors, minimum spanning tree, and several other graph problems. These problems have wide applicability and are used as primitives in several applications including epidemiology.
A major contribution of the project is developing a general technique to show lower bounds for large-scale distributed graph algorithms. These lower bounds help in quantifying the best possible algorithms that one can achieve for distributively solving large-scale problems.
The project also developed efficient distributed algorithms for the problem of influence maximation in a social network, a well-studied problem with applications to many areas such as viral marketing, epidemiology among others.
The project also initiates the study distributed fault-tolerant graph algorithms. It develops a distributed algorithm for the fundamental graph connectivity problem that can output meaningful results even under the presence of malicious processors.
The project makes an important contribution to controlling the Covid-19 pandemic, by developing scheduling mechanisms that trade-off between containing the spread of COVID-19 and performing in-person activity in organizations.
Broader Impacts:
This project has resulted in the discovery of (essentially) optimum algorithms for two fundamental graph problems, namely PageRank and triangle enumeration in the k-machine model, a message passing model that models large-scale distributed computing. The project has also implemented the triangle enumeration algorithm in a SQL based database system. The project has also developed efficient distributed algorithms for various fundamental graph problems in the k-machine model.
The project has also resulted in the development of new techniques for showing lower bounds for distributed graph algorithms in a message passing model, which is of fundamental interest. Other works that have appeared subsequently have been influenced by this work.
The development of efficient algorithms for fundamental graph problems will have a direct impact in designing efficient distributed algorithms for large-scale graphs which is important to Big Graph Data computing.
The project also initiated the study of distributed graph algorithms that are tolerant to even malicous faults of processors executing the algorithm.
Our work on scheduling mechanisms for Covid-19 can have an impact on strategies to operate organizations like hospitals, schools, universities and businesses safely. It develops and analyzes mechanisms called group scheduling that trade off in-person activity for controlling the spread of Covid-19 and vice versa. This can be useful for public health experts.
The results of this project have been published in top peer-reviewed conferences and journals in computer science.
The project has also provided opportunities to train graduate and undergraduate students and post doctoral fellows in Big Data computing, distributed algorithms, and analyzing models and algorithms in epidemiology.
The theory and algorithms developed as part of this project, have been incorporated in courses taught by the PI and his collaborators. In particular, it is part of the Distributed Algorithms course taught by the PI at the University of Houston and IIT Madras. The PI has given tutorials on the topic in universities and conferences.
The project has contributed to opportunities for research and mentoring of seven Ph.D. students --- Soumyottam Chatterjee, Reza Fathi, Nguyen Dinh Pham. Khalid Hourani, Aayush Gupta, Duy Pham, and Krishnamoorthy Iyer (all at the University of Houston, a minority serving Tier 1 public research institution) and four postdoctoral scholars --- Michele Scquizzato, Robert Gmyr, William Moses and Fabien Dufoluon (all at the University of Houston).
The project has also contributed to collaborations with Profs. John Augustine and Yadu Vasudev (IIT Madras), Prof. Kishore Kothapalli (IIIT, Hyderabad), Prof. Anisur Molla (Indian Statistical Institute, Kolkatta), Prof. Sriram Pemmaraju (University of Iowa), and Prof. Peter Robinson (Augusta University),
Prof. Shay Kutten (Technion), and Prof. David Peleg (Weizmann). These collaborations have resulted in more broadly disseminating the research topics among the researchers in the respective universities.
Last Modified: 12/31/2022
Modified by: Gopal Pandurangan
Please report errors in award information by writing to: awardsearch@nsf.gov.
