Abstract

We study networks which are robust in the face of attacks

The key tension here is that on the one hand, connections facilitate communication which is essential for task completion while on the other hand, connections expose individuals to indirect infection/detection and elimination.

We study a game between a designer and an adversary. The designer chooses a network while the adversary chooses the nodes to attack. We find that the optimal attack strategy involves targeting a few nodes and ignoring the rest. Faced with this attack strategy, a robust network consists of equal size groups whose number grows (and size falls) as the attack budget of the adversary increases.

We then extend this mode: suppose the designer can choose the network and defend nodes. The main insight is that it is attractive to protect central nodes as this minimizes the prospects of indirect detection/infection. As reliability of defence grows the designer links more nodes to the protected nodes; with perfectly reliable defence the robust network is a star.

This is based on joint work with Adrien Vigier of Cambridge University.