Network Robustness

Introduction

  • A system is robust if the failure of some of its components doesn’t seriously effect its function (i.e. it fails safe).

  • In general, robustness depends on which components fail and on the extent of the damage.

  • Studying robustness: (1) Artificially remove a node to simulate a failure event, (2) analyze how the structure and function of the network changes without that node and all of its links.

  • We can use graph-connectivity as a proxy for network failure: i.e. if the network remains connected, we can assume that it will likely keep working

  • Eventually, if all links are removed, the network will simply be a dis-integrated network of singletons

Source1

Node removal

  • One form of “attack” on a network is to randomly target and delete nodes

  • Here we show sequence of node deletions and their incident links.

  • After just three nodes are deleted (in frame-d), the network breaks into three components disconnected from each other.

Source1

Analysis:

  • Another way to think about the relative “importance” of nodes in a network is to measure how much it would damage the network structure if particular nodes were to be removed.
  • In real life, node removal might be a person moving away and out of a social network, someone changing jobs and being removed from an email network, internet routers being attacked/overloaded and going down, etc.
  • We consider two types of network damage:
    • Random failure and targeted attack. In a random failure, nodes are chosen randomly for removal.
    • Targeted attack, we will remove nodes based on some criterion, for example, removing nodes in decreasing order of their degree centrality.

Connected components

In order to measure “damage,” we will measure the size of the network’s largest connected component, sometimes called core. First we observe that nx.connected_components is a generator that provides the connected components one at a time, starting with the largest.

Code source1

Simulation: Random attack

  • Since we are deleting nodes, we should make a copy of the network so that we can easily get back to the original graph
    • Using a python function takes care of this, since it makes a local copy inside the function, but we could also use G_new = G.copy()
  • To simulate random failure, we randomly choose some node names and remove them from the graph.
    • We can use random.sample to remove more than one node at at time.

Steps of the simulation

  1. Measure size of the network core (largest connected component) as compared to the original network size
  2. Select M nodes at random and remove them
  3. Repeat until there are less than M nodes, i.e. can’t remove a set of M nodes anymore
Code source1

Results

  • Many real networks, which have central hubs, are robust to random failures, but quite vulnerable to targeted attacks.

Aside: Dropout

  • The process we just described is similar to Dropout

Image source: https://wiki.tum.de/display/lfdv/Dropout

References

Disclaimer: This document is not an original work. It contains content from many sources and is for educational purposes only.

1.
Menczer, F., Fortunato, S. & Davis, C. A. A first course in network science. (Cambridge University Press, 2020).