How to Search for Trouble ... and Find It!
Margaret (Maggie) J. Eppstein
Vermont Complex Systems Center
Dept. of Computer Science, University of Vermont
November 14, 2011
12:50 - 1:40 pm
Nonlinear interactions between certain subsets of components in complex interconnected systems can cause qualitatively dramatic changes in emergent system properties. For example, certain genes and environmental triggers can interact to cause disease; some subsets of molecules will catalyze their own interactions and may be key to the emergence of Life; and some initially localized market interactions can ripple into collapse of entire economies.
However, given the vast numbers of components and interactions in real-world systems, how does one go about determining which small subsets of components are likely to trigger large discrete changes in system properties?
In this talk, I frame this type of combinatorial search problem as nonlinear feature selection and describe an efficient stochastic algorithm that can be used to tackle this problem in a variety of application domains. As a specific case study, I focus on recent research in which we seek to find combinations of outages that lead to large cascading failures in the electrical grid, so that we can mine the results for predictive patterns. Our results show scale-free distributions in the likelihood that network outages interact in deleterious combinations, indicating that a relatively small number of electrical components contribute disproportionately to cascading failure risk. Standard grid performance indices and common metrics of network topology are shown to be insufficient for predicting which outages are likely to result in cascading failure, underscoring the value in using our approach to identify system vulnerabilities.
Professor Eppstein received her B.S. in Zoology from Michigan State University in 1978, her M.S. in Computer Science from the University of Vermont in 1983, and her Ph.D. in Environmental Engineering from the University of Vermont in 1997. She has held several positions in the Department of Computer Science at the University of Vermont, including as a lecturer from 1983-2001, as a research assistant professor from 1997-2002, as assistant professor from 2002 2008, as associate professor since 2008, and as founding Director of the University of Vermont Complex Systems Center from 2006-2010. Her research interests involve forward and inverse modeling and analysis of complex systems in a wide variety of application domains, including biological, environmental, technological, and social systems. Her work has been funded by NSF, NIH, USGS, DOE, DOD, and DOT.