Discontinuity, Nonlinearity, and Complexity
Critical Phase in Complex Networks: a Numerical Study
Discontinuity, Nonlinearity, and Complexity 3(3) (2014) 319346  DOI:10.5890/DNC.2014.09.008
Takehisa Hasegawa$^{1}$, Tomoaki Nogawa$^{2}$, Koji Nemoto$^{3}$
$^{1}$ Graduate School of Information Sciences, Tohoku University, 6309, AramakiAzaAoba, Sendai, 9808579, JAPAN
$^{2}$ Faculty of Medicine, Toho University, 52116, Omorinishi, Otaku, Tokyo 1438540, JAPAN
$^{3}$ Department of Physics, Hokkaido University, Kita 10 Nishi 8, Kitaku, Sapporo, Hokkaido, 0600810, JAPAN
Download Full Text PDF
Abstract
We compare phase transition and critical phenomena of bond percolation on Euclidean lattices, nonamenable graphs, and complex networks. On a Euclidean lattice, percolation showsa phase transition between the nonpercolating phase and percolating phase at the critical point. The critical point is stretched to a finite region, called the critical phase, on nonamenable graphs. To investigate the critical phase, we introduce a fractal exponent, which characterizes a subextensive order of the system. We perform the Monte Carlo simulations for percolation on two nonamenable graphs – the binary tree and the enhanced binary tree. The former shows the nonpercolating phase and the critical phase, whereas the latter shows all three phases. We also examine the possibility of critical phase in complex networks. Our conjecture is that networks with a growth mechanism have only the critical phase and the percolating phase. We study percolation on a stochastically growing network with and without a preferential attachment mechanism, and a deterministically growing network, called the decorated flower, to show that the critical phase appears in those models. We provide afinitesize scaling by using the fractal exponent, which would be a powerful method for numerical analysis of the phase transition involving the critical phase.
Acknowledgments
This work was partially supported by the GrantinAid for Young Scientists (B) of Japan Society for the Promotion of Science (Grant No. 24740054 to T.H.) and JST, ERATO, Kawarabayashi Large Graph Project.
References

[1]  Albert, R. and Barabási, A.L. (2002), Statistical mechanics of complex networks, Reviews of Modern Physics, 74, 4797. 

[2]  Newman, M.E.J. (2003), The structure and function of complex networks, SIAM Review, 45, 167256. 

[3]  Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., and Hwang, D.U. (2006), Complex networks: Structure and dynamics, Physics Reports, 424, 175308. 

[4]  Barrat, A., Barthélemy, M., and Vespignani, A.(2008), Dynamical processes on complex networks, Cambridge University Press, Cambridge. 

[5]  Watts, D.J. and Strogatz, S.H. (1998), Collective dynamics of 'smallworld' networks, Nature, 393, 440442. 

[6]  Barabási, A.L. and Albert, R.(1999), Emergence of scaling in random networks, Science, 286, 509512. 

[7]  Dorogovtsev, S.N., Goltsev, A.V., and Mendes, .J.F.F. (2008), Critical phenomena in complex networks, Reviews of Modern Physics, 80, 12751335. 

[8]  Nogawa, T. and Hasegawa, T. (2009), Monte Carlo simulation study of the twostage percolation transition, Journal of Physics A: Mathematical and Theoretical, 42, 145001. 

[9]  Nogawa, T. and Hasegawa, T. (2009), Reply to the comment on 'monte carlo simulation study of the twostage percolation transition in enhanced binary trees', Journal of Physics A: Mathematical and Theoretical, 42, 478002. 

[10]  Hasegawa, T. and Nemoto, K. (2010), Critical phase of bond percolation on growing networks. Physical Review E, 81, 051105. 

[11]  Hasegawa, T., Sato, M., and Nemoto, K. (2010), Generatingfunction approach for bond percolation in hierarchical networks, Physical Review E, 82, 046101. 

[12]  Nogawa, T., Hasegawa, T., and Nemoto, K. (2012), Generalized scaling theory for critical phenomena including essential singularities and infinite dimensionality, Physical Review Letters, 108, 255703. 

[13]  Nogawa, T., Hasegawa, T., and Nemoto, K. (2012), Criticality governed by the stable renormalization fixed point of the ising model in the hierarchical smallworld network, Physical Review E, 86, 030102. 

[14]  Hasegawa, T. and Nogawa, T. (2013), Absence of the nonpercolating phase for percolation on the nonplanar hanoi network, Physical Review E, 87, 032810. 

[15]  Hasegawa, T., Nogawa, T., and Nemoto, K. (2013), Profile and scaling of the fractal exponent of percolations in complex networks, EPL (Europhysics Letters), 104, 16006. 

[16]  Nogawa, T. and Hasegawa, T. (2013), Metatransition between an inverted bkt transition and an abrupt transition in the bond percolation on a random hierarchical smallworld network, arXiv:1312.4697. 

[17]  Stauffer, D. and Aharony, A. (1994), Introduction to percolation theory, Taylor and Francis. 

[18]  Benjamini, I. and Schramm, O. (1996), Percolation beyond zd, many questions and a few answers, Electronic Communications in Probability, 1, 71. 

[19]  R. Lyons. Phase transitions on nonamenable graphs. Journal of Mathematical Physics, 41:1099, 2000. 

[20]  Schonmann, R.H. (2001), Multiplicity of phase transitions and meanfield criticality on highly nonamenable graphs, Communications in Mathematical Physics, 219, 271322. 

[21]  Burton, R.M. and Keane, M. (1989), Density and uniqueness in percolation, Communications in Mathematical Physics, 121, 501505. 

[22]  Mohar, B. (1991), Some relations between analytic and geometric properties of infinite graphs,. Discrete mathematics, 95, 193219. 

[23]  Benjamini, I. and Schramm, O. (2001), Percolation in the hyperbolic plane, Journal of the American Mathematical Society, 14, 487507. 

[24]  Dorogovtsev, S.N., Mendes, J.F.F., and Samukhin, A.N. (2001), Sizedependent degree distribution of a scalefree growing network. Physical Review E, 63, 062101. 

[25]  Eggarter, T.P. (1974), Cayley trees, the ising problem, and the thermodynamic limit. Physical Review B, 9, 2989. 

[26]  MüllerHartmann, E. and Zittartz, J. (1974), New type of phase transition, Physical Review Letters, 33, 893. 

[27]  Baek, S. K., Minnhagen, P., and Kim, B.J. (2009), Comment on 'monte carlo simulation study of the twostage percolation transition in enhanced binary trees', Journal of Physics A: Mathematical and Theoretical, 42, 478001. 

[28]  Minnhagen, P. and Baek, S.K. (2010), Analytic results for the percolation transitions of the enhanced binary tree, Physical Review E, 82, 011113. 

[29]  Gu, H. and Ziff, R.M. (2012), Crossing on hyperbolic lattices, Physical Review E, 85, 051141. 

[30]  Baek, S.K. (2012), Upper transition point for percolation on the enhanced binary tree: A sharpened lower bound, Physical Review E, 85, 051128. 

[31]  Baek, S.K., Minnhagen, P., and Kim, B.J. (2009), Percolation on hyperbolic lattices, Physical Review E, 79, 011124. 

[32]  Lee, J.F. and Baek, S.K. (2012), Bounds of percolation thresholds on hyperbolic lattices, Physical Review E, 86, 062105. 

[33]  Albert, R., Jeong, H., and Barabási, A.L. (2000), Error and attack tolerance of complex networks, Nature, 406, 378382. 

[34]  Cohen, R., Erez, K., ben Avraham, D., and Havlin, S. (2000), Resilience of the internet to random breakdowns, Physical Review Letters, 85, 4626. 

[35]  Cohen, R., ben Avraham, D., and Havlin, S. (2002), Percolation critical exponents in scalefree networks, Physical Review E, 66, 036113. 

[36]  Molloy, M. and Reed, B. (1995), A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, 6, 161180. 

[37]  Callaway, D.S., Newman, M.E.J., Strogatz, S.H., andWatts, D.J. (2000), Network robustness and fragility: Percolation on random graphs, Physical Review Letters, 85, 54685471. 

[38]  Cohen, R., Erez, K., ben Avraham, D., and Havlin, S.(2001), Breakdown of the internet under intentional attack, Physical Review Letters, 86, 36823685. 

[39]  Goltsev, A.V., Dorogovtsev, S.N., and Mendes, J.F.F. (2008), Percolation on correlated networks, Physical Review E, 78, 051105. 

[40]  Tanizawa, T., Havlin, S., and Stanley, H.E. (2012), Robustness of onionlike correlated networks against targeted attacks, Physical Review E, 85, 046109. 

[41]  Newman, M.E.J., Properties of highly clustered networks, Physical Review E, 68, 026121. 

[42]  Gleeson, J.P. (2009), Bond percolation on a class of clustered random networks, Physical Review E, 80, 036107. 

[43]  Gleeson, J.P. and Melnik, S. (2009), Analytical results for bond percolation and kcore sizes on clustered networks, Physical Review E, 80, 046121. 

[44]  Gleeson, J.P., Melnik, S., and Hackett, A. (2010), How clustering affects the bond percolation threshold in complex networks, Physical Review E, 81, 066114. 

[45]  Callaway, D.S., Hopcroft, J.E., Kleinberg, J.M., Newman, M.E.J., and Strogatz, S.H. (2001), Are randomly grown graphs really random? Physical Review E, 64, 041902. 

[46]  Dorogovtsev, S.N., Mendes, J.F.F., and Samukhin, A.N. (2001), Anomalous percolation properties of growing networks, Physical Review E, 64, 066110. 

[47]  Lancaster, D. (2002), Cluster growth in two growing network models, Journal of Physics A: Mathematical and General, 35, 1179. 

[48]  Kim, J., Krapivsky, P.L., Kahng, B., and Redner, S.(2002), Infiniteorder percolation and giant fluctuations in a protein interaction network, Physical Review E, 66, 055101. 

[49]  Coulomb, S. and Bauer, M. (2003), Asymmetric evolving random networks, The European Physical Journal BCondensed Matter and Complex Systems, 35, 377389. 

[50]  Zalányi, L., Csárdi, G., Kiss, T., Lengyel, M., Warner, R., Tobochnik, J., and Érdi, P. (2003), Properties of a random attachment growing network, Physical Review E, 68, 066104. 

[51]  Krapivsky, P.L. and Derrida, B. (2004), Universal properties of growing networks, Physica A: Statistical Mechanics and its Applications, 340, 714724. 

[52]  Bollobás, B. and Riordan, O. (2004), The phase transition and connectedness in uniformly grown random graphs, 3243, 118. 

[53]  Bollobás, B., Janson, S., and Riordan, O. (2005), The phase transition in the uniformly grown random graph has infinite order, Random Structures & Algorithms, 26, 136. 

[54]  Bollobás, B. and Riordan, O. (2005), Slow emergence of the giant component in the growing mout graph, Random Structures & Algorithms, 27, 124. 

[55]  Riordan, O. (2005), The small giant component in scalefree random graphs, Combinatorics Probability and Computing, 14, 897938. 

[56]  Pietsch, W. (2006), Derivation of the percolation threshold for the network model of barabási and albert, Physical Review E, 73, 066112. 

[57]  Zhang, Z., Zhou, S., Zhao, S., and Guan, J.(2008), Degree and component size distributions in the generalized uniform recursive tree, Journal of Physics A: Mathematical and Theoretical, 41, 185101. 

[58]  Dorogovtsev, S.N., Mendes, J.F.F., and Samukhin, A.N. (2000), Structure of growing networks with preferential linking. Physical Review Letters, 85, 4633. 

[59]  Krapivsky, P.L., Redner, S., and Leyvraz, F. (2000), Connectivity of growing random networks, Physical Review Letters, 85, 4629. 

[60]  Janson, S., Knuth, D.E., Łuczak, T., and Pittel, B. (1993), The birth of the giant component, Random Structures & Algorithms, 4, 233358. 

[61]  Auto, D.M., Moreira, A.A., Herrmann, H.J., and Andrade Jr., J.S. (2008), Finitesize effects for percolation on apollonian networks, Physical Review E, 78, 066112. 

[62]  Dorogovtsev, S.N. (2003), Renormalization group for evolving networks, Physical Review E, 67, 045102. 

[63]  Rozenfeld, H.D., Havlin, S., and BenAvraham, D. (2007), Fractal and transfractal recursive scalefree nets. New Journal of Physics, 9, 175. 

[64]  Rozenfeld, H.D. and ben Avraham, D. (2007), Percolation in hierarchical scalefree nets, Physical Review E, 75, 061102. 

[65]  Hinczewski, M. and Berker, A.N. (2006), Inverted berezinskiikosterlitzthouless singularity and hightemperature algebraic order in an ising model on a scalefree hierarchicallattice smallworld network, Physical Review E, 73, 066126. 

[66]  Berker, A.N., Hinczewski, M., and Netz, R.R. (2009), Critical percolation phase and thermal berezinskiikosterlitzthouless transition in a scalefree network with shortrange and longrange random bonds, Physical Review E, 80, 041118. 

[67]  Boettcher, S., Singh, V., and Ziff, R. M. (2012), Ordinary percolation with discontinuous transitions. Nature Communications, 3, 787. 

[68]  Zhang, Z. and Comellas, F. (2011), Farey graphs as models for complex networks,. Theoretical Computer Science, 412(8), 865875. 

[69]  Boettcher, S., Cook, J.L., and Ziff, R.M. (2009), Patchy percolation on a hierarchical network with smallworld bonds, Physical Review E, 80, 041115. 

[70]  Hong, H., Ha, M., and Park, H. (2007), Finitesize scaling in complex networks, Physical Review Letters, 98, 258701. 

[71]  Wu, C.C. (1996), Ising models on hyperbolic graphs, Journal of statistical physics, 85, 251259. 

[72]  Wu, C.C. (2000), Ising models on hyperbolic graphs ii, Journal of Statistical Physics, 100, 893904. 

[73]  Shima, H. and Sakaniwa, Y. (2006), Geometric effects on critical behaviours of the ising model, Journal of Physics A: Mathematical and General, 39, 4921. 

[74]  Shima, H. and Sakaniwa, Y. (2006), The dynamic exponent of the ising model on negatively curved surfaces, Journal of Statistical Mechanics: Theory and Experiment, 2006, P08017. 

[75]  Sakaniwa, Y. and Shima, H. (2009), Survival of shortrange order in the ising model on negatively curved surfaces. Physical Review E, 80, 021103. 

[76]  Ueda, K., Krcmar, R., Gendiar, A., and Nishino, T. (2007), Corner transfer matrix renormalization group method applied to the ising model on the hyperbolic plane, Journal of the Physical Society of Japan, 76, 084004. 

[77]  Krcmar, R., Gendiar, A., Ueda, K., and Nishino, T. (2008), Ising model on a hyperbolic lattice studied by the corner transfer matrix renormalization group method, Journal of Physics A: Mathematical and Theoretical, 41, 125001. 

[78]  Iharagi, T., Gendiar, A., Ueda, H., and Nishino, T. (2010), Phase transition of the ising model on a hyperbolic lattice, Journal of the Physical Society of Japan, 79, 104001. 

[79]  Gendiar, A., Krcmar, R., Andergassen, S., Dani’ska, M., and Nishino, T. (2012), Weak correlation effects in the ising model on triangulartiled hyperbolic lattices, Physical Review E, 86, 021105. 

[80]  Bauer, M., Coulomb, S. and Dorogovtsev, S.N. (2005), Phase transition with the berezinskiikosterlitzthouless singularity in the ising model on a growing network, Physical Review Letters, 94, 200602. 

[81]  Boettcher, S., and Brunson, C.T. (2011), Fixedpoint properties of the ising ferromagnet on the hanoi networks. Physical Review E, 83, 021103. 

[82]  Boettcher, S. and Brunson, C.T. (2011), Renormalization group for critical phenomena in complex networks. Frontiers in Physiology, 2. 

[83]  Boettcher, S. and Brunson, C.T. (2012), Classification of critical phenomena having a parameterdependent renormalization, arXiv:1209.3447. 

[84]  Pemantle, R. (1992), The contact process on trees, The Annals of Probability, 20892116. 

[85]  Liggett, T.M. (1996), Multiple transition points for the contact process on the binary tree, The Annals of Probability, 24(4), 16751710. 

[86]  Stacey, A.M. (1996), The existence of an intermediate phase for the contact process on trees, The Annals of Probability, 17111726. 