As an intro, here is the Abstract from Nagaraja and Anderson’s paper:
“Often an attacker tries to disconnect a network by destroying nodes or edges, while the defender counters using various resilience mechanisms. Examples include a music industry body attempting to close down a peer-to-peer file-sharing network; medics attempting to halt the spread of an infectious disease by selective vaccination; and a police agency trying to decapitate a terrorist organisation. Albert, Jeong and Barab´asi famously analysed the static case, and showed that vertex-order attacks are effective against scale-free networks. We extend this work to the dynamic case by developing a framework based on evolutionary game theory to explore the interaction of attack and defence strategies. We show, first, that naive defences don’t work against vertex-order attack; second, that defences based on simple redundancy don’t work much better, but that defences based on cliques work well…Our models thus build a bridge between network analysis and evolutionary game theory, and provide a framework for analysing defence and attack in networks where topology matters. They suggest definitions of efficiency of attack and defence, and may even explain the evolution of insurgent organisations from networks of cells to a more virtual leadership that facilitates operations rather than directing them.” (emphasis added)
First, a little overview on the science of topology as applied to network design and vulnerability:
The Scale-free network suggested in (b) is not a case of hierarchy emerging out of randomness, but rather an analysis of the communication connections between nodes, not necessarily the command-connections. More connected nodes, shaded in (b), are “vertexes,” and are the traditional targets of decapitation attacks when trying to destroy a scale-free network. Nagaraja and Anderson first analyze the effectiveness of the vertex decapitation tactic on a scale-free network, and demonstrate that it is a highly effective means of disrupting a network when only simple defensive measures are taken, such as simple replacement of the decapitated node (we see this game playing out between al-Qa’ida in
Next, Nagaraja and Anderson address the effectiveness of several tactics to defend against vertex-decapitation attacks. Essentially, the time-tested tactic used by insurgent groups everywhere is by far the most effective: when one node becomes an attractive vertex target, break that node into a clique of several nodes, with each new node connected to every other in the clique, and dividing the prior connections of the vertex among the new nodes in the clique in order to reduce their attractiveness when faced with a vertex-targeting scheme.
Here’s a graphic of the use of the clique transition as a defensive tactic:
And here’s Ngaraja and Anderson’s analysis on the viability of the clique-transition defensive tactic to the vertex-decapitation attack.
So, the final conclusion of this
Taking a bit closer look, what is the optimal connectivity structure for rhizome? In theory, a pure rhizome structure would have no higher-order vertexes for attack. However, there is the potential that if every node maintains the same connectivity, communications will either be so burdensome (every node has many, many connections), or too slow (every node has very few connections). The most efficient linking methodology that still maintains a uniformly low vertex-order among nodes is the “small-worlds” theory: most links connect to very “close” neighbors, but at least one or two are very distant and weak. These distant, weak links are what makes the “6-degrees of separation” effect possible. How is someone in Southern California really linked to a poor peasant in rural