CAREER: Network Robustification: Theories, Algorithms and Applications

在各种高影响应用领域中出现的网络的一个共同且基本的属性是健壮性--量化网络在存在外部干扰时继续运行的能力，即在存在随机故障或故意攻击的情况下剩余网络的连接情况如何。例如，2012年飓风桑迪导致纽约市大都市区大范围停电，造成巨大经济损失，估计达500亿美元，并造成严重的社会后果。此外，最近的一项研究表明，即使是对美国电网的小规模攻击也可能导致全国范围内的停电。网络健壮性是识别和最大限度地减少此类关键基础设施网络漏洞的关键。例如，在智能交通系统中，网络健壮性可以帮助缓解交通拥堵。现有的绝大多数关于网络健壮性的工作基本上都是观察性的。虽然在观察网络健壮性方面已经取得了显著的进展，但同样重要的问题也没有得到充分的研究，那就是如何设计有效的干预策略来提高网络的健壮性。在现有观测工作的基础上，该项目旨在进一步研究网络健壮性的干预方法。这个项目的总体目标是开发基本的理论和算法，以产生一个健壮的网络，称为网络健壮性问题。这将通过三项研究努力来实现。第一个推力旨在发展网络鲁棒性问题的基本理论，包括它的统一性、它的难易程度和它的逼近性。第二个推力旨在开发一套有效的、可扩展的和自适应的算法来以期望的方式优化网络的健壮性。第三个推力在现实世界的应用环境中验证和验证了所提出的技术，包括智能交通系统和在线社会协作。该项目完成后，将在两个方向上促进网络健壮性的发展。首先，阐述了网络鲁棒性问题的几个关键步骤，包括网络鲁棒性问题的统一性、难易程度和逼近性。其次，它将导致新的算法和工具具有更好的有效性、可扩展性、适用性和适应性。该研究计划与其教育计划紧密结合，以促进亚利桑那州立大学的数据挖掘，培养相关领域的研究生，并为本科生以及K-12学生提供研究机会。研究成果将纳入国际和平研究所教授的数据科学课程，并将通过出版物、会议教程、讲习班以及可能的技术转让进一步传播。

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.