What can we learn from terrorists about network optimization?

 

ALEXANDER GUTFRAIND

LOS ALAMOS NATIONAL LABORATORY

 

Most complex socio-economic networks such as transportation networks, information systems and even clandestine social networks need to provide resilience - to be able to function even if some of the nodes are compromised by human or natural adversaries. In many cases the failure of a single node could lead to a far-reaching domino effect where some of the adjacent nodes are lost as well, followed by their neighbors and so on. This cascade threat motivates the search for mechanisms and network designs that would increase the networks' cascade resilience while maintaining performance efficiency. I will introduce a solution based on a direct but tractable approach: the networks are designed by finding networks that maximize a combination of cascade resilience and efficiency. Under certain definitions of resilience and efficiency the optimal networks are those consisting of multiple star-like cells. For many parameter values, when the risk of cascades is increased the edge density of the optimal network topology initially decreases but then surprisingly increases again when cascade risk is high. This implies paradoxically that some networks ought not to be modified for cascade resilience, since the cost in efficiency is too high. Understanding cascade resilience and its structural phase transitions will help identify design more resilient networks in many diverse application areas and identify vulnerabilities in violent underground groups.