Color-avoiding percolation

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.

Figure 1

Color-avoiding percolation with redundant paths for avoiding white and black nodes. (a) Sender S and receiver R can communicate along the magenta (lower) path avoiding nodes of white color, or along the yellow (upper) path avoiding black nodes. (b) The component ${\mathcal{L}}_{\overline{\mathrm{white}}}^{+}$, where every node pair can communicate over a path avoiding nodes of white color in between. Links to dangling nodes of white color are shown with dashed lines. (c) Component ${\mathcal{L}}_{\overline{\mathrm{black}}}^{+}$. (d) Nodes in ${\mathcal{L}}_{\mathrm{color}}={\mathcal{C}}_{\overline{\mathrm{white}}}\cap {\mathcal{C}}_{\overline{\mathrm{black}}}\cap {\mathcal{L}}_{\overline{\mathrm{white}}}^{+}\cap {\mathcal{L}}_{\overline{\mathrm{black}}}^{+}$ are highlighted with red halos, where ${\mathcal{C}}_{\overline{c}}$ denotes the set of nodes with color other than $c$. Nodes in ${\mathcal{L}}_{\mathrm{color}}$ are pairwise color-avoiding connected. If black and white nodes would be avoided together, connectivity for blue nodes would break down.

Figure 2

Color-avoiding connectivity depends on topology and color distribution. Results for Poisson graphs, where the first two colors with frequencies $r_1+r2=0.8$ are avoided, and connectivity is measured as the fraction of nodes being CAC among the nodes of the trusted third color with $r_3=0.2$. (a) The black (upper) line shows the connectivity $S_{\mathrm{color}}^{\left\{1\right\}}$ avoiding the dominating color $c=1$ with frequency $r_1=0.5$. The blue (middle) line shows results $S_{\mathrm{color}}^{\{1,2\}}$, if first and second color are avoidable, where the second color has a smaller frequency $r_2=0.3$. The fraction of connected nodes reduces only slightly, even if many more nodes have to be avoided. If nodes of colors 1 and 2 would be avoided at the same time, as shown with the red (lower) line, connectivity would reduce considerably. Numerical results confirm the theory (crosses, averages over 100 networks of size $N={10}^7$). (b) For $\overline{k}=4$, color 1 cannot be avoided at all as long as $r_1>r_{\mathrm{crit}}=3/4$. Therefore, in a network with one dominating node class, it can be beneficial to replace colors of some nodes, thus reducing $r_1$ and increasing $r_2$ (as outlined in the inset). While standard connectivity stays suppressed (red lower line), color-avoiding connectivity (blue middle line) increases almost as much as connectivity avoiding only the larger color (black upper line). (c) $S_{\mathrm{color}}^{\{1,2\}}$ is shown for varying topology and color frequencies. The solid black line indicates the critical manifold. Dashed black lines highlight the parameter manifolds of (a) and (b), and the phase transition along these lines has critical exponent ${\beta }_k={\beta }_r=1$. The phase transition along the dotted black line is of different type, with exponent ${\beta }_k=2$ (see Fig. 3). This is connected to a sharp bend in the critical manifold.

Figure 3

Crossover between critical behavior with ${\beta }_k=1$ (black dashed line) and ${\beta }_k=2$ (red solid line). We fix the frequency of the dominating avoided color $r_1=0.2$, thus fixing ${\overline{k}}_{\mathrm{crit}}=1.25$ on Poisson graphs. Results are shown for $r_2=r_1$ (red solid line and crosses), $r_2=r_1-0.03$ (green dotted line and circles), $r_2=r_1/2$ (black dashed line and squares), and $r_2=0$ (blue dash-dotted line, identical to standard percolation avoiding first color). For the third color, trusted for sending and transmitting, we have $r_3=1-r_1-r_2$. Symbols are averages over 100 networks of size $N={10}^7$.

Figure 4

Influence of the dominating colors. Results for Poisson graphs. The first three colors are avoided. (a) Compared to a single dominating color (black upper line, $r_1=0.3, r_2=r_3=0.12$, trusted fourth color with $r_4=0.46$), degenerated highest frequencies reduce the color-avoiding connectivity stronger, and change the critical behavior (blue middle line: $r_1=r_2=0.3, r_3=0.12, r_4=0.28$; red lower line: $r_1=r_2=r_3=0.3, r_4=0.1$). The results are repeated in (b) with logarithmic scaling. We see that the critical exponent ${\beta }_k$ is identical to the degeneration of the highest color frequency.

Figure 5

Simultaneous probabilities for avoiding many colors give a qualitative understanding of critical exponents. (a) With two avoided colors and $r_1=1/4, r_2=1/5$, the critical connectivity is $\overline{k}=4/3$. Close to the critical point, $v_{\left\{1\right\}}$ grows with exponent of 1 (black dotted line), saturating to the probability of having color $c\ne 1$ for large $\overline{k}$. $v_{\left\{2\right\}}$ (black dash-dotted line) has a value of about $1/10$ at the critical point. The product of both probabilities $v_{\left\{1\right\}}{v}_{\left\{2\right\}}$ (red dashed line) can be seen as an approximation of independent probabilities for $v_{\{1,2\}}\propto S_{\mathrm{color}}^{\{1,2\}}$ (red solid line). This helps to qualitatively understand the critical exponent ${\beta }_k=1$. (b) Three avoided colors with $r_1=r_2=r_3=1/4$. Probabilities $v_{\left\{1\right\}}$ (black dotted line), $v_{\left\{1\right\}}^2$ (red dashed-dotted line), and $v_{\left\{1\right\}}^3$ (blue dashed line) are useful for a qualitative understanding of the quadratic behavior of $v_{\{1,2\}}$ (red crosses) and cubic behavior of $v_{\{1,2,3\}}\propto S_{\mathrm{color}}^{\{1,2,3\}}$ (blue solid line). In this way, the critical exponent ${\beta }_k=3$ is comprehensible. Asymptotic for large $\overline{k}$: $1-r_1-r_2$ true result, $(1-r_1)(1-r_2)=1-r_1-r_2+r_1{r}_2$ with independence assumption.

Figure 6

Sender and receiver trust their own colors. Having four colors with frequencies $r_c=c/10$, we choose pairs $(c_1,c_2)\subset \{1,2,3,4\}$ of trusted colors for sending and receiving. Shown is the fraction of sender nodes with color $c_1$ which are able to reach nodes of the receiver color $c_2$. Denoting $c_3$ and $c_4$ for the two remaining colors, it reads $S_{\mathrm{color}}^{\{c_3,c_4\}}$ (for sender and receiver color being the same $c_1$, we use $c_2, c_3$, and $c_4$ denoting the other colors, and $S_{\mathrm{color}}^{\{c_2,c_3,c_4\}}$). For the smallest $\overline{k}=1.4$, we see that all nodes of colors 1 and 2 are excluded from communication, but they are needed for colors 3 and 4 to connect them. For increased $\overline{k}=1.6$, nodes of color 4 can communicate with nodes of all colors, and with $\overline{k}=2.0$, nodes of all color pairs can communicate.

Figure 7

For scale-free graphs, trusting colors can increase color-avoiding connectivity remarkably. Graphs with broad degree distribution ($p_k\sim k^{-\alpha }, k>0$) and the same color frequencies $r_c=c/10$ as in Fig. 6. The red dotted line shows $S_{\mathrm{color}}^{\{1,2,3,4\}}$, where no color is trusted for transmission (the diamonds indicate numerical results, averages over 100 graphs of size $N={10}^5$). This is restricted by the two-core (solid black line). With trusting colors, color-avoiding connectivity is increased above the size of the two-core. Results shown for trusting color 4 ($S_{\mathrm{color}}^{\{1,2,3\}}$, green dashed line, and circles for numerical results) and trusting colors 3 and 4 ($S_{\mathrm{color}}^{\{1,2\}}$, blue dash-dotted line, and squares for numerical results). The latter case, where sender and receiver nodes of colors 3 and 4 trust their colors, is close to full standard connectivity (black solid line with crosses).

Figure 8

Comparison with the approximate theory of [2]. Left: $C=3$ colors of the same frequency $r_c=1/C$ are avoided for transmission, all colors trusted for sending. Results with the approximate theory of [2] (AICP, red dashed line) are close to results with the theory presented here (black solid line). The deviation (positive values with the blue dotted line and negative values shown with the green dash-dotted line) is small. Right: For $C=10$ colors, the deviation is larger, and close to the critical point, the theory of [2] gives poor results, even if the critical behavior is qualitatively captured. Black circles show numerical results (averages over 100 networks of size $N={10}^8$).

Figure 9

A fake approximation, closer to the theory then AICP but violating constraint Eq. (49), gives poor results. Left: For $C=5$ colors, we see results of the theory presented here (black solid line), and results with AICP (red dashed line). Results of a fake approximation are poor (dash-dotted green line), because this approximation violates the constraint, residual term ${\mathrm{\Delta }}^{\mathrm{app}1}$, shown with a dotted green line. Right: The error ${\delta }_5^{\mathrm{AICP}}$ (red dashed line) made in describing $u_{\{1,\cdots ,5\}}$ is quadratic in $\overline{k}-{\overline{k}}_{\mathrm{crit}}$ close to the critical point. For the fake approximation, ${\delta }_5^{\mathrm{app}1}$ is constructed to be smaller (green dash-dotted line).

Figure 10

Uniting colors of small frequency. The black solid line shows results where eight colors are avoided, with frequencies ${\left(r_c\right)}_c=(4/10,2/10,1/10,1/20,1/40,1/80,1/80)$, summing up to 0.8. The green dotted line shows an upper limit, where only the first three colors are avoided, with ${\left(r_c\right)}_c=(4/10,2/10,1/10)$. The red dashed line shows a lower limit, where the last six colors are united into one new color, with ${\left(r_c\right)}_c=(4/10,2/10,2/10)$. Combining many colors of small frequencies into one color reduces color-avoiding connectivity only slightly, thus allowing for better performance of algorithms.