Question about Robustness
Consider a large scale-free network with average degree ⟨k⟩ = 5. According to robustness concepts, which of the following options best describes the critical fraction of nodes that would need to be removed to cause the collapse of the giant component (i) in the case of random failures and (ii) in the case of targeted attack, respectively?
a) The network is equally robust to random failures and to attacks on hubs: in both cases, it is necessary to remove about 50% of the nodes to collapse the giant component.
b) Under random failures, the network collapses after removing only about 15% of the nodes; in contrast, a targeted attack requires removing about 80% of the nodes (including the hubs) to fragment the giant component.
c) In random failures, it is necessary to remove about 80% of the nodes to eliminate the giant component; in targeted attacks (removing hubs), removing about 15% of the nodes is enough to drastically fragment the network.
d) There is no critical threshold for random failure (it would be necessary to remove practically 100% of the nodes to collapse the giant component), but in targeted attacks the giant component disappears only after removing more than 50% of the nodes.
e) None of the above.
Original idea by: Ingrid Barbosa
Good question, but I would think we also need to know in order to check the percentages mentioned in the alternatives. Am I right?
ReplyDeleteProfessor, I formulated the question aiming to focus more on qualitative concepts and orders of magnitude. However, you are right. To make the question formally more precise, I could explicitly mention that the percentages are only indicative, for example, “a large portion” versus “a small fraction” of the nodes. I will adjust bellow
ReplyDeleteConsider a large scale-free network. According to robustness concepts, which of the following options best describes the critical fraction of nodes that would need to be removed to cause the collapse of the giant component (i) in the case of random failures and (ii) in the case of targeted attack, respectively?
ReplyDeletea) The network is equally robust to random failures and to targeted attacks: in both cases, removing a moderate fraction of nodes is sufficient to collapse the giant component.
b) Under random failures, the giant component collapses after removing a small fraction of nodes. In contrast, a targeted attack requires removing a large fraction of nodes to fragment the network.
c) Under random failures, a large fraction of nodes must be removed to eliminate the giant component. Under targeted attacks (removing hubs), a small fraction of nodes is sufficient to drastically fragment the network.
d) There is no meaningful robustness difference between random failures and targeted attacks, since in both cases the giant component disappears only after removing almost all nodes.
e) None of the above