graph-tiger 0.6.0

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:

1. Quantify network vulnerability and robustness,
2. Simulate a variety of network attacks, cascading failures and spread of dissemination of entities
3. Augment a network's structure to resist attacks and recover from failure
4. 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. Scott Freitas, Diyi Yang, Srijan Kumar, Hanghang Tong, and Duen Horng (Polo) Chau. CIKM Resource Track, 2021.

Setup

To quickly get started, install TIGER using pip

$ pip install graph-tiger

Alternatively, you can clone TIGER, create a new Anaconda environment, and install the library by running python setup.py install.

To verify that everything works as expected, you can run the tests cases using python -m pytest tests/.

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{freitas2021evaluating,
    title={Evaluating Graph Vulnerability and Robustness using TIGER},
    author={Freitas, Scott and Yang, Diyi and Kumar, Srijan and Tong, Hanghang and Chau, Duen Horng},
    journal={ACM International Conference on Information and Knowledge Management},
    year={2021}
}

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

Use model='motter_lai' for permanent overload failures or model='crucitti' for dynamic edge-efficiency congestion. Crucitti results are average network efficiencies and are already normalized.

from graph_tiger.cascading import Cascading
from graph_tiger.graphs import graph_loader

graph = graph_loader('BA', n=400, seed=1)

params = {
    'model': 'motter_lai',
    'runs': 1,
    'steps': 100,
    'seed': 1,

    '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: Initial attacked state	Step 6: Beginning of cascading failure	Step 100: Final simulated state

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: :heavy_check_mark:)
  Tong et al. On the Vulnerability of Large Graphs (ICDM 2010)
• Spectral Gap (GPU Accelerated: :heavy_check_mark:)
  Estrada Network robustness to targeted attacks. The interplay of expansibility and degree distribution (European Physical Journal B 2006)
• Natural Connectivity (GPU Accelerated: :heavy_check_mark:)
  Jun et al. Natural connectivity of complex networks (Chinese Physics Letters 2010)
• Approximate Natural Connectivity (GPU Accelerated: :heavy_check_mark:)
• Spectral Scaling (GPU Accelerated: :heavy_check_mark:)
  Estrada Network robustness to targeted attacks. The interplay of expansibility and degree distribution (European Physical Journal B 2006)
• Generalized Robustness Index (GPU Accelerated: :heavy_check_mark:)
  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 Models
  • Motter and Lai Cascade-based attacks on complex networks (Physical Review E 2002)
  • Crucitti, Latora, and Marchiori Model for cascading failures in complex networks (Physical Review E 2004)
  • Wei, Luo, and Zhang Analysis of cascading failure in complex power networks under the load local preferential redistribution rule (Physica A 2012)
  • Local allocation policies: equal/degree-weighted sharing, greedy or proportional spare-capacity sharing, and coordinated maximum-flow allocation. Supply application workloads, capacities, and initial failures; every policy transfers overflow rather than deliberately shedding work. See the allocation tutorial and runnable comparisons.
• Susceptible-Infected-Susceptible (SIS) Model
  Pastor-Satorras and Vespignani Epidemic spreading in scale-free networks (Physical Review Letters 2001)
• Susceptible-Infected-Recovered (SIR) Model
  Kermack et al. A contribution to the mathematical theory of epidemics (Royal Society A 1927)

TIGER implements SIS and SIR as synchronous, discrete-time stochastic processes on a contact network.

License

MIT License