Color-avoiding percolation

Sebastian M. Krause, Michael M. Danziger, Vinko ZlatićPhysical 2017 · DOI · arXiv

Abstract

Many real world networks have groups of similar nodes which are vulnerable to the same failure or adversary. Nodes can be colored in such a way that colors encode the shared vulnerabilities. Using multiple paths to avoid these vulnerabilities can greatly improve network robustness, if such paths exist. Color-avoiding percolation provides a theoretical framework for analyzing this scenario, focusing on the maximal set of nodes which can be connected via multiple color-avoiding paths. In this paper we extend the basic theory of color-avoiding percolation that was published in S. M. Krause et al. [Phys. Rev. X 6, 041022 (2016)]. We explicitly account for the fact that the same particular link can be part of different paths avoiding different colors. This fact was previously accounted for with a heuristic approximation. Here we propose a better method for solving this problem which is substantially more accurate for many avoided colors. Further, we formulate our method with differentiated node functions, either as senders and receivers, or as transmitters. In both functions, nodes can be explicitly trusted or avoided. With only one avoided color we obtain standard percolation. Avoiding additional colors one by one, we can understand the critical behavior of color-avoiding percolation. For unequal color frequencies, we find that the colors with the largest frequencies control the critical threshold and exponent. Colors of small frequencies have only a minor influence on color-avoiding connectivity, thus allowing for approximations.

Introduction: The Challenge of Correlated Failures

Traditional percolation theory typically assumes that node or link failures are independent. However, in modern infrastructure, failures are often correlated. For instance, a group of routers might share the same firmware vulnerability, or multiple power plants might depend on a single gas pipeline. In these scenarios, the failure of one component implies the potential failure of all others sharing that specific vulnerability.

Color-avoiding percolation (CAP) addresses this by assigning "colors" to nodes to represent shared risks. The goal is to determine if two nodes can communicate via a set of paths such that no single color (vulnerability) can sever all of them. If a path exists that avoids "Red" nodes and another exists that avoids "Blue" nodes, the connection is robust against the failure of either color.

Conceptual illustration of color-avoiding paths. (a) shows paths avoiding specific colors, while (d) highlights the role of 'trusted' nodes in maintaining connectivity.

An Exact Analytical Framework

Previous research into CAP relied on heuristic approximations to manage the complexity of overlapping paths—specifically, the fact that a single physical link can belong to multiple color-avoiding paths. This paper introduces an exact analytical theory using generating functions to track the probability of a node belonging to the "giant color-avoiding component."

The authors derive a system of $2^{|T|} - 1$ self-consistency equations, where $T$ is the set of avoided colors. By applying the inclusion-exclusion principle and introducing new dual variables ($v_Q$), they successfully "untangle" the overlapping probabilities. This method allows for a precise calculation of connectivity even as the number of avoided colors increases, a significant improvement over previous heuristics.

Key Insights: Dominant Colors and the Power of Trust

One of the most significant findings is the "Dominant Color" rule. The network's critical threshold—the point at which it loses global connectivity—is primarily dictated by the color with the highest frequency. Rare vulnerabilities have a negligible impact on overall robustness, allowing researchers to simplify complex systems by grouping infrequent colors into "meta-colors."

Furthermore, the model distinguishes between node functions. Nodes can act as transmitters, which must be avoided if their color is compromised, or as senders/receivers, who might "trust" their own color. This distinction is vital; in scale-free networks, allowing nodes to trust their own color can dramatically boost the size of the giant component beyond traditional theoretical limits.

Phase transitions in CAP. (a) and (b) show the fraction of nodes in the giant component as a function of mean degree and color frequency, while (c) maps the critical manifold.

Results and Critical Behavior

The exact theory proves to be substantially more accurate than previous models, especially for systems with many avoided colors. The authors also explored the critical exponents of CAP. While standard percolation typically shows a linear growth near the threshold (exponent $\beta=1$), CAP exhibits a power-law growth with $\beta = n$, where $n$ is the number of colors tied for the highest frequency. This indicates that networks with multiple primary vulnerabilities are significantly more fragile and slower to recover after crossing the critical threshold.

Conclusion

By providing an exact mathematical treatment for color-avoiding percolation, this work offers a robust tool for analyzing the resilience of complex networks against correlated failures. While the computational complexity grows exponentially with the number of colors, the "dominant color" approximation provides a practical path forward for real-world applications. Future work will focus on developing practical routing algorithms to utilize these theoretical paths and exploring the impact of non-random color distributions.

Summary updated

Abstract

Many real world networks have groups of similar nodes which are vulnerable to the same failure or adversary. Nodes can be colored in such a way that colors encode the shared vulnerabilities. Using multiple paths to avoid these vulnerabilities can greatly improve network robustness, if such paths exist. Color-avoiding percolation provides a theoretical framework for analyzing this scenario, focusing on the maximal set of nodes which can be connected via multiple color-avoiding paths. In this paper we extend the basic theory of color-avoiding percolation that was published in S. M. Krause et al. [Phys. Rev. X 6, 041022 (2016)]2160-330810.1103/PhysRevX.6.041022. We explicitly account for the fact that the same particular link can be part of different paths avoiding different colors. This fact was previously accounted for with a heuristic approximation. Here we propose a better method for solving this problem which is substantially more accurate for many avoided colors. Further, we formulate our method with differentiated node functions, either as senders and receivers, or as transmitters. In both functions, nodes can be explicitly trusted or avoided. With only one avoided color we obtain standard percolation. Avoiding additional colors one by one, we can understand the critical behavior of color-avoiding percolation. For unequal color frequencies, we find that the colors with the largest frequencies control the critical threshold and exponent. Colors of small frequencies have only a minor influence on color-avoiding connectivity, thus allowing for approximations.
BibTeX
@inproceedings{krause2017color,
  author = {Sebastian M. Krause and Michael M. Danziger and Vinko Zlatić},
  title = {{Color-avoiding percolation}},
  booktitle = {Physical},
  year = {2017},
  doi = {10.1103/physreve.96.022313},
}
Figure