- 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

Analytical results for bond percolation and k-core sizes on clustered networks

James P. Gleeson and Sergey Melnik

  • Department of Mathematics and Statistics, University of Limerick, Limerick, Ireland

PDF

Phys. Rev. E 80, 046121 – Published 26 October, 2009

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

Abstract

An analytical approach to calculating bond percolation thresholds, sizes of k-cores, and sizes of giant connected components on structured random networks with nonzero clustering is presented. The networks are generated using a generalization of Trapman’s [P. Trapman, Theor. Popul. Biol. 71, 160 (2007)] model of cliques embedded in treelike random graphs. The resulting networks have arbitrary degree distributions and tunable degree-dependent clustering. The effect of clustering on the bond percolation thresholds for networks of this type is examined and contrasted with some recent results in the literature. For very high levels of clustering the percolation threshold in these generalized Trapman networks is increased above the value it takes in a randomly wired (unclustered) network of the same degree distribution. In assortative scale-free networks, where the variance of the degree distribution is infinite, this clustering effect can lead to a nonzero percolation (epidemic) threshold.

View figure in article

Article Text

References (53)

  1. M. E. J. Newman, SIAM Rev. 45, 167 (2003).
  2. S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Rev. Mod. Phys. 80, 1275 (2008).
  3. S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D. U. Hwang, Phys. Rep. 424, 175 (2006).
  4. S. Dorogovtsev and J. Mendes, Evolution of Networks: From Biological Nets to the Internet and WWW (Oxford University Press, Oxford, 2003).
  5. M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. E 64, 026118 (2001).
  6. Z. Burda, J. Jurkiewicz, and A. Krzywicki, Phys. Rev. E 70, 026106 (2004).
  7. G. Bianconi, N. Gulbahce, and A. E. Motter, Phys. Rev. Lett. 100, 118701 (2008).
  8. D. J. Watts and S. H. Strogatz, Nature (London) 393, 440 (1998).
  9. M. Á. Serrano and M. Boguñá, Phys. Rev. E 74, 056114 (2006).
  10. A. Vázquez, R. Pastor-Satorras, and A. Vespignani, Phys. Rev. E 65, 066130 (2002).
  11. M. Á. Serrano and M. Boguñá, Phys. Rev. E 74, 056115 (2006).
  12. D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. Lett. 85, 5468 (2000).
  13. M. E. J. Newman, Phys. Rev. E 68, 026121 (2003).
  14. T. Britton, M. Deijfen, A. N. Lagerås, and M. Lindholm, e-print arXiv:0708.3939.
  15. M. Á. Serrano and M. Boguñá, Phys. Rev. Lett. 97, 088701 (2006).
  16. K. T. D. Eames, Theor. Popul. Biol. 73, 104 (2008).
  17. J. C. Miller, e-print arXiv:0806.2888.
  18. P. Trapman, Ph.D. thesis, Vrije University, Amsterdam, 2006.
  19. P. Trapman, Theor. Popul. Biol. 71, 160 (2007).
  20. S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. E 65, 066122 (2002).
  21. E. Ravasz and A. L. Barabási, Phys. Rev. E 67, 026112 (2003).
  22. J. P. Gleeson, Phys. Rev. E 77, 046117 (2008).
  23. B. Bollobás, in Graph Theory and Combinatorics: Proceeding of Cambridge Combinatorial Conference in Honor of Paul Erdős, edited by B. Bollobás (Academic, New York, 1984), p. 35.
  24. A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, Phys. Rev. E 73, 056101 (2006).
  25. S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt, and E. Shir, Proc. Natl. Acad. Sci. U.S.A. 104, 11150 (2007).
  26. S. N. Dorogovtsev, A. V. Goltsev, and J. F. F. Mendes, Phys. Rev. Lett. 96, 040601 (2006).
  27. M. E. J. Newman, Phys. Rev. Lett. 103, 058701 (2009).
  28. J. P. Gleeson, Phys. Rev. E 80, 036107 (2009).
  29. R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett. 85, 4626 (2000).
  30. R. Pastor-Satorras and A. Vespignani, Phys. Rev. Lett. 86, 3200 (2001).
  31. R. Albert, H. Jeong, and A. L. Barabási, Nature (London) 406, 378 (2000).
  32. M. Boguñá and R. Pastor-Satorras, Phys. Rev. E 66, 047104 (2002).
  33. M. Boguñá, R. Pastor-Satorras, and A. Vespignani, in Proceedings of the XVIII Sitges Conference on Statistical Mechanics of Complex Networks, edited by J. M. Rubi (Springer, Berlin, 2003).
  34. A. V. Goltsev, S. N. Dorogovtsev, and J. F. F. Mendes, Phys. Rev. E 78, 051105 (2008).
  35. A. Vázquez and Y. Moreno, Phys. Rev. E 67, 015101(R) (2003).
  36. C. P. Warren, L. M. Sander, and I. M. Sokolov, Phys. Rev. E 66, 056105 (2002).
  37. V. M. Eguiluz and K. Klemm, Phys. Rev. Lett. 89, 108701 (2002).
  38. An undirected, unweighted network representing the topology of the Western States Power Grid of the United States, http://cdg.columbia.edu/uploads/datasets/power_unweighted
  39. The CAIDA Autonomous System Relationships Dataset, 30 June 2008, http://www.caida.org/data/active/as-relationships; http://as-rank.caida.org/data/2008/as-rel.20080630.a0.01000.txt
  40. M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 98, 404 (2001).
  41. Network of coauthorships between scientists posting preprints on the Condensed Matter E-Print Archive, includes all preprints posted between 1 January 1995 and 31 March 2005, http://www-personal.umich.edu/mejn/netdata/cond-mat-2005.zip
  42. R. Albert, H. Jeong, and A. L. Barabási, Nature (London) 401, 130 (1999).
  43. World Wide Web data for webpages within nd.edu domain, http://www.nd.edu/networks/resources/www/www.dat.gz; www.barabasilab.com/resources/www/www.dat.gz
  44. Internet router-level graph computed from ITDK0304 skitter and iffinder measurements. “CAIDA’s Internet Topology Data Kit #0304.” San Diego Supercomputer Center, University of California, San Diego (2003), www.caida.org/tools/measurement/skitter/router_topology/ itdk0304_rlinks_undirected.gz
  45. X. Guardiola, R. Guimera, A. Arenas, A. Diaz-Guilera, D. Streib, and L. A. N. Amaral, e-print arXiv:cond-mat/0206240.
  46. M. Boguñá, R. Pastor-Satorras, A. Diaz-Guilera, and A. Arenas, Phys. Rev. E 70, 056122 (2004).
  47. Giant component of the network of users of the Pretty-Good-Privacy algorithm for secure information interchange, http://deim.urv.cat/aarenas/data/xarxes/PGP.zip
  48. D. Dhar, P. Shukla, and J. P. Sethna, J. Phys. A 30, 5259 (1997).
  49. J. P. Gleeson and D. J. Cahalane, Phys. Rev. E 75, 056103 (2007).
  50. J. P. Gleeson, Phys. Rev. E 77, 057101 (2008).
  51. H. J. Kim and J. M. Kim, Phys. Rev. E 72, 036109 (2005).
  52. Because all nodes are initially inactive in the cases studied here, we do not require this probability to be conditional on the inactive state of the parent, as used in [22,48,49].
  53. The number Ñ of superindividuals in step (i) of the algorithm of Sec. II was tuned to give N=105 nodes in the individuals graph.

Outline

Information

Phys. Rev. E 80, 046121– Published 26 October, 2009
  • Received 4 December 2008

© 2009 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation