Book contents
- Frontmatter
- Contents
- 1 Introduction
- PART I RANDOM NETWORK MODELS
- PART II STRUCTURE AND ROBUSTNESS OF COMPLEX NETWORKS
- 6 Distances in scale-free networks: the ultra small world
- 7 Self-similarity in complex networks
- 8 Distances in geographically embedded networks
- 9 The structure of networks: the generating function method
- 10 Percolation on complex networks
- 11 Structure of random directed networks: the bow tie
- 12 Introducing weights: bandwidth allocation and multimedia broadcasting
- PART III NETWORK FUNCTION: DYNAMICS AND APPLICATIONS
- Appendix A Probability theoretical methods
- Appendix B Asymptotics and orders of magnitude
- Appendix C Algorithms for network simulation and investigation
- References
- Index
10 - Percolation on complex networks
from PART II - STRUCTURE AND ROBUSTNESS OF COMPLEX NETWORKS
Published online by Cambridge University Press: 05 August 2013
- Frontmatter
- Contents
- 1 Introduction
- PART I RANDOM NETWORK MODELS
- PART II STRUCTURE AND ROBUSTNESS OF COMPLEX NETWORKS
- 6 Distances in scale-free networks: the ultra small world
- 7 Self-similarity in complex networks
- 8 Distances in geographically embedded networks
- 9 The structure of networks: the generating function method
- 10 Percolation on complex networks
- 11 Structure of random directed networks: the bow tie
- 12 Introducing weights: bandwidth allocation and multimedia broadcasting
- PART III NETWORK FUNCTION: DYNAMICS AND APPLICATIONS
- Appendix A Probability theoretical methods
- Appendix B Asymptotics and orders of magnitude
- Appendix C Algorithms for network simulation and investigation
- References
- Index
Summary
Introduction
It is well known [BH96, SA94] that in grids and other organized lattices, in any dimension larger than one, a percolation phase transition occurs. The usual percolation model assumes that the sites (nodes) or bonds (links) in the lattice are occupied with some probability (or density), p, and unoccupied with probability q = 1 − p. The system is considered percolating if there is a path from one side of the lattice to the other, passing only through occupied links and nodes. When such a path exists, the component or cluster of sites that spans the network from side to side is called the spanning cluster or the infinite cluster The percolation phase transition occurs at some critical density pc that depends on the type and dimensionality of the lattice.
In networks no notion of side exists. However, as will be seen in this chapter, the ideas of percolation theory can still be applied to obtain useful results. The main difference compared to lattices is that the condition for percolation is no longer the spanning property, but rather the property of having a component (cluster) containing O(N) nodes, where N is the total original number of nodes in the network. Such a component, if it exists, is termed the giant component. The condition of the existence of a giant component above the percolation threshold and its absence below the threshold also applies to lattices, and therefore can be considered as more general than the spanning property.
- Type
- Chapter
- Information
- Complex NetworksStructure, Robustness and Function, pp. 97 - 122Publisher: Cambridge University PressPrint publication year: 2010
- 1
- Cited by