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.
To quickly get started, install TIGER using pip
$ pip install graph-tigerAlternatively, you can clone TIGER and create a new Anaconda environment using the YAML file.
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
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}
}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)
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 |
|---|---|---|
 |
 |
 |
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 |
|---|---|---|
 |
 |
 |
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)