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) PDF of nodes belonging to the ks-th shell. The total number of shells is 25 and the most populated shell is ks = 7. (b) Ratio of the number of nodes for each shell that did not survive the 10,000 trials. (c) Median of the survival rate for each shell for ranging from ks ≥ 9. Error bars are plotted using quartile deviation. The guideline shows Ps ∝ exp(Bks) where B = 0.16. (d) Schematic figure of the degree of decomposition in k-shell decomposition analysis. Each plate shows the shell (ks = 1 (blue); 2 (green); 3 (pink)). Focusing on the white node, the red links are oriented towards a higher shell, and their number is denoted by ku. The green links are oriented in the same shell, and their number is km. The blue links are oriented to a lower shell, and their number is kd.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g010: (a) PDF of nodes belonging to the ks-th shell. The total number of shells is 25 and the most populated shell is ks = 7. (b) Ratio of the number of nodes for each shell that did not survive the 10,000 trials. (c) Median of the survival rate for each shell for ranging from ks ≥ 9. Error bars are plotted using quartile deviation. The guideline shows Ps ∝ exp(Bks) where B = 0.16. (d) Schematic figure of the degree of decomposition in k-shell decomposition analysis. Each plate shows the shell (ks = 1 (blue); 2 (green); 3 (pink)). Focusing on the white node, the red links are oriented towards a higher shell, and their number is denoted by ku. The green links are oriented in the same shell, and their number is km. The blue links are oriented to a lower shell, and their number is kd.

Mentions: For a more detailed characterization of the structure of this business transaction network, we apply k-shell decomposition analysis [35] to the network to calculate the number of shells in the network and number of nodes in each shell. We define a k-shell as the set of nodes belonging to the k-core but not to the (k+1)-core, where k-core is defined by the maximal sub-graph having a minimal link number k. This decomposition characterizes the importance of nodes in a complex network structure. As a result, we find that the business relation network is decomposed into 25 shells. We assign an integer index ks to each node that represents the shell number to which the node belongs. As shown in Fig 10(a), the distribution of shell numbers is maximum at ks = 7, and there are 1,346 nodes with the largest index ks = 25. The number of nodes at the periphery (ks = 1) is very small because we extracted the LSCC from raw network data.


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) PDF of nodes belonging to the ks-th shell. The total number of shells is 25 and the most populated shell is ks = 7. (b) Ratio of the number of nodes for each shell that did not survive the 10,000 trials. (c) Median of the survival rate for each shell for ranging from ks ≥ 9. Error bars are plotted using quartile deviation. The guideline shows Ps ∝ exp(Bks) where B = 0.16. (d) Schematic figure of the degree of decomposition in k-shell decomposition analysis. Each plate shows the shell (ks = 1 (blue); 2 (green); 3 (pink)). Focusing on the white node, the red links are oriented towards a higher shell, and their number is denoted by ku. The green links are oriented in the same shell, and their number is km. The blue links are oriented to a lower shell, and their number is kd.
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g010: (a) PDF of nodes belonging to the ks-th shell. The total number of shells is 25 and the most populated shell is ks = 7. (b) Ratio of the number of nodes for each shell that did not survive the 10,000 trials. (c) Median of the survival rate for each shell for ranging from ks ≥ 9. Error bars are plotted using quartile deviation. The guideline shows Ps ∝ exp(Bks) where B = 0.16. (d) Schematic figure of the degree of decomposition in k-shell decomposition analysis. Each plate shows the shell (ks = 1 (blue); 2 (green); 3 (pink)). Focusing on the white node, the red links are oriented towards a higher shell, and their number is denoted by ku. The green links are oriented in the same shell, and their number is km. The blue links are oriented to a lower shell, and their number is kd.
Mentions: For a more detailed characterization of the structure of this business transaction network, we apply k-shell decomposition analysis [35] to the network to calculate the number of shells in the network and number of nodes in each shell. We define a k-shell as the set of nodes belonging to the k-core but not to the (k+1)-core, where k-core is defined by the maximal sub-graph having a minimal link number k. This decomposition characterizes the importance of nodes in a complex network structure. As a result, we find that the business relation network is decomposed into 25 shells. We assign an integer index ks to each node that represents the shell number to which the node belongs. As shown in Fig 10(a), the distribution of shell numbers is maximum at ks = 7, and there are 1,346 nodes with the largest index ks = 25. The number of nodes at the periphery (ks = 1) is very small because we extracted the LSCC from raw network data.

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