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

网络中的级联现象是指某些小的冲击或故障被网络大量放大和传播的过程。例子包括民用基础设施系统的逐步崩溃、社会学中的社会传染和创新扩散、生物学中的流行病、经济学中的病毒式营销、金融系统中的违约级联以及电力网络中的停电。建模、分析和控制网络中级联行为的能力能够检测对冲击的敏感性，有助于制定脆弱性缓解策略以提高弹性，并服务于人类健康、基础设施和国防领域的公共利益。由于其令人惊讶的复杂行为和广泛的适用性，这个教师早期职业发展计划（CAREER）项目的重点是网络中的组件采取二进制状态，如零或一，不活跃或活跃，健康或失败。这里，级联是一个过程，其中相对少量的组件的不可逆激活或故障通过网络传播，并最终导致网络组件的大部分激活或故障。迄今为止，防止和促进二元级联的进展一直受到这种行为的复杂性的阻碍。本计画所发展之技术与演算法，可望提供理论与计算工具，供大型网路中之叶栅建模、分析与设计之用。该项目不仅将促进网络系统的基础科学，还将提高我们的准备工作，以避免关键网络（如健康，交通，电力，通信和金融系统）的故障。该项目还拥有强大的教育和推广计划，包括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.