Bypassing Large Groups of Vulnerable Nodes in Complex Networks

In many networked systems there are large groups of similar nodes which are vulnerable to the same failure or adversary. For example, servers in a communication network running the same software will fail together, if this software has a bug. Therefore, we are often faced with networks where all nodes of a group can fail together. Further, many different vulnerabilities can cover the whole network. This structural weakness has so far been overlooked in studies of network robustness. Here we discuss how multiple redundant paths enable a high level of robustness. With each vulnerability described as a color, we discuss ”color-avoiding percolation” [1,2]. An example network is shown in Figure 1 on the left, with all white nodes sharing one vulnerability and all black nodes sharing a second vulnerability. In the middle of the figure, the yellow path enables the sender node S and the receiver node R to communicate avoiding black nodes, while the purple path avoids white nodes. It would be impossible to avoid black and white nodes with a single path. On the right of the figure, the red halos indicate nodes in the largest color-avoiding component which are pairwise able to avoid all vulnerabilities. We present a fast numerical algorithm for finding the largest color-avoiding component in real world networks and analytical results for random network ensembles.