CAREER: Network Robustification: Theories, Algorithms and Applications

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

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.