Color-avoiding percolation
arXiv:1611.02617 · doi:10.1103/PhysRevE.96.022313
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. 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 [Krause et. al., Phys. Rev. X 6 (2016) 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. We compare this approximation with a new, more exact theory and show that the new theory is substantially more accurate for many avoided colors. Further, we formulate our new theory with differentiated node functions, as senders/receivers or as transmitters. In both functions, nodes can be explicitly trusted or avoided. With only one avoided color we obtain standard percolation. With one by one avoiding additional colors, we can understand the critical behavior of color avoiding percolation. For heterogeneous 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.
arXiv comment15 pages, 10 figures
References in corpus (25)
- Epidemic spreading in scale-free networks
- Random graphs with arbitrary degree distributions and their applications
- The spread of epidemic disease on networks
- Network robustness and fragility: Percolation on random graphs
- Resilience of the Internet to random breakdowns
- Influence maximization in complex networks through optimal percolation
- New Model of Internet Topology Using k-shell Decomposition
- MEDUSA - New Model of Internet Topology Using k-shell Decomposition
- k-core organization of complex networks
- Robustness of a Network of Networks
- Network robustness of multiplex networks with interlayer degree correlations
- Percolation and Epidemic Thresholds in Clustered Networks
- k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
- Percolation in networks composed of connectivity and dependency links
- Resilience and rewiring of the passenger airline networks in the United States
- Marketing Percolation
- Message passing theory for percolation models on multiplex networks with link overlap
- Evolution of robust network topologies: Emergence of central backbones
- Bicomponents and the robustness of networks to failure
- From the Physics of Interacting Polymers to Optimizing Routes on the London Underground
- Vulnerability and co-susceptibility determine the size of network cascades
- Several Multiplexes in the same City: The role of wealth differences in urban mobility
- Critical behavior of -core percolation: Numerical studies
- Networks with arbitrary edge multiplicities
- Optimal redundancy against disjoint vulnerabilities in networks
Cited by in corpus (8)
- Percolation on complex networks: Theory and application
- How does bond percolation happen in coloured networks?
- 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
- Emergent networks in fractional percolation
- On the complexity of color-avoiding site and bond percolation
- Color-avoiding percolation in edge-colored Erdős-Rényi graphs