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

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.
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 failureand 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.
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()
- Using a python function takes care of this, since it makes a local copy inside the function, but we could also use
- To simulate random failure, we randomly choose some node names and remove them from the graph.
- We can use
random.sampleto remove more than one node at at time.
- We can use
Steps of the simulation
- Measure size of the network core (largest connected component) as compared to the original network size
- Select M nodes at random and remove them
- Repeat until there are less than M nodes, i.e. can’t remove a set of M nodes anymore
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.