10 - Percolation on complex networks

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 p_c 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.