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 happens with a certain probability. The probability of deleting a node can follow any distribution; 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 each empirical network differently.[1]
The effect on the network connectedness is measured with the diameter of the network (the length of the longest shortest path between two nodes).[2] When we remove a fraction f of nodes, the diameter of the network increases monotonically with f. This is because each node has approximately the same degree and thus contributes 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 interconnectedness of the network is untouched.
When node 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.[3]
r<1
\gamma=3+
| 2r | |
| 1-r |
r=1
r>1
When the objective is to break down a network, it makes much more sense to target certain nodes instead of removing them in a uniformly random fashion. This is the case for example when someone is fighting against a bacterium, or wants to dismantle a criminal network. Targeted removal 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.[4] 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.[5]
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 homogeneous, the degree of the nodes are close to each other (the degree distribution is sharply peaked around its mean), so targeting of the most connected ones is not very different from a random selection.
The diameter of the BA model increases drastically when the most connected nodes are deleted compared to the random removal case. The diameter is doubled when 5% of the nodes are eliminated. This is because removing the hubs seriously changes the topology of the network, most links are removed, so the diameter goes up.