Optimal cost for strengthening or destroying a given network

Strengthening or destroying a network is a very important issue in designing resilient networks or in planning attacks against networks, including planning strategies to immunize a network against diseases, viruses, etc. Here we develop a method for strengthening or destroying a random network with a minimum cost. We assume a correlation between the cost required to strengthen or destroy a node and the degree of the node. Accordingly, we define a cost function $c\left(k\right)$, which is the cost of strengthening or destroying a node with degree $k$. Using the degrees $k$ in a network and the cost function $c\left(k\right)$, we develop a method for defining a list of priorities of degrees and for choosing the right group of degrees to be strengthened or destroyed that minimizes the total price of strengthening or destroying the entire network. We find that the list of priorities of degrees is universal and independent of the network's degree distribution, for all kinds of random networks. The list of priorities is the same for both strengthening a network and for destroying a network with minimum cost. However, in spite of this similarity, there is a difference between their $p_c$, the critical fraction of nodes that has to be functional to guarantee the existence of a giant component in the network.

Figure 1

Demonstrating the behavior of $z\left(k\right)$ when the maximum degree of the network is 10 [(a), (b)] with power-law cost function and [(c), (d)] with exponential cost function: (a) An extremum maximum for $z\left(k\right)$ at intermediate values of $k$ $\left(k_{\max }=5\right)$ when $\alpha =2.25$ (and in general for any $2<\alpha <3)$. (b) Monotonic decreasing function of $z\left(k\right)$ for $\alpha =3.2$ (and in general for any $\alpha \ge 3)$. (c) The case of very small $\beta$ where $z\left(k\right)$ behaves as a monotonic increasing function. (d) An extremum maximum for $z\left(k\right)$ at intermediate values of $k$ $\left(k_{\max }=6\right)$ when $\beta =0.4$ (and in general for all $0<\beta <1.5)$. In all cases, for simplifying the demonstration, the values of $z\left(k\right)$ were normalized by dividing them by the maximum value of the original series $z\left(k\right)$.

Figure 2

[(a), (b)] Behavior of the size of the giant component vs the normalized accumulated cost: Cost function is power law $c\left(k\right)=k^{\alpha }$. Open symbols represent simulations results of ER networks having $N={10}^3$ nodes: (a) Average degree $\lambda =4$ and $\alpha =3.2$. (b) Average degree $\lambda =8$ and $\alpha =1$. A normalization of the cost values $P$ on the $x$ axis was implemented by dividing by the minimum total cost $P_{\min }$ of the four curves (strategies). [(c), (d)] Behavior of the size of the giant component vs the cost: Cost function is exponential $c\left(k\right)=e^{\beta k}$. (c) Average degree $\lambda =4$ and $\beta =0.2$. (d) Average degree $\lambda =8$ and $\beta =2.5$. Averages are taken over 50 realizations. The $\alpha$'s and $\beta$'s values were taken as an examples to ranges that state different orders of degrees to be destroyed: descending order from high degrees and ascending order from low degrees and the intermediate degrees. In the right-hand side of the graphs, the four bars demonstrate the fraction of the removed nodes from each degree in each graph. Each bar is shown by a symbol respective to the symbol of the graph that it represents. Inset in panels (c) and (d): Closeup of the region where there are several curves that intersect the $x$ axis very closely. In accordance with our prediction, the curves that represent our method (rectangles) intersect the $x$ axis at the lowest point compared to the other curves.

Figure 3

Behavior of the size of the giant component in SF networks: Open symbols represent simulations results of SF networks having $N={10}^3$ nodes. The exponent $\gamma$ in the distribution $p\left(k\right)=C{k}^{-\gamma }$ is 2.8. [(a), (b)] Cost function $c\left(k\right)$ is power law with (a) $\alpha =1.0$, (b) $\alpha =3.2$. [(c), (d)] Cost function $c\left(k\right)$ is exponential with (c) $\beta =0.01$, (d) $\beta =2.5$. In each of the graphs the order of choosing the degrees to be removed is identical to the graphs in Fig. 2, except the curves that are signed by circles where only 1% (and not 5% as in Fig. 2) of the nodes with the highest degrees are not removed. For the convenience, the bars in the right side of each figure were truncated arbitrarily above $k=20$, but in fact they include also the hubs with degrees up to about $k=40$. Inset in (b): Closeup of the region where there are two curves that intersect the $x$ axis very closely. In accordance with our prediction, the curve that represents our method (rectangles) intersects the $x$ axis at the lowest point compared to the other curves.