Event

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: Bill Marmagas

Title: NDSSL Open Science Grid Resources

Abstract: NDSSL has an infrastructure in place for submitting high throughput computing grid jobs to the Open Science Grid national cyberinfrastructure as well as to local campus resources.  This infrastructure has been in place for some time for the development of software interfaces into our various applications.  Access to this infrastructure is also generally available to everyone in NDSSL as another computational resource for performing research.

Speaker 2: Sudip Saha

Title: Reducing the Spectral Radius to Control Epidemic Spread in Networks

Abstract: The largest eigenvalue of the adjacency matrix of a network (referred to as the spectral radius) is an important metric in its own right. Further, for several models of epidemic spread on networks (e.g., the `flu-like' SIS model), it has been shown that an epidemic dies out quickly if the spectral radius of the graph is below a certain threshold that depends on the model parameters. This motivates a strategy to control epidemic spread by reducing the spectral radius of the underlying network.

We develop a suite of provable approximation algorithms for reducing the spectral radius by removing the minimum cost set of edges (modeling quarantining) or nodes (modeling vaccinations), with different time and quality tradeoffs. Our main algorithm, GreedyWalk, is based on the idea of hitting closed walks of a given length, and gives an O(log^2 n)-approximation, where n denotes the number of nodes; it also performs much better in practice compared to all prior heuristics proposed for this problem. In addition, we give a new primal-dual based algorithm with an even better approximation guarantee (O(log n)) albeit with slower running time. We also give lower bounds on the worst-case performance of some of the popular heuristics. Finally we demonstrate the applicability of our algorithms and the properties of our solutions via extensive experiments on multiple synthetic and real networks.