Node deletion

Node deletion is the procedure of removing a node from a network, where the node is either chosen randomly or directly. Node deletion is used to test the robustness and the attack tolerance of networks. Understanding how a network changes in response to node deletion is critical in many empirical networks. Application varies across many fields, including the breakdown of the World Wide Web via router removal, elimination of epidemics or fighting against criminal organizations.

Removing a node or multiple nodes randomly from a network means that the elimination of a set of nodes happen with a certain probability. The probability of deleting a node can follow any distributions, the most common is to assume a uniform distribution. The effect of the node deletion is highly dependent on the topology of the network, so it affects every empirical networks differently.

The effect on the network connectedness is measured with the diameter of the network. When we remove an f fraction of nodes, the diameter of the network increases monotonically with f. This is because each node has approximately the same degree thus they contribute to the interconnectedness by relatively the same amount.

The effect on a scale-free network is very different from what is experienced with random networks. As f increases, the diameter remains unchanged even on a 5% error level. This robustness comes from the presence of hubs in the network, as long as the hubs are not malfunctioning, the internonnectedness of the network is untouched.

When network deletion is combined with other processes, the topology of the network can change drastically. To illustrate this, consider the BA model. In each step add a new node with m links to the network, and also remove a node with probability r. This leads to different networks depending on m and r.

When the objective is to break down a network it makes much more sense to target certain nodes instead of removing them in a random fashion. This is the case for example when someone is fighting against a bacterium, or wants to eliminate a criminal network. Targeted removel can happen according to many strategies, the most effective ones are the targeting of the highest degree nodes, and the targeting of the nodes with the highest betweenness centrality. The strategies effectivity can be either measured by how the diameter of the network changes, or how the largest components size changes over periods of removal.

When removing nodes starting from the most connected one (the node with the highest degree) the diameter of the Erdős-Rényi model reacts similarly to a random deletion of nodes. This is because the model is rather homogenous, the degree of the nodes are close to each other, so targeting the most connected ones are not very different from a random selection.

...
Wikipedia