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

Syracuse University, Syracuse NY

Investigators

Abstract

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.