CAREER: A Scalable Optimization-Based Framework for Modeling and Analysis of Cascading Failures

网络中的级联行为是指某些小的冲击或故障被网络大量放大和传播的过程。这些例子包括民用基础设施系统的逐步崩溃、社会学创新的社会蔓延和扩散、生物学的流行病、经济学中的病毒式营销、金融系统的违约级联以及电力网络的停电。对网络中的级联行为进行建模、分析和控制的能力能够检测对冲击的敏感性，有助于制定漏洞缓解策略以提高弹性，并服务于人类健康、基础设施和国防领域的公共利益。由于其令人惊讶的错综复杂的行为和广泛的适用性，这个教师早期职业发展计划(Career)项目专注于组件处于二进制状态的网络，例如0或1，非活动或活动，健康或故障。这里，级联是这样一个过程，在该过程中，数量相对较少的组件的不可逆激活或故障通过网络传播，并最终导致网络的大部分组件的激活或故障。迄今为止，由于这种行为的复杂性，在预防和促进双元级联方面的进展一直受到阻碍。本项目中开发的技术和算法有望为大规模网络中的级联建模、分析和设计提供理论和计算工具。该项目不仅将促进网络系统的基础科学，还将提高我们的准备，以避免关键网络出现故障，如健康、交通、电力、通信和金融系统。该项目也有强大的教育和推广计划，包括K-12、本科生和研究生以及当地社区。为了推进新兴网络中级联行为的建模、分析和设计的可扩展技术，Carrer项目考虑了最优级联播种问题：对于给定的网络，找出其在时间零的故障最大化故障放大比的组件集--最终故障和初始故障之间的比率。两类具体的网络被用作最优级联播种的激励应用：运输网络和阈值网络。阈值网络是这样一种网络，在这种网络中，如果某个组件的邻居中至少有一部分发生故障，则该组件发生故障。基础研究的变革性思想是利用分段线性函数来逼近级联网络的复杂时间动力学。这些非线性动力学的特殊松弛版本被嵌入到具有级联促进目标的高维线性规划中。通过使用稀疏优化和压缩传感中的正则化技术，可以克服寻找最关键初始故障的组合方面的问题。所开发的方法适合于大规模网络，并有可能增强用于布尔和非线性系统的一般类别的分析和设计的系统论工具集。该项目的更广泛影响包括预防疫情爆发和疾病传播，在社会政治网络中引发积极的社会变革和集体行动，以及检测和缓解新兴智能电网的脆弱性。教育工作的重点是使用参与式学习策略来填补从K-12到研究生的教育渠道，并以网络和优化为中心。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

The phenomena of cascading behavior in a network is the process in which certain small shocks or malfunctions are massively amplified and propagated by the network. Examples include progressive collapse in civil infrastructure systems, social contagion and diffusion of innovations in sociology, epidemics in biology, viral marketing in economics, default cascades in financial systems, and blackouts in power networks. The ability to model, analyze, and control the cascade behavior in networks enables detection of sensitivities to shocks, helps develop vulnerability mitigation strategies for increased resilience, and serves the public interest in the areas of human health, infrastructure, and national defense. Due to their surprisingly intricate behavior and wide applicability, this Faculty Early Career Development Program (CAREER) project focuses on networks in which components take binary states, such as zero or one, inactive or active, healthy or failed. Here, a cascade is a process in which the irreversible activation or failure of a relatively small number of components spreads through the network and ultimately results in the activation or failure of a substantial portion of the network's components. To date, progress in the prevention and promotion of binary cascades has been hampered by the complexity of such behavior. The techniques and algorithms developed in this project are expected to provide theoretical and computational tools for the modeling, analysis, and design of cascades in large-scale networks. This project will not only promote fundamental science of network systems but also improve our preparedness to avoid failures in critical networks such as, health, traffic, power, communication, and financial systems. The project also has strong education and outreach plan that includes K-12, undergraduate and graduate students, and local community. To advance scalable techniques for the modeling, analysis, and design of cascading behavior in emerging networks, this CARRER project considers the optimal cascade seeding problem: For a given network find the set of components whose failure at time zero maximizes the failure amplification ratio -- the ratio between the number of final and initial failures. Two concrete classes of networks are employed as motivational applications of optimal cascade seeding: transportation networks and threshold networks. Threshold networks are ones in which a component fails if at least a certain fraction of its neighbors have failed. The transformative idea of the fundamental research is to utilize piecewise-linear functions to approximate the complex temporal dynamics of cascading networks. A special relaxed version of these nonlinear dynamics is embedded in a high-dimensional linear program with a cascade-promoting objective. Combinatorial aspects of finding the most critical initial failures are overcome through the use of regularization techniques from sparse optimization and compressed sensing. The developed approach scales gracefully to large-scale networks and has the potential to enhance the systems-theoretic toolset for analysis and design in general classes of Boolean and nonlinear systems. The broader impacts of this project include prevention of epidemic outbreaks and spread of disease, triggering positive social change and collective action in sociopolitical networks, and vulnerability detection and mitigation in the emerging smart grid. The education effort is focused on filling the educational pipeline from K-12 to graduate students using engaged learning strategies and is centered around networks and optimization.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.