Limits...
Precise calculation of a bond percolation transition and survival rates of nodes in a complex network.

Kawamoto H, Takayasu H, Jensen HJ, Takayasu M - PLoS ONE (2015)

Bottom Line: As an example of a real-world network, we apply our analysis to a business relation network consisting of approximately 3,000,000 links among 300,000 firms and observe the transition with critical exponents close to the mean-field values taking into account the finite size effect.We focus on the largest cluster at the critical point, and introduce survival probability as a new measure characterizing the robustness of each node.We also discuss the relation between survival probability and k-shell decomposition.

View Article: PubMed Central - PubMed

Affiliation: Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, Midori-ku, Yokohama, Japan.

ABSTRACT
Through precise numerical analysis, we reveal a new type of universal loopless percolation transition in randomly removed complex networks. As an example of a real-world network, we apply our analysis to a business relation network consisting of approximately 3,000,000 links among 300,000 firms and observe the transition with critical exponents close to the mean-field values taking into account the finite size effect. We focus on the largest cluster at the critical point, and introduce survival probability as a new measure characterizing the robustness of each node. We also discuss the relation between survival probability and k-shell decomposition.

Show MeSH
(a) Order parameter R in the whole range of f. (b) Order parameter R in the range of f between 0.97 and 1.00. Circles and squares specify values below and above the critical point, respectively. (Inset) Log-log plots of R vs. f′−f. f′ < fc (circles), f′ = fc (triangles), and f′ > fc (squares). The grey guideline shows the power law with critical exponent β = 1.0. Error bars estimated by the interquartile range (IQR) from 100 trials using different random number seeds are plotted (all error bars are within the size of plotted squares.). (c) Normalized second largest cluster size T below the critical point (circles), and the average cluster size S above the critical point (squares). (Inset) Average cluster size S and f−fc in log-log scale. The grey guideline shows the slope for the critical exponent γ = 1.0. (d) Cumulative cluster size distributions in log-log scale. The dot-dash, bold and dash lines show values below, at, and above the critical point, respectively. The guideline shows a slope of 1.5, corresponding to the critical exponent τ = 2.5. The results are a superposition of 10 trials.
© Copyright Policy
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4401659&req=5

pone.0119979.g002: (a) Order parameter R in the whole range of f. (b) Order parameter R in the range of f between 0.97 and 1.00. Circles and squares specify values below and above the critical point, respectively. (Inset) Log-log plots of R vs. f′−f. f′ < fc (circles), f′ = fc (triangles), and f′ > fc (squares). The grey guideline shows the power law with critical exponent β = 1.0. Error bars estimated by the interquartile range (IQR) from 100 trials using different random number seeds are plotted (all error bars are within the size of plotted squares.). (c) Normalized second largest cluster size T below the critical point (circles), and the average cluster size S above the critical point (squares). (Inset) Average cluster size S and f−fc in log-log scale. The grey guideline shows the slope for the critical exponent γ = 1.0. (d) Cumulative cluster size distributions in log-log scale. The dot-dash, bold and dash lines show values below, at, and above the critical point, respectively. The guideline shows a slope of 1.5, corresponding to the critical exponent τ = 2.5. The results are a superposition of 10 trials.

Mentions: The order parameter R is defined as the ratio of the link number of the largest cluster to that of the original LSCC, and the control parameter f is defined as the ratio of the number of removed links to the total number of links in the original LSCC. In Fig 2(a) the value of R is plotted as a function of f. It appears that R decays linearly and moves toward 0 at f = 1. However, by zooming into the range of f between 0.97 and 1.00, as shown in Fig 2(b), we find that the order parameter R becomes approximately 0 at a non-trivial value of f, indicating the existence of a percolation transition. To calculate the position of the transition, we determine the value of f for which the second largest cluster becomes the largest by the removal of a link that divides the largest cluster into two smaller clusters. This value of f is denoted by fc, and it is the critical point. This method is similar to that of estimating the critical point by observing the ratio of the size of the second largest cluster to the size of the largest cluster [31]. We repeat the simulation 100 times with different random numbers and calculate the critical point as fc = 0.994.


Precise calculation of a bond percolation transition and survival rates of nodes in a complex network.

Kawamoto H, Takayasu H, Jensen HJ, Takayasu M - PLoS ONE (2015)

(a) Order parameter R in the whole range of f. (b) Order parameter R in the range of f between 0.97 and 1.00. Circles and squares specify values below and above the critical point, respectively. (Inset) Log-log plots of R vs. f′−f. f′ < fc (circles), f′ = fc (triangles), and f′ > fc (squares). The grey guideline shows the power law with critical exponent β = 1.0. Error bars estimated by the interquartile range (IQR) from 100 trials using different random number seeds are plotted (all error bars are within the size of plotted squares.). (c) Normalized second largest cluster size T below the critical point (circles), and the average cluster size S above the critical point (squares). (Inset) Average cluster size S and f−fc in log-log scale. The grey guideline shows the slope for the critical exponent γ = 1.0. (d) Cumulative cluster size distributions in log-log scale. The dot-dash, bold and dash lines show values below, at, and above the critical point, respectively. The guideline shows a slope of 1.5, corresponding to the critical exponent τ = 2.5. The results are a superposition of 10 trials.
© Copyright Policy
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4401659&req=5

pone.0119979.g002: (a) Order parameter R in the whole range of f. (b) Order parameter R in the range of f between 0.97 and 1.00. Circles and squares specify values below and above the critical point, respectively. (Inset) Log-log plots of R vs. f′−f. f′ < fc (circles), f′ = fc (triangles), and f′ > fc (squares). The grey guideline shows the power law with critical exponent β = 1.0. Error bars estimated by the interquartile range (IQR) from 100 trials using different random number seeds are plotted (all error bars are within the size of plotted squares.). (c) Normalized second largest cluster size T below the critical point (circles), and the average cluster size S above the critical point (squares). (Inset) Average cluster size S and f−fc in log-log scale. The grey guideline shows the slope for the critical exponent γ = 1.0. (d) Cumulative cluster size distributions in log-log scale. The dot-dash, bold and dash lines show values below, at, and above the critical point, respectively. The guideline shows a slope of 1.5, corresponding to the critical exponent τ = 2.5. The results are a superposition of 10 trials.
Mentions: The order parameter R is defined as the ratio of the link number of the largest cluster to that of the original LSCC, and the control parameter f is defined as the ratio of the number of removed links to the total number of links in the original LSCC. In Fig 2(a) the value of R is plotted as a function of f. It appears that R decays linearly and moves toward 0 at f = 1. However, by zooming into the range of f between 0.97 and 1.00, as shown in Fig 2(b), we find that the order parameter R becomes approximately 0 at a non-trivial value of f, indicating the existence of a percolation transition. To calculate the position of the transition, we determine the value of f for which the second largest cluster becomes the largest by the removal of a link that divides the largest cluster into two smaller clusters. This value of f is denoted by fc, and it is the critical point. This method is similar to that of estimating the critical point by observing the ratio of the size of the second largest cluster to the size of the largest cluster [31]. We repeat the simulation 100 times with different random numbers and calculate the critical point as fc = 0.994.

Bottom Line: As an example of a real-world network, we apply our analysis to a business relation network consisting of approximately 3,000,000 links among 300,000 firms and observe the transition with critical exponents close to the mean-field values taking into account the finite size effect.We focus on the largest cluster at the critical point, and introduce survival probability as a new measure characterizing the robustness of each node.We also discuss the relation between survival probability and k-shell decomposition.

View Article: PubMed Central - PubMed

Affiliation: Department of Computational Intelligence and Systems Science, Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, Midori-ku, Yokohama, Japan.

ABSTRACT
Through precise numerical analysis, we reveal a new type of universal loopless percolation transition in randomly removed complex networks. As an example of a real-world network, we apply our analysis to a business relation network consisting of approximately 3,000,000 links among 300,000 firms and observe the transition with critical exponents close to the mean-field values taking into account the finite size effect. We focus on the largest cluster at the critical point, and introduce survival probability as a new measure characterizing the robustness of each node. We also discuss the relation between survival probability and k-shell decomposition.

Show MeSH