Controlling percolation with limited resources

Connectivity, or the lack thereof, is crucial for the function of many man-made systems, from financial and economic networks over epidemic spreading in social networks to technical infrastructure. Often, connections are deliberately established or removed to induce, maintain, or destroy global connectivity. Thus, there has been a great interest in understanding how to control percolation, the transition to large-scale connectivity. Previous work, however, studied control strategies assuming unlimited resources. Here, we depart from this unrealistic assumption and consider the effect of limited resources on the effectiveness of control. We show that, even for scarce resources, percolation can be controlled with an efficient intervention strategy. We derive such an efficient strategy and study its implications, revealing a discontinuous transition as an unintended side effect of optimal control.

Figure 1

Controlling the percolation transition. (a) Random percolation: in each step a link is selected uniformly at random and added to the network. (b) Controlled percolation: In each step, we can prevent the chosen link from being added to the network, paying a cost $c\left[S\right(i),S(j\left)\right]$ from a limited budget $B$. The constraint of a limited budget requires an efficient control strategy. As described in the text, we only prevent links when the probability that the intervention is successful is sufficiently large, $\mathrm{Prob}\left(\mathrm{success}\right)\ge 1-\epsilon$. We consider an intervention unsuccessful if a similarly large cluster is likely to appear again with the next link $e_{kl}$. Consequently, we intervene when the probability of such a failure $\mathrm{Prob}\left(\mathrm{failure}\right)\approx \mathrm{Prob}[S\left(k\right)+S\left(l\right)\ge S_{ij}]<\epsilon$ is small (the expected time until a similarly large cluster appears is large). When this failure probability is too large or the budget is exhausted, we do not intervene. As illustrated, this control delays the creation of large clusters and the onset of percolation.

Figure 2

Effects of resource limited control of percolation. (a) Single realization of the evolution of the relative size of the largest cluster for $N=2^{25}$ (red solid line) and remaining fraction of the budget (red dashed line) for budget parameter $b=0.05$ and intervention intensity $\epsilon =0.1$. Compared to zero budget, the percolation threshold is shifted from $p_c=0.5$ (gray line, showing random percolation without control) to $p_c\approx 0.67$. Interestingly, the transition remains continuous and in the same universality class. (b) Single realizations of the evolution of the relative size of the largest cluster for $N=2^{25}$, $\epsilon =0.1$, and different values of $b$. Surprisingly, when $b$ becomes large enough, the transition becomes discontinuous. Inset: the largest gap $max(\mathrm{\Delta }{S}_1/N)$, averaged over $2^{10}$ to $2^6$ realizations; error bars indicate the standard deviation. For small $b$, the scaling is the same as expected for random percolation, $max(\mathrm{\Delta }{S}_1/N)\sim N^{-1/3}$. However, for a sufficiently large budget, the largest gap is independent of the network size and the transition is discontinuous.

Figure 3

Discontinuous transition above a critical budget. Percolation threshold $p_c$ measured by the position of the largest gap of $S_1$ for different values of $b$. Results are averaged over 1024 and 256 realizations for networks of size $N=2^{20}$ and $2^{25}$, respectively. Error bars indicate the standard deviation. The delay increases with an increasing budget until it becomes constant above a critical budget $b_c\approx 0.058$. At the same time, the transition changes from continuous to discontinuous at $b=b_c$. Inset: The size of the largest gap $\max (\mathrm{\Delta }{S}_1/N)$ for different $b$.

Figure 4

“Phase diagram” and discontinuous transition as a result of optimal control. Position of the transition $p_c$ for budget parameter $b=0.05$ as a function of intervention intensity $\epsilon$ and intervention start $p_{\mathrm{start}}$. Results for system size $N=2^{20}$, averaged over $R=128$ realizations. The largest delay with $p_c\approx 0.72$ is achieved for a set of optimal intervention parameters (bright yellow) that separate the continuous from the discontinuous transition regime. The transition becomes discontinuous as a result of the optimal resource limited control. The black dashed line represents our estimate for this optimal parameter set in $(\epsilon ,p_{\mathrm{start}})$ space (see text). The thin lines indicate lines of constant $p_c$.

Figure 5

Effectiveness of resource limited control. Single realizations of the largest cluster size for the budget limited control (red solid line) and the product rule (green dashed line) [21] resulting in explosive percolation ($N=2^{25}$). The parameters are $b=0.88$ and $\epsilon =0.62$. In both models $L_{\mathrm{rej}}\approx 0.88N$ links are rejected until the phase transition occurs. This illustrates that the intervention rule defined in the main text is more effective in delaying the transition and at the same time keeps the transition smoother.

Figure 6

Controlled percolation. Single realizations of the largest cluster size (red solid lines) and the remaining fraction of the budget (green dashed lines) for various parameter combinations and $N=2^{25}$. Depending on the parameters the delay between the last interventions (budget reaching 0) and the percolation transition changes. The transition is smoothest when this gap is large. When the budget lasts until after the percolation transition, the transition becomes discontinuous.

Figure 7

Finite-size scaling for controlled percolation. Results for finite-size scaling for the estimated critical point and two values of $p$ slightly below and above. The error bars indicate the standard deviation; lines are guides to the eye. Averages are taken over 1024 to 64 realizations for system sizes from $N=2^{20}$ to $N=2^{30}$. The black dashed lines indicate the best fits; the resulting exponents are listed in Table 1 above. (a) Results for the exponent $-\beta /\nu \approx -1/3$, showing the same behavior as expected for random percolation for all continuous transitions. For $b=0.1$, $\epsilon =0.1$ we find $\beta \approx 0$, corresponding to a discontinuous transition. (b) Results for the exponent $\gamma /\nu \approx 1/3$, showing the same behavior as expected for random percolation for all continuous transitions.

Figure 8

Critical cluster size distribution. Cluster size distribution $n_S$ for various system sizes $N$ $[N=2^{20}$, $2^{25}$, and $2^{30}$ averaged over 1024, 256, and 64 realizations, respectively ($N=2^{20}$, $2^{22}$, and $2^{25}$ for $b=0.1$, $\epsilon =0.1$)]. Here, $n_S$ describes the relative frequency of clusters of size $S$. The results are aggregated into logarithmic bins for clusters with size $S>N^{1/3}$ up to $S=16N^{1/2}$. The scaling is expected to follow a power law $n_S\sim S^{-\tau }$ for large $S$; the dashed black lines show the scaling expected for random percolation with exponent $\tau =5/2$ (not normalized). The peak in the cluster size distribution for small $S$ is a signature of the finite size of clusters in the system when the interventions stop. Larger budgets allow for more interventions shifting the peak to larger $S$ and making it more pronounced. Higher intervention intensities use the budget earlier, shifting the peak to lower $S$.

Figure 9

Distribution of interventions. (a) Single realization of the largest cluster size in the subcritical regime for $N=2^{25}$ with unlimited budget and $\epsilon =0.1$. (b), (c) Probability of an intervention for a single link chosen at $p$ for two different system sizes averaged over 100 realizations each. When a new cluster size appears in the network the intervention probability “resets.” This causes the transitions to $S_1=3$ at $p_3$, $S_1=4$ at $p_4$, and so on to occur at fixed positions. This behavior is similar to the subcritical evolution of the largest cluster in the BFW model, leading to a discontinuous transition at $p_k\to p_c$ for $k\to \infty$.

Figure 10

Estimating the intervention rate. Probability of an intervention for a single link chosen at $p$ for system size $N=2^{20}$ averaged over 100 realizations. The red and green lines illustrate the approximation used to define the effective intervention rate ${\epsilon }_{\mathrm{eff}}$ (green), describing a local average of the true intervention rate (here for $p_{\mathrm{start}}=0$).

Figure 11

Enhancing percolation. Single realizations of the largest cluster size (red solid lines) and the remaining fraction of the total budget (green dashed lines) for various parameter combinations for interventions enhancing percolation ($N=2^{25}$). Depending on the parameters the transition is enhanced more or less strongly. As for delaying the transition, interventions are most efficient when the interventions last exactly until the transition.