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
Schematic figures of the percolation process of a complete graph.In our simulation, an initial state (f = 0) is chosen as an ER-graph with a link density p between p = pc and 1, and we consider removal process of links toward p = 0(f = 1).
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g008: Schematic figures of the percolation process of a complete graph.In our simulation, an initial state (f = 0) is chosen as an ER-graph with a link density p between p = pc and 1, and we consider removal process of links toward p = 0(f = 1).

Mentions: In the previously described simulation, we regard the ER-graphs as the initial states (f = 0), in which the link density, p, is given by 2M/(N(N−1)), as schematically shown in Fig 8. In the theory of ER-graphs, the critical point of percolation phase transition is given by pc = 1/N [33], and the relation between f and p is as follows:p=1-N(N-1)2-M+mN(N-1)2=2M(1-f)N(N-1)(10)where N(N−1)/2−M is the difference of link numbers between the complete graph and initial ER-graph with M links, m is the number of links removed from the initial state (f = 0), and f = m/M. As the critical point of the ER-graph is given by pc = 1/N, we have the following relation:1-fc=N-12M(11)Under our finite size scaling assumption, M ∝ Nϕ, we obtain the following equation:1-fc∝M-1+1/Φ(12)This equation is consistent with Eq (9). Therefore, we understand that the scaling relations, Eq (9), is a natural generalization of the percolation theory of ER-graphs to more general complex networks.


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)

Schematic figures of the percolation process of a complete graph.In our simulation, an initial state (f = 0) is chosen as an ER-graph with a link density p between p = pc and 1, and we consider removal process of links toward p = 0(f = 1).
© Copyright Policy
Related In: Results  -  Collection

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

pone.0119979.g008: Schematic figures of the percolation process of a complete graph.In our simulation, an initial state (f = 0) is chosen as an ER-graph with a link density p between p = pc and 1, and we consider removal process of links toward p = 0(f = 1).
Mentions: In the previously described simulation, we regard the ER-graphs as the initial states (f = 0), in which the link density, p, is given by 2M/(N(N−1)), as schematically shown in Fig 8. In the theory of ER-graphs, the critical point of percolation phase transition is given by pc = 1/N [33], and the relation between f and p is as follows:p=1-N(N-1)2-M+mN(N-1)2=2M(1-f)N(N-1)(10)where N(N−1)/2−M is the difference of link numbers between the complete graph and initial ER-graph with M links, m is the number of links removed from the initial state (f = 0), and f = m/M. As the critical point of the ER-graph is given by pc = 1/N, we have the following relation:1-fc=N-12M(11)Under our finite size scaling assumption, M ∝ Nϕ, we obtain the following equation:1-fc∝M-1+1/Φ(12)This equation is consistent with Eq (9). Therefore, we understand that the scaling relations, Eq (9), is a natural generalization of the percolation theory of ER-graphs to more general complex networks.

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