**TIGER** is a Python toolbox to conduct graph vulnerability and robustness research. TIGER contains numerous state-of-the-art methods to help users conduct graph vulnerability and robustness analysis on graph structured data. Specifically, TIGER helps users:

**Quantify**network*vulnerability*and*robustness*,**Simulate**a variety of network attacks, cascading failures and spread of dissemination of entities**Augment**a network's structure to resist*attacks*and recover from*failure***Regulate**the dissemination of entities on a network (e.g., viruses, propaganda).

For additional information, take a look at the **Documentation** and our paper:

**Evaluating Graph Vulnerability and Robustness using TIGER**. **Freitas, Scott**, and Chau, Duen Horng. *arXiv, 2020.*

### Setup

To quickly get started, install TIGER using pip

`$ pip install graph-tiger`

Alternatively, you can clone TIGER and create a new Anaconda environment using the YAML file.

### Tutorials

We provide 5 in-depth tutorials in the **Documentation**, each covers a core aspect of TIGER's functionality.

**Tutorial 1: Measuring Graph Vulnerability and Robustness**

**Tutorial 2: Attacking a Network**

**Tutorial 3: Defending A Network**

**Tutorial 4: Simulating Cascading Failures on Networks**

**Tutorial 5: Simulating Entity Dissemination on Networks**

### Citing

If you find *TIGER* useful in your research, please consider citing the following paper:

```
@article{freitas2020evaluating,
title={Evaluating Graph Vulnerability and Robustness using TIGER},
author={Freitas, Scott and Chau, Duen Horng},
journal={arXiv preprint arXiv:2006.05648},
year={2020}
}
```

### Quick Examples

#### EX 1. Calculate graph robustness (e.g., spectral radius, effective resistance)

```
from graph_tiger.measures import run_measure
from graph_tiger.graphs import graph_loader
graph = graph_loader(graph_type='BA', n=1000, seed=1)
spectral_radius = run_measure(graph, measure='spectral_radius')
print("Spectral radius:", spectral_radius)
effective_resistance = run_measure(graph, measure='effective_resistance')
print("Effective resistance:", effective_resistance)
```

### EX 2. Run a cascading failure simulation on a Barabasi Albert graph

```
from graph_tiger.cascading import Cascading
from graph_tiger.graphs import graph_loader
graph = graph_loader('BA', n=400, seed=1)
params = {
'runs': 1,
'steps': 100,
'seed': 1,
'l': 0.8,
'r': 0.2,
'c': int(0.1 * len(graph)),
'k_a': 30,
'attack': 'rb_node',
'attack_approx': int(0.1 * len(graph)),
'k_d': 0,
'defense': None,
'robust_measure': 'largest_connected_component',
'plot_transition': True, # False turns off key simulation image "snapshots"
'gif_animation': False, # True creaets a video of the simulation (MP4 file)
'gif_snaps': False, # True saves each frame of the simulation as an image
'edge_style': 'bundled',
'node_style': 'force_atlas',
'fa_iter': 2000,
}
cascading = Cascading(graph, **params)
results = cascading.run_simulation()
cascading.plot_results(results)
```

Step 0: Network pre-attack | Step 6: Beginning of cascading failure | Step 99: Collapse of network |
---|---|---|

### EX 3. Run an SIS virus simulation on a Barabasi Albert graph

```
from graph_tiger.diffusion import Diffusion
from graph_tiger.graphs import graph_loader
graph = graph_loader('BA', n=400, seed=1)
sis_params = {
'model': 'SIS',
'b': 0.001,
'd': 0.01,
'c': 1,
'runs': 1,
'steps': 5000,
'seed': 1,
'diffusion': 'min',
'method': 'ns_node',
'k': 5,
'plot_transition': True,
'gif_animation': False,
'edge_style': 'bundled',
'node_style': 'force_atlas',
'fa_iter': 2000
}
diffusion = Diffusion(graph, **sis_params)
results = diffusion.run_simulation()
diffusion.plot_results(results)
```

Step 0: Virus infected network | Step 80: Partially infected network | Step 4999: Virus contained |
---|---|---|

### Techniques Implemented

**Vulnerability and Robustness Measures:**

**Vertex Connectivity**

Ellens*et al.*Graph measures and network robustness (arXiv 2013)**Edge Connectivity**

Ellens*et al.*Graph measures and network robustness (arXiv 2013)**Diameter**

Ellens*et al.*Graph measures and network robustness (arXiv 2013)**Average Distance**

Ellens*et al.*Graph measures and network robustness (arXiv 2013)**Average Inverse Distance (Efficiency)**

Ellens*et al.*Graph measures and network robustness (arXiv 2013)**Average Vertex Betweenness**

Ellens*et al.*Graph measures and network robustness (arXiv 2013)**Approximate Average Vertex Betweenness**

Brandes*et al.*Centrality Estimation in Large Networks (International Journal of Bifurcation and Chaos 2007)**Average Edge Betweenness**

Ellens*et al.*Graph measures and network robustness (arXiv 2013)**Approximate Average Edge Betweenness**

Brandes*et al.*Centrality Estimation in Large Networks (International Journal of Bifurcation and Chaos 2007)**Average Clustering Coefficient****Largest Connected Component****Spectral Radius**(**GPU Accelerated:**)✔️

Tong*et al.*On the Vulnerability of Large Graphs (ICDM 2010)**Spectral Gap**(**GPU Accelerated:**)✔️

Estrada Network robustness to targeted attacks. The interplay of expansibility and degree distribution (European Physical Journal B 2006)**Natural Connectivity**(**GPU Accelerated:**)✔️

Jun*et al.*Natural connectivity of complex networks (Chinese Physics Letters 2010)**Approximate Natural Connectivity**(**GPU Accelerated:**)✔️ **Spectral Scaling**(**GPU Accelerated:**)✔️

Estrada Network robustness to targeted attacks. The interplay of expansibility and degree distribution (European Physical Journal B 2006)**Generalized Robustness Index**(**GPU Accelerated:**)✔️

Malliaros*et al.*Fast Robustness Estimation in Large Social Graphs: Communities and Anomaly Detection (SDM 2012)**Algebraic Connectivity**

Chan*et al.*Optimizing network robustness by edge rewiring: a general framework (DMKD 2016)**Number of Spanning Trees**

Baras*et al.*Efficient and robust communication topologies for distributed decision making in networked systems (CDC 2009)**Approximate Number of Spanning Trees****Effective Resistance**

Klein Resistance distance (Journal of Mathematical Chemistry 1993)**Approximate Effective Resistance**

**Attack Strategies:**

**Remove Node: Netshield**

Tong*et al.*On the Vulnerability of Large Graphs (ICDM 2010)**Remove Node: PageRank**

Page*et al.*The PageRank Citation Ranking: Bringing Order to the Web**Remove Node: Eigenvector Centrality**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Remove Node: Initial Degree (ID)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Remove Node: Recalculated Degree (RD)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Remove Node: Initial Betweenness (IB)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Remove Node: Recalculated Betweenness (RB)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Remove Node: Random**

Tong*et al.*Gelling, and melting, large graphs by edge manipulation (CIKM 2012)**Remove Edge: Netshield Line****Remove Edge: PageRank Line**

Tong*et al.*Gelling, and melting, large graphs by edge manipulation (CIKM 2012)**Remove Edge: Eigenvector Centrality Line**

Tong*et al.*Gelling, and melting, large graphs by edge manipulation (CIKM 2012)**Remove Edge: Degree Line**

Tong*et al.*Gelling, and melting, large graphs by edge manipulation (CIKM 2012)**Remove Edge: Random**

Tong*et al.*Gelling, and melting, large graphs by edge manipulation (CIKM 2012)**Remove Edge: Initial Betweenness (IB)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Remove Edge: Recalculated Betweenness (RB)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Remove Edge: Initial Degree (ID) Removal**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Remove Edge: Recalculated Degree (RD) Removal**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)

**Defense Strategies:**

**Vaccinate Node: Netshield**

Tong*et al.*On the Vulnerability of Large Graphs (ICDM 2010)**Vaccinate Node: PageRank**

Page*et al.*The PageRank Citation Ranking: Bringing Order to the Web**Vaccinate Node: Eigenvector Centrality**

Tong*et al.*On the Vulnerability of Large Graphs (ICDM 2010)**Vaccinate Node: Initial Degree (ID)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Vaccinate Node: Recalculated Degree (RD)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Vaccinate Node: Initial Betweenness (IB)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Vaccinate Node: Recalculated Betweenness (RB)**

Holme*et al.*Attack vulnerability of complex networks (Physical Review E 2002)**Vaccinate Node: Random****Add Edge: PageRank**

Tong*et al.*Gelling, and melting, large graphs by edge manipulation (CIKM 2012)**Add Edge: Eigenvector Centrality**

Tong*et al.*Gelling, and melting, large graphs by edge manipulation (CIKM 2012)**Add Edge: Degree Centrality**

Tong*et al.*Gelling, and melting, large graphs by edge manipulation (CIKM 2012)**Add Edge: Random**

Beygelzimer*et al.*Improving network robustness by edge modification (Physica A 2005)**Add Edge: Preferential**

Beygelzimer*et al.*Improving network robustness by edge modification (Physica A 2005)**Rewire Edge: Random**

Beygelzimer*et al.*Improving network robustness by edge modification (Physica A 2005)**Rewire Edge: Random Neighbor**

Beygelzimer*et al.*Improving network robustness by edge modification (Physica A 2005)**Rewire Edge: Preferential**

Beygelzimer*et al.*Improving network robustness by edge modification (Physica A 2005)**Rewire Edge: Preferential Random**

Beygelzimer*et al.*Improving network robustness by edge modification (Physica A 2005)

**Simulation Frameworks:**

**Cascading Failure Model**

Crucitti*et al.*A model for cascading failures in complex networks (Physical Review E 2004)**Susceptible-Infected-Susceptible (SIS) Model**

Kermack*et al.*A contribution to the mathematical theory of epidemics (Royal Society A 1927)**Susceptible-Infected-Recovered (SIR) Model**

Kermack*et al.*A contribution to the mathematical theory of epidemics (Royal Society A 1927)