A Multi-Purpose Toolbox to Quantify, Mitigate and Visualize Risk of Virus Spread

What is graph vulnerability and robustness?

First mentioned as early as the 1970’s, network robustness has a rich and diverse history spanning numerous fields of engineering and science. While the fields of study are diverse, they are linked by a common definition, defined as a

Figure 1. TIGER provides a number of important tools for graph vulnerability and robustness research, including robustness measures, attack strategies, defense techniques and simulation models. Here, a TIGER user is visualizing a computer virus simulation that follows the SIS infection model on the Oregon-1 Autonomous System network. Top: defending only 5 nodes with Netshield, the number of infected entities is reduced to nearly zero. Bottom: without any defense, the virus remains endemic.

What tools are available to study network robustness?

While significant research has been devoted to studying network vulnerability and robustness, no comprehensive open-source toolbox currently exists to assist researchers and practitioners in this important topic. This lack of available tools hinders reproducibility and examination of existing work, development of new research, and dissemination of new ideas.

Robustness Measures

TIGER contains 22 robustness measures, grouped into one of three categories depending on whether the measure utilizes the graph, adjacency, or Laplacian matrix. In Table 1, we highlight each implemented measure, the category it belongs to (graph, adjacency, Laplacian), and its application to network robustness.

Table 1. Comparison of TIGER robustness measures. Measures are grouped based on whether they use the graph, adjacency or Laplacian matrix. For each measure, we describe it’s application to measuring robustness.

Example Robustness Measures

We select 3 robustness measures, one from each of the three categories, to extensively discuss.

Equation 1. Average vertex betweenness measures the average load on vertices in the network. The smaller the average the more robust the network, since load is more evenly distributed across nodes.
Equation 2. Spectral scaling measures the number of bridges and bottlenecks in a graph, the higher the value, the more easily separated the graph (low robustness).
Equation 3. Effective resistance measure how well connected a network is, where a smaller value indicates a more robust network.

Network Attacks

There are two primary ways a network can become damaged — (1) natural failure and (2) targeted attack. Natural failures typically occur when a piece of equipment breaks down from natural causes. In the study of graphs, this would correspond to the removal of a node or edge in the graph. While random network failures regularly occur, they are typically less severe than targeted attacks. In contrast, targeted attacks carefully select nodes and edges in the network for removal in order to maximally disrupt network functionality. As such, we focus the majority of our attention to targeted attacks.

Figure 1. TIGER cascading failure simulation on the US power grid network when 4 power stations are attacked. Time step 1: shows the network under normal conditions. Time step 50: we observe a series of failures originating from the bottom of the network. Time step 70: most of the network has collapsed.

Network Defenses

The same network centrality measures that are effective in attacking a network are important to network defense (e.g., degree, betweenness, PageRank, eigenvector, etc.). In fact, if an attack strategy is known a priori, node monitoring can largely prevent an attack altogether.

Figure 2. Comparing ability of 5 edge defenses to improve KY-2 network robustness after 30 of the most “central” nodes are attacked. Edge addition performs the best, and random edge rewiring performs the worst.

Network Simulation Tools

TIGER contains 4 broad and important types of robustness simulation tools — (1) dissemination of network entities, (2) cascading failures (3) network attacks, and (4) network defense.

Figure 3. TIGER cascading failure simulation on the US power grid network when 4 substations are attacked. Time step 1: shows the network under normal conditions. Time step 50: we observe a series of failures originating from the bottom of the network. Time step 70: most of the network has collapsed.

Want to read more?

For all of the nitty-gritty details of TIGER we release our code on Github and our paper on arXiv.

PhD student @ Georgia Tech. I work at the intersection of applied and theoretical machine learning.