So, Wired writes up three West Point professors and their algorithm to decide which members of a terrorist network to zap. Apparently they implemented it in 30 lines of Python. The paper is here, with some pseudocode and the tantalising hint that they used NetworkX, but no Python. However, even the Wired piece tells us enough to reverse engineer it.
The key idea here is that whacking terrorist leaders is often stupid, because it causes the enemy to adopt a flatter, more decentralised, and therefore less vulnerable network structure. Also, they point out, the leaders are often forces for restraint and points of contact for negotiation.
Being who they were, they decided that they could fix this with a better optimisation. They looked at the network-wide degree centrality, a measurement of the centralisation or otherwise of the whole network which is defined as the fraction of total nodes in the network an average node is connected to. They then asked how this changed when they removed a node from the network. And they reasoned that increasing it was desirable, as it rendered the network overall more fragile and unstable.
Now, the Lobster Project uses weighted betweenness centrality – the fraction of the shortest routes through the network that pass through a given node, with more important nodes being accounted for as such – as its centrality metric. There is no particular reason to think that this would work differently.
So I thought I’d implement it. Their implementation used 30 lines, but I presume that includes the test harness to generate or load a specimen network as well as the analysis. Here goes:
def greedy_fragile(mgraph, month, mini, nodes):
...network_wide_centrality = float(sum(nodes.values())/len(nodes.values()))
...mgraph.remove_node(mini[0])
...n = centrality_nodes(mgraph)
...nwc = float(sum(n.values())/len(n.values()))
...mgraph.add_node(mini[0], mini[1])
...return {'Minister': mini[0], 'Title': mini[1]['Title'], 'Department': mini[1]['Department'], 'Date': month, 'Greedy_Fragile': network_wide_centrality - nwc}
mgraph is the NetworkX graph object, month is the month, mini is the minister (or lobby), nodes is the precomputed list of nodes and their centrality values. Obviously, if it wasn’t for the weird datastore thing I’d have done this recursively and made it return the values for the whole network rather than calling it for each node.
And it works. The first result was that one particular minister was slightly reducing the overall centralisation (and therefore fragility/instability) of the system as a whole. And he’s Ed Davey. As the point of having Lib Dems is meant to be reducing the centrality of Dave from PR and paddock-boy in the system, this suggests that we shouldn’t get rid of him yet.