Topological stability and dynamic resilience in complex networks

Abstract

Stability is a concern in complex networks as disparate as power grids, ecosystems, financial networks, the Internet, and metabolisms. I introduce two forms of topological stability that are relevant to network architectures: cut and connection stability. Cut-stability concerns a network's ability to resist being broken into pieces. Connection-stability concerns a network's ability to resist the spread of viral processes. These two forms of stability are antagonistic. Therefore, no network can ever be com­pletely architecturally stable. Changes to network topology that increase one form of sta­bility, compromise the other. This may seem disappointing, but there is good news. Dy­namic processes can stabilize a network and compensate for architectural limitations. Let us call such stabilizing processes, 'resilient mechanisms'. Such resilient mechanisms can be abstracted from stabilizing processes in biology, or designed de novo. Resilient processes have evolved to dynamically stabilize biological networks in the face of architectural limitations. They have been studied by biologists in several areas from homeostasis to evolutionary robustness. These processes exist today because they have been effective over evolutionary time scales. This provides an opportunity for computer scientists to learn from biology about processes that can stabilize the complex networks characteristic of distributed systems. I introduce a multi-agent framework, Probabilistic Network Models (PNMs), within which we can test different candidate resilient processes under varying network architec­tures. I focus on a PNM for a viral instability where the resilient process is the simple immune response of sending a warning message. Counter-intuitively, network architectures that favour the virus, also favour the warning message running ahead. Dynamic resilience, thus allows for an architectural weakness in connection-stability to be circumvented by pro­cesses as simple as sending a warning message.