Robustness Analysis of Complex Networks with Applications to Power Grids
My current project involves proposing two mitigation strategies for cascading failures in power grid networks. These strategies are based on the topological and electrical properties of the power grid networks.
The first strategy uses the electrical centrality and node significance measures to decide the location of distributed generation in the transmission system. Using distributed generation allows load satisfaction locally, and also increases reliability of the system in case of failures. Electrical centrality considers the electrical structure of the power grid to indicate the electrically central nodes whereas the node significance selects important nodes based on flow of power in to and out of the nodes. The use of these measures to decide the location of DGs significantly improves the robustness of the power grid, in terms of load and node loss, when one or more links go out of operation. The second strategy utilizes the spectral properties of the power grid for the addition of a long link in the existing grid. The addition of a long link reduces the characteristic path length of the network which directly affects the network robustness. The eigenvalues corresponding to the second, third, and fourth smallest eigenvectors are used to determine the location of the long link such that the characteristic path length is the smallest for the network.
These two strategies have been tested on the 14, 30, 57, 118, and 300 bus IEEE test networks available at http://www.ee.washington.edu/research/pstca/
Publications Google Scholar
Complex networks can represent a large variety of phenomena, from the topology of an overlay network built over the Internet by a Peer-to-Peer application, to the contact networks that characterize the spreading of epidemics due to bioterrorism agents or naturally occurring infectious diseases. This project concerns the study of multiple statistical metrics and performance indices which characterize complex networks.
People: Caterina Scoglio, Mina Youssef, Phillip Schumm, Sakshi Pahwa.
- Robust Topologies (Mina Youssef)
- Clustering Algorithms (Phillip Schumm)
- Cascading Effects (Sakshi Pahwa)
Cascading failures can be seen in a variety of complex networks including the Internet, the Electric Power Grid, Transportation networks, Social, and Economic networks. We modeled the Power Grid as a complex network to study cascading effects. Cascading effects usually occur in power grids when a critical failure at one place spreads to a wider area, such as 2003 Northeast blackout.
We developed a simulator to study the cascading effects on IEEE test networks representing the different parts of the US power grid. A network generator was developed to generate power grid networks with characteristics similar to the original test cases but with different topologies. Topological analysis of the power grid was stressed upon because topology plays an important role in determining the robustness of the network. Two novel mitigation strategies were suggested to prevent cascading failures - Targeted load reduction and Islanding using distributed sources.
Some of the future work includes a thorough fault and power flow analysis with islanding and distributed sources, detailed analysis on some of the network metrics which may play a role in determining the robustness of the power grid networks and including geographical and other practical constraints to the generated networks to make them more realistic. In addition, work has begun on the analysis of the distribution grid, focusing on the topology, variation of loads and size and placement of distributed renewable generation to enable islanding realistically in the distribution network..
- Piet Van Mieghem, Xin Ge, Phillip Schumm, Stojan Trajanovski, and Huijuan Wang, “Spectral graph analysis of modularity and assortativity,” Physical Review E, vol. 82, no. 5, p. 056113, Nov. 2010.
- Sakshi Pahwa, Amelia Hodges, Caterina Scoglio, and Sean Wood "Topological Analysis of the Power Grid and Mitigation Strategies Against Cascading Failures" Proceedings of the 4th Annual International IEEE Systems Conference, 2010, San Diego, USA. PDF Extended Abstract
- Ali Sydney, Caterina Scoglio, Mina Youssef, and Phillip Schumm "Characterizing the Robustness of Complex Networks," International Journal of Internet Technology and Secured Transactions, vol. 2, no. 3, pp. 291 - 320, 2010.
- Supriya Nirkhiwale, Caterina Scoglio, " Optimal mobility pattern in epidemic networks" Proceedings of IEEE Globecom 2009 Wireless Networking Symposium (GC'09-WNS)
- Caterina Scoglio, Robert Kooij, Phillip Schumm, Ali Sydney, and Mina Youssef, "Metrics for robustness in complex networks" Presentation at Delft TU, NAS Group, January 2009, Delft, The Netherlands. PDF preprint
- Robert Kooij, Phillip Schumm, Caterina Scoglio, and Mina Youssef, “A new metric for robustness with respect to virus spread” Proceedings of IFIP-TC Networking 2009 (33% acceptance rate), 2009.
-Caterina Scoglio, Robert Kooij, Phillip Schumm, Ali Sydney, and Mina Youssef "Metrics for Robustness in Complex Networks" Poster presented at "Complex Systems Conference" National Academies Keck Futures Initiative, November 12-15, 2008, Arnold and Mabel Beckman Center, Irvine, CA.PDF preprint
-Ali Sydney, Caterina Scoglio, Phillip Schumm, and Robert Kooij "ELASTICITY: Topological Characterization of Robustness in Complex Networks" Proceedings of IEEE/ACM Bionetics 2008.
- Caterina Scoglio, Todd Easton, Phillip Schumm, and Don Gruenbacher "Controlling Epidemic Outbreaks through Modeling, Analysis, and Optimization of Complex Networks" Presentation at THE NABC FORUM August 2007. PDF preprint
- Phillip Schumm, Caterina Scoglio, Todd Easton, and Don Gruenbacher "Epidemic Spreading on Weighted Contact Networks" Proceedings of IEEE/ACM Bionetics 2007, Budapest, Hungary, Dec. 2007. PDF preprint
- Caterina Scoglio, Todd Easton, Ronette Gehring, and Phillip Schumm "Validated Mathematical Models for Epidemics: Utopia or Reality" Presentation at DMP Seminar Series Fall 2007, November 2007. PDF preprint
GpENI: Great Plains Environment for Network Innovation
The Great Plains Environment for Network Innovation (GpENI) is a regional network between The University of Kansas (KU), Kansas State University (K-State), University of Nebraska – Lincoln (UNL), and University of Missouri – Kansas City within the Great Plains Network, supported with optical switches from Ciena interconnected by Qwest fiber infrastructure, in collaboration with the Kansas Research and Education Network (KanREN) and Missouri Research and Education Network. GpENI is funded in part by the National Science Foundation GENI (Global Environment for Network Innovation) Program as part of Cluster B in Spiral 1.
For more info GpENI wiki
Overlay, Optical, and Virtual Networks
An overlay network is an application-layer logical network created on top of the physical network. It is formed by all or a subset of the underlying physical nodes. The connections between each pair of overlay nodes are provided by overlay links which consist of many underlying physical links. Overlay networks can be used to improve performance and provide quality of service on the IP network, by routing data on the overlay links based on performance measurements.
- M. Youssef, B.Y. Choi, C. Scoglio, E. K. Park "Dynamic Hybrid Topology Design for Integrated Traffic Support in WDM Mesh Networks" International Journal of Computer Networks, Accepted for publication, 2010
- Yunzhao Li, Don Gruenbacher "Analysis of P2P File Sharing Networks Credit System for Fairness Management" IEEE/IFIP NOMS 2010 Mini-conference. OSAKA, JAPAN, April, 2010
- M. Youssef, C. Scoglio "On Graph-based Characteristics of Optimal Overlay Topologies." Computer Network Journal, Elsevier, vol. 53, Issue 7, pp. 913-925, May 2009.
- M. Youssef, B.Y. Choi, C. Scoglio, E. K. Park "Dynamic Hybrid Topology Design for Multicastin Constrained WDM Networks." Proceedings of ICCCN 2008 (26% acceptance rate), St. Thomas, USA, 2008.
- D. Pompili, C. Scoglio, and L. Lopez. "Multicast Algorithms in Service Overlay Networks." Computer Communications Journal vol. 31, pp. 489-505, August 2008.
- B. McBride and C. Scoglio. "Constructing Traffic-Aware Overlay Topologies: A Machine Learning Approach." Proceedings of Workshop on Peer-to-Peer Systems (IPTPS 2008), Tampa Bay, USA, 2008. PDF preprint
- D. Medhi, B.Y. Choi, C. Scoglio, S. Song, S Dispensa "Agent-Based VPN Architecture: Framework and Optimal User Connectivity (Static Case)" in Proceedings of IEEE ADCOM 2007, Guwahati, India, 2007.
- B. McBride and C. Scoglio. "Characterizing Traffic Demand Aware Overlay Routing Network Topologies." Proceedings of IEEE Workshop on High Performance Switching and Routing 2007, New York, USA, 2007. PDF preprint
- M. Youssef, C. Scoglio, and T. Easton. "Optimal Topology Design for Overlay Networks." Proceedings of IFIP Networking 2007 (22% acceptance rate), Atlanta, USA, 2007. PDF preprint
- B. McBride, C. Scoglio, and S. Das. "Distributed Biobjective Ant Colony Algorithm for Low Cost Overlay Network Routing." Proceedings of the 2006 International Conference on Artificial Intelligence. Las Vegas, NV, USA. 2006. PDF preprint
Traffic Modeling and Forecasting
In this project we optimally design dynamic reservation schemes which allocate the bandwidth on-line in real-time to flows or aggregation of flows efficiently on the basis of local measurements. It will be possible to use these schemes in currently deployed networks such as MPLS and overlay networks, which are virtual networks, built using the current Internet infrastructure.
- Caterina Scoglio, Carlo Bruni, Giorgio Koch, Sweta Sutrave "Estimation of Traffic Flows from Aggregate Measurements" Mathematical and Computer Modelling, Accepted for publication, 2010.
- Nikkie Anand, Caterina Scoglio, and Bala Natarajan "Traffic Modeling and Forecasting using Non-Linear Time Series Model - GARCH" Workshop on Advances in Wireless Networking, "WOW-NET 2007" in conjunction with IFIP Networking 2007, Atlanta, USA, May 2007
- Nikkie Anand, Caterina Scoglio, and Bala Natarajan "GARCH - Non-Linear Time Series Model for Traffic Modeling and Prediction" Proceedings of IEEE/IFIP NOMS 08 (short paper), Salvador da Bahia, Brazil, April 2008
- Lutfa Akter, Bala Natarajan, and Caterina Scoglio "Modeling and Forecasting Secondary User Activity in Cognitive Radio Networks" Proceedings of ICCCN 2008 (26% acceptance rate), St. Thomas, USA, 2008.
For this project, Sandia National Labs and Kansas State University have teamed up and have developed a scaled version of the Red Storm (Thor's Hammer) Super Computer. This has given us the ability to work within the realm of Interconnection Networks by providing a testbed for evaluating different routing theories. Along with routing, this opens up a plethora of research areas for our networking group as well.
People: Don Gruenbacher, Chris Lydick
- Chris Lydick. Evaluating Network Performance Tools for Comparing Transport Protocols. July 2007, Sandia National Laboratories. SAND2007-4526. PDF