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.

Random deletion

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.

[Erdős-Rényi model]

The effect on the network connectedness is measured with the diameter of the network. 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.

[Barabási-Albert model]

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.

Random removal from a growing network

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.
  • , Scale-free Phase: In this phase the network keeps growing, although the growth rate is smaller due to the deletion of nodes. Here the degree distribution remains a power law, with the coefficient.
  • , Exponential Phase: In this case the removal of nodes and the appearance of new ones are equal, so the network has a constant size. The network loses its scale-free property, the degree distribution turns into a stretched exponential.
  • , Declining Network: The rate of removal is higher than the growth rate, so the network declines, after finite steps it disappears.

Targeted deletion

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. 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.

Erdős-Rényi model

When removing nodes starting from the most connected one 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, so targeting of the most connected ones is not very different from a random selection.

Barabási-Albert model

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.