Biased percolation on scale-free networks

Biased (degree-dependent) percolation was recently shown to provide strategies for turning robust networks fragile and vice versa. Here, we present more detailed results for biased edge percolation on scale-free networks. We assume a network in which the probability for an edge between nodes $i$ and $j$ to be retained is proportional to ${\left(k_i{k}_j\right)}^{-\alpha }$ with $k_i$ and $k_j$ the degrees of the nodes. We discuss two methods of network reconstruction, sequential and simultaneous, and investigate their properties by analytical and numerical means. The system is examined away from the percolation transition, where the size of the giant cluster is obtained, and close to the transition, where nonuniversal critical exponents are extracted using the generating-functions method. The theory is found to agree quite well with simulations. By presenting an extension of the Fortuin-Kasteleyn construction, we find that biased percolation is well-described by the $q\to 1$ limit of the $q$-state Potts model with inhomogeneous couplings.

Figure 1

(Color online) The critical fraction at percolation $f_c$ as a function of the network size $N$. To compute this critical fraction we average over ${10}^4$ network realizations for each set of parameters and apply for each network the percolation process 100 times. No cutoff was introduced for the maximal node degree and network reconstruction was done with the sequential approach.

Figure 2

(Color online) The probability ${\rho }_k$ to retain a node after depreciation [see Eq. (15)] as a function of its original degree $k$ using the sequential approach. The main panel shows results for networks with $\gamma =4$ submitted to PB with $\alpha =-1$. The dots indicate the simulation results for ten network realizations and ten percolation routines. The continuous lines are the best fit to the data of Eq. (17). The inset shows the same but for a network with $\gamma =2.5$ subjected to CB with $\alpha =0.5$. The arrows indicate the crossover value $k_{\times }$. The continuous lines are the best fits to the data of Eq. (17). In both cases, $m=2$ and $N={10}^5$. No cutoff was introduced for the maximal node degree. From top to bottom f=0.9, 0.5, 0.1.

Figure 3

(Color online) Mean nearest-neighbor degree $k_{nn}$ as a function of the degree of a node $k$, both for the original network (upper, red line) and a network where only a fraction $f=0.9$ of the links is present (lower, black line). Clearly correlations which give rise to disassortative mixing emerge in the depreciated network. We used an original network constructed with the uncorrelated configuration model with $\gamma =2.6$, $m=2$, and $N={10}^5$, which is diluted using sequential biased percolation with $\alpha =0.3$, such that $\overline{\gamma }=3.3$. The result was obtained with two network realizations, on both of them the percolation process was applied four times. To reduce the noise level, the mean-neighbor degree is averaged over eight successive values.

Figure 4

(Color online) The probability that a node belongs to the giant cluster, ${\mathcal{P}}_{\infty }$, as a function of the fraction of retained links $f$ for unbiased percolation $\left(\alpha =0\right)$. We compare the sequential approach simulations (blue squares), the iterative simultaneous approach simulations (red triangles), and the theory of generating functions (black line). We used an original network with $\gamma =2.5$ and $N={10}^5$. The analytical results up to the fraction $f_u=1$ are obtained with the generating-functions theory. All results are in very good mutual agreement.

Figure 5

(Color online) The probability that a node belongs to the giant cluster, ${\mathcal{P}}_{\infty }$, as a function of the fraction of retained links $f$ for biased percolation with $\alpha =0.25$. We compare the sequential (blue line) and simultaneous (red dots) approach simulations. We used an original network with $\gamma =2.5$ and $N={10}^5$.

Figure 6

(Color online) The probability that a node belongs to the giant cluster, ${\mathcal{P}}_{\infty }$, as a function of the fraction of retained links $f$ for biased percolation with $\alpha =0.25$. We compare the sequential approach simulations (upper blue line), the iterative simultaneous approach simulations (red dots) and the theory of generating functions (lower black line). We used an original network with $\gamma =2.5$ and $N={10}^5$. The analytical results up to the fraction $f_u=0.44$ are obtained with the generating-functions theory. This figure presents more detail of the critical region of Fig. 5.

Figure 7

(Color online) The probability ${\rho }_k$ to retain a node after depreciation [see Eq. (15)] as a function of its original degree $k$ for different values of $f$ and using the iterated simultaneous approach. From bottom to top, we included 10%, 60%, and 90% of the links. We used a network with $\gamma =2.5$, $\alpha =0.5$ and $N={10}^5$ and averaged over ten network realizations. Results are averages over ten percolation simulations. Since $f_u=0.44$, the first regime can be reached in a single sweep and thus no cross-over emerges for $f=0.1$. The crossover (indicated by arrow) becomes apparent for $f=0.9$ when ten iterative steps are performed. This figure should be compared with the inset of Fig. 2 where the sequential approach was used.

Figure 8

(Color online) Emergence of correlations in the diluted network in the iterative simultaneous approach. This figure shows the mean nearest-neighbor degree in the diluted network. We used an original network constructed with the uncorrelated configuration model with $\gamma =2.6$, $m=2$, and $N={10}^5$ which is diluted using the iterative simultaneous approach to biased percolation with $\alpha =0.3045$, such that $\overline{\gamma }=3.3$. The diluted networks contain, from bottom to top, 40 (red), 50 (black), 90 (green), 95 (blue), 98 (purple), and 99.5 (gray) percent of the edges of the original network. To obtain such a network, respectively, 1, 2, 5, 8, and 12 iterations have been made. The result was obtained with 10 network realizations, on all of them, the percolation process was applied 10 times. To reduce the noise level, the mean nearest-neighbor degree was averaged over eight successive values.