Structural robustness of scale-free networks against overload failures

Shogo Mizutaka and Kousuke Yakubo

Phys. Rev. E 88, 012803 – Published 8 July 2013

Abstract

We study the structural robustness of scale-free networks against overload failures induced by loads exceeding the node capacity, based on analytical and numerical approaches to the percolation problem in which a fixed number of nodes are removed according to the overload probability. Modeling fluctuating loads by random walkers in a network, we find that the degree dependence of the overload probability drastically changes with respect to the total load. We also elucidate that there exist two types of structural robustness of networks against overload failures. One is measured by the critical total load $W_{c}$ and the other is by the critical node removal fraction $f_{c}$ . Enhancing the scale-free property, networks become fragile in both senses of $W_{c}$ and $f_{c}$ . By contrast, increasing the node tolerance, scale-free networks become robust in the sense of the critical total load, while they come to be fragile in the sense of the critical node removal fraction. Furthermore, we show that these trends are not affected by degree-degree correlations, although assortative mixing makes networks robust in both senses of $W_{c}$ and $f_{c}$ .

Received 21 March 2013

DOI:https://doi.org/10.1103/PhysRevE.88.012803

Authors & Affiliations

Shogo Mizutaka^* and Kousuke Yakubo^†

Department of Applied Physics, Hokkaido University, Sapporo 060-8628, Japan

^*s.mizutaka@eng.hokudai.ac.jp
^†yakubo@eng.hokudai.ac.jp

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 88, Iss. 1 — July 2013

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Profiles of the overload probability $F_{W} (k)$ for various values of $W$ . The thin line at the bottom shows $F_{W} (k)$ at $W = W_{0}$ . The thick black lines from the top show the profiles of $F_{W} (k)$ for $W = 2 W_{0}$ , $1.5 W_{0}$ , $1.3 W_{0}$ , $1.1 W_{0}$ , and $1.05 W_{0}$ , respectively. The parameter $m$ is fixed at $m = 4$ for these lines. The thick gray line represents $F_{W} (k)$ for $W = 1.628 W_{0}$ and $m = 6.0$ . The initial total load $W_{0}$ is set at $W_{0} = 2 M$ with $M = 200 000$ . The zigzag structure in these curves is due to the quantity $[q_{k} (W_{0})]$ in Eq. (8).Reuse & Permissions
Figure 2
Degree distribution function $P (k)$ given by Eq. (12) with $γ = 3.0$ and $d = 4.0$ . The average degree of this distribution function is $〈 k 〉 = 4.44$ . The inset shows the $d$ dependence of $〈 k 〉$ for $γ = 2.5$ , $3.0$ , and $4.0$ from top to bottom, respectively.Reuse & Permissions
Figure 3
Numerical confirmation of the analytical treatment. The symbols represent the numerically calculated order parameter $S$ (the number of nodes in the giant component divided by the total node number $N$ ) as a function of (a) the rescaled total load $W / W_{0}$ and (b) the node removal fraction $f$ , where $W_{0}$ is the initial total load. The degree distribution $P (k)$ is given by Eq. (12) with $γ = 2.5$ and $d = 5.8272$ ( $〈 k 〉 = 10.0$ ) and the generalized random graph for the numerical calculations contains $N = 10 000$ nodes. The overload failure occurs under the condition of $m = 2$ and $W_{0} = 2 M$ , where $M$ is the number of edges. The numerical results are averaged over 50 samples. The vertical dashed lines represent the critical total load $W_{c} / W_{0} = 1.912$ and the critical removal fraction $f_{c} = 0.547$ obtained theoretically by Eqs. (10) and (11).Reuse & Permissions
Figure 4
Critical total load $W_{c}$ rescaled by the initial load $W_{0}$ as a function of the scale-free exponent $γ$ . The result is analytically calculated for the scale-free random graphs whose degree distribution is described by Eq. (12) with the fixed average degree $〈 k 〉 = 10.0$ and by setting $m = 2$ and $W_{0} = 2 M$ . The solid, dashed, and dotted lines in the inset show the $γ$ dependence of the critical node removal fraction $f_{c}$ for overload failures, random failures, and targeted attacks, respectively.Reuse & Permissions
Figure 5
Rescaled critical total load $W_{c} / W_{0}$ (upper panel) and the critical node removal fraction $f_{c}$ (lower panel) as a function of the node tolerance parameter $m$ . The dashed and dotted lines represent the analytical results for the scale-free random graphs (SF) described by Eq. (12) with $γ = 4.5$ and $2.5$ , respectively. The solid lines indicate the results for the Erdős-Rényi random graph (RG). We set $〈 k 〉 = 10.0$ and $W_{0} = 2 M$ as in the case of Fig. 4.Reuse & Permissions
Figure 6
Critical node removal fraction $f_{c}$ as a function of the Pearson correlation coefficient $r$ . The parameters used for the calculations are given in the text. The three lines indicate the results for $m = 2$ , 4, and 6 from top to bottom, respectively.Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics