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
Examples of typical clusters; (a) f < fc, (b) f = fc and (c) f > fc. Bridge links and loop links are shown in blue and red, respectively. (d) Ratio of bridge links (blue line) and loop links (broken red line) in the largest cluster. (e) Probability that the largest cluster has a loop. The broken black line shows the critical point. Results are estimated for 100 trials.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g005: Examples of typical clusters; (a) f < fc, (b) f = fc and (c) f > fc. Bridge links and loop links are shown in blue and red, respectively. (d) Ratio of bridge links (blue line) and loop links (broken red line) in the largest cluster. (e) Probability that the largest cluster has a loop. The broken black line shows the critical point. Results are estimated for 100 trials.

Mentions: The mean-field approximation of percolation theory is based on the assumption of the loopless tree structure, and its applicability is directly checked numerically. Parts of typical network configurations are shown in Fig 5(a), 5(b) and 5(c) for cases where f < fc, f = fc and f > fc, respectively. We see in these figures that a large number of loop links, drawn in red, are below the transition point, and that all links above the critical point are bridge links. In Fig 5(d), we plot the ratio of the number of bridge links Rb to that of loop links Rl = 1−Rb as a function of f for the original LSCC. For very small values of f, almost all links are loop links, and Rl decreases gradually before rapidly decaying to 0 for values of f close to 1. In order to observe the behavior of the system around f = 1 in detail, we calculate the probability PL that the largest cluster has at least one loop by repeating the simulation 100 times, as shown in Fig 5(e). We show that this probability abruptly decreases to 0 around the transition point, i.e., the percolation transition point is also the loop-less transition point. Around the critical point, the contribution of loops is very small. Therefore, the mean-field approximation becomes exact such that the critical exponents belong to the mean-field university class.


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)

Examples of typical clusters; (a) f < fc, (b) f = fc and (c) f > fc. Bridge links and loop links are shown in blue and red, respectively. (d) Ratio of bridge links (blue line) and loop links (broken red line) in the largest cluster. (e) Probability that the largest cluster has a loop. The broken black line shows the critical point. Results are estimated for 100 trials.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g005: Examples of typical clusters; (a) f < fc, (b) f = fc and (c) f > fc. Bridge links and loop links are shown in blue and red, respectively. (d) Ratio of bridge links (blue line) and loop links (broken red line) in the largest cluster. (e) Probability that the largest cluster has a loop. The broken black line shows the critical point. Results are estimated for 100 trials.
Mentions: The mean-field approximation of percolation theory is based on the assumption of the loopless tree structure, and its applicability is directly checked numerically. Parts of typical network configurations are shown in Fig 5(a), 5(b) and 5(c) for cases where f < fc, f = fc and f > fc, respectively. We see in these figures that a large number of loop links, drawn in red, are below the transition point, and that all links above the critical point are bridge links. In Fig 5(d), we plot the ratio of the number of bridge links Rb to that of loop links Rl = 1−Rb as a function of f for the original LSCC. For very small values of f, almost all links are loop links, and Rl decreases gradually before rapidly decaying to 0 for values of f close to 1. In order to observe the behavior of the system around f = 1 in detail, we calculate the probability PL that the largest cluster has at least one loop by repeating the simulation 100 times, as shown in Fig 5(e). We show that this probability abruptly decreases to 0 around the transition point, i.e., the percolation transition point is also the loop-less transition point. Around the critical point, the contribution of loops is very small. Therefore, the mean-field approximation becomes exact such that the critical exponents belong to the mean-field university class.

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