Optimal redundancy against disjoint vulnerabilities in networks

Abstract

Redundancy is commonly used to guarantee continued functionality in networked systems. However, often many nodes are vulnerable to the same failure or adversary. A "backup" path is not sufficient if both paths depend on nodes which share a vulnerability.For example, if two nodes of the Internet cannot be connected without using routers belonging to a given untrusted entity, then all of their communication-regardless of the specific paths utilized-will be intercepted by the controlling entity.In this and many other cases, the vulnerabilities affecting the network are disjoint: each node has exactly one vulnerability but the same vulnerability can affect many nodes. To discover optimal redundancy in this scenario, we describe each vulnerability as a color and develop a "color-avoiding percolation" which uncovers a hidden color-avoiding connectivity. We present algorithms for color-avoiding percolation of general networks and an analytic theory for random graphs with uniformly distributed colors including critical phenomena. We demonstrate our theory by uncovering the hidden color-avoiding connectivity of the Internet. We find that less well-connected countries are more likely able to communicate securely through optimally redundant paths than highly connected countries like the US. Our results reveal a new layer of hidden structure in complex systems and can enhance security and robustness through optimal redundancy in a wide range of systems including biological, economic and communications networks.

15 pages

References in corpus (9)

• The structure and dynamics of multilayer networks
• Influence maximization in complex networks through optimal percolation
• New Model of Internet Topology Using k-shell Decomposition
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Percolation in living neural networks
• Message passing theory for percolation models on multiplex networks with link overlap
• Multi-state epidemic processes on complex networks
• Bicomponents and the robustness of networks to failure
• Meta-food-chains as a many-layer epidemic process on networks

Cited by in corpus (6)

• A system-wide network reconstruction of gene regulation and metabolism in Escherichia coli
• Color-avoiding percolation
• Bond and site color-avoiding percolation in scale free networks
• Critical field-exponents for secure message-passing in modular networks
• General theory for extended-range percolation on simple and multiplex networks
• Color-avoiding percolation in edge-colored Erdős-Rényi graphs