CAREER: Network Robustification: Theories, Algorithms and Applications

Arizona State University, Scottsdale AZ

Investigators

Abstract

A common and fundamental property of the networks arising in a variety of high-impact application domains is robustness - quantifying the network's ability to continue to function in the presence of an external disturbance, i.e., how well is the remaining network connected in the presence of either random failures or intentional attacks. For instance, the widespread power outages in the New York City metropolitan area due to Hurricane Sandy in 2012 caused huge economic loss estimated to be $50B along with severe societal consequences. Moreover, a recent study suggests that even a small-scale attack on the U.S. power grid could cause a nationwide blackout. Network robustness is the key to identifying and minimizing the vulnerability of such critical infrastructure networks. For example, in intelligent transportation systems, network robustness can help alleviate traffic congestion. The vast majority of the existing work on network robustness is essentially observational. Although remarkable progress has been made in terms of observing network robustness, an equally important problem, which has not been sufficiently studied, is how to design effective strategies to intervene to improve the network's robustness desired ways. Building upon the existing observational work, this project aims to further investigate an intervention approach to network robustness. The overall goal of this project is to develop basic theories and algorithms that result in a robust network, referred to as the network robustification problem. This will be pursued through three research thrusts. The first thrust aims to develop basic theories for the network robustification problem, including its unification, its hardness, and its approximability. The second thrust aims to develop a suite of effective, scalable and adaptive algorithms to optimize the network robustness in a desired way. The third thrust validates and verifies the proposed techniques in the context of real-world applications, including an intelligent transportation system and an online social collaboration. Upon completion, this project will advance the state-of-the-art of network robustness in two directions. First, it will lay down a few critical steps to pave the theoretic foundations of the network robustification problem, including its unification, its hardness and its approximability. Second, it will lead to new algorithms and tools with better effectiveness, scalability, applicability and adaptability. The research plan is closely integrated with its education plan to promote data mining at Arizona State University, to train graduate students in the related fields, and to provide research opportunities for undergraduate students as well as K-12 students. The research outputs will be integrated into the data science courses that the PI teaches, and will be further disseminated by publications, conference tutorials, workshops, as well as potential technology transfer.