| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | August 26, 2015 |
| Latest Amendment Date: | August 26, 2015 |
| Award Number: | 1555780 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Nina Amla
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2015 |
| End Date: | August 31, 2018 (Estimated) |
| Total Intended Award Amount: | $124,701.00 |
| Total Awarded Amount to Date: | $124,701.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
1350 BEARDSHEAR HALL AMES IA US 50011-2103 (515)294-5225 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
226 Atanasoff Hall Ames IA US 50011-1301 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Software & Hardware Foundation |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
In the age of globalization and informatization, the study of information propagation in the network of connected entities plays an important role in understanding and analyzing security and safety concerns. Entities in the network can be people, groups or computing devices, while the network is the relationship describing how one entity can influence or can be influenced by others. In epidemiology, the network of entities may correspond to the population groups and their spatial/proximity relationships. In social or market sciences, the network captures the exchange of ideas and information (or misinformation among peers, or leaders and followers), and the studies focus on identifying the critical groups of entities that are sufficient to influence the entire network. In all the above applications, the central theme is to analyze the spread of information/infection and use external influences/stimuli to either contain its spread within desired level or maximize its impact. Such external influences/stimuli that impact the spread can be referred to as vaccines. This project investigates ways to identify the way to deploy the vaccines, and the order in which to do so to realize the desired objective.
At its core, the project develops and applies formal method techniques, particularly model checking, to capture the dynamics of information spread in a network and analyze them. The long term objective is to develop a robust and application-domain agnostic framework which will allow succinct and precise representation of network and spread-model of information as a finite-state graph, and desired objectives as temporal properties over the graph. The project establishes a natural connection between the application domains and solution methodology, which furthers research in formal methods, particularly in terms of developing new types of specification language and efficient techniques to analyze and explore models expressed in this language. The cross-disciplinary nature of the educational and research activities, and the dissemination of research results will help to open new avenues of research not only in formal methods but also in information propagation and analysis. The project involves undergraduate and under-represented students.
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 study of propagation of information in a network of connected
entities is an important area of research in multiple domains ranging
from epidemiology, social and market sciences to intrusion detection
in computer science. The common questions in these domains are to
either contain the spread of information within desired level or
maximize its impact. Addressing these questions is key to broad
societal issues e.g., public health policies for vaccination,
strategic placement of health care facilities in vulnerable
communities, maximizing the impact of public education, improving
strategic marketing through information dissemination.
[Knowledge Gaps Addressed]. Three specific problems have been
addressed that are central to addressing the above questions:
maximizing the spread of information among a targeted group while
avoiding another; identifying critical set of entities, which when
protected ensure the maximal disruption of spread of unwanted
information; developing strategies for allocating resources to control
the spread of unwanted information.
[Research Findings]. We present formal description of the problems,
and prove that the problems are computationally hard, and traditional
techniques used in the context of information diffusion in a network
are not directly applicable for addressing them. We develop new
algorithms, heuristics and strategies, and show their effective
application in a number of real-life networks (available at Stanford
Large Network Dataset Collection).
[Benefits to Science of Computing]. The research results present a
road-map for formalizing the key questions related to information
diffusion, and shows how computational techniques can be deployed to
effectively and efficiently answer some of these questions for large
complex networks typical in real-world settings.
[Contributions to Learning and Work-Force Development]. Four graduate
students were directly involved in the proposed research. One of them
is continuing as a doctoral student, while others have joined the
industry work-force.
Last Modified: 12/01/2018
Modified by: Samik Basu
Please report errors in award information by writing to: awardsearch@nsf.gov.
