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

Related in: MedlinePlus

(a) Normalized size of the largest cluster Rc at the critical point for each network shown in Fig 3(b). The line shows the slope for Rc ∝ M−δ, δ = 0.50. Colors are the same as in Fig 3(b). (b) Number of clusters at the critical point for each network shown in Fig 3(b). The line shows the slope for Ns ∝ Mρ, ρ = 0.77. (c) Critical link density as a function of M for each network shown in Fig 3(b). The line shows the slope for 1−fc ∝ M−ε, ε = 0.23. The number of trials ranges from 1,000 to 100,000, depending on convergence speed for each network. The error bars indicate the interquartile range (IQR). (d) Critical link density on Erdös-Rényi graph (ER-graph), ϕ = 1.5 (triangles), ϕ = 1.7 (squares), and ϕ = 2.0 (circles). The number of trials ranges from 1,000 to 100,000, depending on convergence speed for each network.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g007: (a) Normalized size of the largest cluster Rc at the critical point for each network shown in Fig 3(b). The line shows the slope for Rc ∝ M−δ, δ = 0.50. Colors are the same as in Fig 3(b). (b) Number of clusters at the critical point for each network shown in Fig 3(b). The line shows the slope for Ns ∝ Mρ, ρ = 0.77. (c) Critical link density as a function of M for each network shown in Fig 3(b). The line shows the slope for 1−fc ∝ M−ε, ε = 0.23. The number of trials ranges from 1,000 to 100,000, depending on convergence speed for each network. The error bars indicate the interquartile range (IQR). (d) Critical link density on Erdös-Rényi graph (ER-graph), ϕ = 1.5 (triangles), ϕ = 1.7 (squares), and ϕ = 2.0 (circles). The number of trials ranges from 1,000 to 100,000, depending on convergence speed for each network.

Mentions: We introduce three more scaling relations for characterization of the critical point in the initial size of the clipped networks, M. In Fig 7(a) we observe Rc, the value of the order parameter at the critical point, which is given by the largest cluster’s link number divided by the initial link numbers, M. From this log-log plot we find that the scaling relation, Rc ∝ M−δ, holds for δ = 0.50. In Fig 7(b), the number of clusters at the critical point for each clipped network is plotted as a function of M, and we confirm another power law, Ns ∝ Mρ, where ρ is approximately 0.77. In Fig 7(c), the scaling relation for the critical link density, 1−fc ∝ M−ε, holds for ε about 0.23. This relation demonstrates that the critical link density converges to 0 in the large system limit; therefore, we may call this the sparse graph limit transition.


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) Normalized size of the largest cluster Rc at the critical point for each network shown in Fig 3(b). The line shows the slope for Rc ∝ M−δ, δ = 0.50. Colors are the same as in Fig 3(b). (b) Number of clusters at the critical point for each network shown in Fig 3(b). The line shows the slope for Ns ∝ Mρ, ρ = 0.77. (c) Critical link density as a function of M for each network shown in Fig 3(b). The line shows the slope for 1−fc ∝ M−ε, ε = 0.23. The number of trials ranges from 1,000 to 100,000, depending on convergence speed for each network. The error bars indicate the interquartile range (IQR). (d) Critical link density on Erdös-Rényi graph (ER-graph), ϕ = 1.5 (triangles), ϕ = 1.7 (squares), and ϕ = 2.0 (circles). The number of trials ranges from 1,000 to 100,000, depending on convergence speed for each network.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g007: (a) Normalized size of the largest cluster Rc at the critical point for each network shown in Fig 3(b). The line shows the slope for Rc ∝ M−δ, δ = 0.50. Colors are the same as in Fig 3(b). (b) Number of clusters at the critical point for each network shown in Fig 3(b). The line shows the slope for Ns ∝ Mρ, ρ = 0.77. (c) Critical link density as a function of M for each network shown in Fig 3(b). The line shows the slope for 1−fc ∝ M−ε, ε = 0.23. The number of trials ranges from 1,000 to 100,000, depending on convergence speed for each network. The error bars indicate the interquartile range (IQR). (d) Critical link density on Erdös-Rényi graph (ER-graph), ϕ = 1.5 (triangles), ϕ = 1.7 (squares), and ϕ = 2.0 (circles). The number of trials ranges from 1,000 to 100,000, depending on convergence speed for each network.
Mentions: We introduce three more scaling relations for characterization of the critical point in the initial size of the clipped networks, M. In Fig 7(a) we observe Rc, the value of the order parameter at the critical point, which is given by the largest cluster’s link number divided by the initial link numbers, M. From this log-log plot we find that the scaling relation, Rc ∝ M−δ, holds for δ = 0.50. In Fig 7(b), the number of clusters at the critical point for each clipped network is plotted as a function of M, and we confirm another power law, Ns ∝ Mρ, where ρ is approximately 0.77. In Fig 7(c), the scaling relation for the critical link density, 1−fc ∝ M−ε, holds for ε about 0.23. This relation demonstrates that the critical link density converges to 0 in the large system limit; therefore, we may call this the sparse graph limit transition.

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
Related in: MedlinePlus