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) Cumulative distributions of the survival rate at the critical point (fc = 0.994) of nodes belonging to the largest shell, ks = 25, in the initial state. (b) Schematic figure of calculating the survival rate. Each link is supposed to be removed with the same probability and we compare the sizes of separated clusters. The gray nodes belong to the largest cluster. (c) Cumulative distribution of link numbers at the critical point in a log-log plot. The solid line is calculated only in the largest cluster, and a superposition of 100 trials. The dotted line is calculated for all clusters, and we take superposition of 10 trials. The guide line shows the slope of 1.5, the same slope as Fig 1(a).
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g011: (a) Cumulative distributions of the survival rate at the critical point (fc = 0.994) of nodes belonging to the largest shell, ks = 25, in the initial state. (b) Schematic figure of calculating the survival rate. Each link is supposed to be removed with the same probability and we compare the sizes of separated clusters. The gray nodes belong to the largest cluster. (c) Cumulative distribution of link numbers at the critical point in a log-log plot. The solid line is calculated only in the largest cluster, and a superposition of 100 trials. The dotted line is calculated for all clusters, and we take superposition of 10 trials. The guide line shows the slope of 1.5, the same slope as Fig 1(a).

Mentions: Fig 11(a) shows the distribution of the survival rate of nodes belonging to the 25-shell. This figure suggests that the survival rate of the nodes in this highest shell has wide diversity. In order to understand this diversity, for comparison, we theoretically calculate the survival rate for a Cayley tree, which is a regular tree network with link number K for all nodes, a typical theoretical model of a loopless network. We remove a link as schematically shown in Fig 11(b) and calculate the probability of a node belongings to the largest cluster. Although we will not derive it here, we can show that the survival rate distribution for a Cayley tree of the total link number M is given as, f(Ps) = (k(k−1)/(M+1))exp(−MPs+M−1), an exponential distribution, which is much less diverse than the real survival rate distribution. As discussed in Section 5, the critical clusters, as with those of a Caley tree, are almost loopless; the difference in the survival rate distribution may be caused by the non-uniformity of the link numbers. We can directly observe non-uniformity of link numbers of nodes in the critical clusters as shown in Fig 11(c). We can confirm that the slope of the distribution is smaller for the critical clusters than for the original network shown in Fig 1(a), implying that the link number distribution is highly non-uniform; this result may be a cause for the wide diversity in the survival rate.


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) Cumulative distributions of the survival rate at the critical point (fc = 0.994) of nodes belonging to the largest shell, ks = 25, in the initial state. (b) Schematic figure of calculating the survival rate. Each link is supposed to be removed with the same probability and we compare the sizes of separated clusters. The gray nodes belong to the largest cluster. (c) Cumulative distribution of link numbers at the critical point in a log-log plot. The solid line is calculated only in the largest cluster, and a superposition of 100 trials. The dotted line is calculated for all clusters, and we take superposition of 10 trials. The guide line shows the slope of 1.5, the same slope as Fig 1(a).
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g011: (a) Cumulative distributions of the survival rate at the critical point (fc = 0.994) of nodes belonging to the largest shell, ks = 25, in the initial state. (b) Schematic figure of calculating the survival rate. Each link is supposed to be removed with the same probability and we compare the sizes of separated clusters. The gray nodes belong to the largest cluster. (c) Cumulative distribution of link numbers at the critical point in a log-log plot. The solid line is calculated only in the largest cluster, and a superposition of 100 trials. The dotted line is calculated for all clusters, and we take superposition of 10 trials. The guide line shows the slope of 1.5, the same slope as Fig 1(a).
Mentions: Fig 11(a) shows the distribution of the survival rate of nodes belonging to the 25-shell. This figure suggests that the survival rate of the nodes in this highest shell has wide diversity. In order to understand this diversity, for comparison, we theoretically calculate the survival rate for a Cayley tree, which is a regular tree network with link number K for all nodes, a typical theoretical model of a loopless network. We remove a link as schematically shown in Fig 11(b) and calculate the probability of a node belongings to the largest cluster. Although we will not derive it here, we can show that the survival rate distribution for a Cayley tree of the total link number M is given as, f(Ps) = (k(k−1)/(M+1))exp(−MPs+M−1), an exponential distribution, which is much less diverse than the real survival rate distribution. As discussed in Section 5, the critical clusters, as with those of a Caley tree, are almost loopless; the difference in the survival rate distribution may be caused by the non-uniformity of the link numbers. We can directly observe non-uniformity of link numbers of nodes in the critical clusters as shown in Fig 11(c). We can confirm that the slope of the distribution is smaller for the critical clusters than for the original network shown in Fig 1(a), implying that the link number distribution is highly non-uniform; this result may be a cause for the wide diversity in the survival rate.

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