Location: NDSSL Conference Room 2018, RB XV, Corporate Research Center

Graduate Students and NDSSL Faculty conduct weekly seminars on a variety of topics related to the research being conducted in the lab.

Speaker 1: Mina Youssef

Title: Dynamical response of the power grid due to catastrophic events

Abstract: We study the consequences of an improvised nuclear detonation (IND) to the sub-transmission and distribution systems in Washington D.C. in the Eastern Interconnection (EI). We briefly discuss the geographical location of the blast and the interconnection of the power utility serving this area, with the neighboring power utilities. Analysis of the grid with respect to steady state stability as well as transient stability is performed to understand the impact of loss in load as a result of the blast. The steady state analysis alone does not offer a complete understanding of the loss of the neighboring substations. The transient analysis finds that for the simulated event, the system stabilizes after the occurrence of the event. By analyzing the power flow redistribution, we found that there are three subgraphs that experience a power surge after the blast takes place.

Speaker 2: Jose Cadena

Title: Finding Anomalies in Temporal Networks

Abstract: Anomaly detection is a fundamental problem in dynamic networks. We study an approach for identifying anomalous subgraphs based on the Heaviest Dynamic Subgraph (HDS) problem. The HDS in a time-evolving edge-weighted graph consists of a pair containing a subgraph and sub-interval whose sum of edge weights is maximized. The HDS problem is equivalent to the Prize Collecting Steiner Tree (PCST) problem with the Net-Worth objective— this is a very challenging problem, in general, and numerous heuristics have been proposed.
We develop a new approach for the HDS problem, which consists of: (1) a new temporal filtering method that selects a sub-quadratic set of time intervals, and provably preserves the maximum HDS solution, within a factor of 2, (2) an optimal fixed parameter algorithm for maximizing the Net-Worth objective, in terms of the number of nodes in the solution, and (3) a faster heuristic for the PCST problem, that adapts the algorithm by Cole et al., 2001, for the primal-dual approach of Goemans and Williamson (GW) for PCST problem. Our algorithms give a provably improved solution to the HDS problem, both in terms of running time and quality of the solution, and give an interesting tradeoff between time and quality.