Scaling and percolation in the small-world network model

In this paper we study the small-world network model of Watts and Strogatz, which mimics some aspects of the structure of networks of social interacti ons. We argue that there is one nontrivial length-scale in the model, analo gous to the correlation length in other systems, which is well-defined in t he limit of infinite system size and which diverges continuously as the ran domness in the network tends to zero, giving a normal critical point in thi s limit. This length-scale governs the crossover from large- to small-world behavior in the model, as well as the number of vertices in a neighborhood of given radius on the network. We derive the value of the single critical exponent controlling behavior in the critical region and the finite size s caling form for the average vertex-vertex distance on the network, and, usi ng series expansion and Pade approximants, find an approximate analytic for m for the scaling function. We calculate the effective dimension of small-w orld graphs and show that this dimension varies as a function of the length -scale on which it is measured, in a manner reminiscent of multifractals. W e also study the problem of site percolation on small-world networks as a s imple model of disease propagation, and derive an approximate expression fo r the percolation probability at which a giant component of connected verti ces first forms (in epidemiological terms, the point at which an epidemic o ccurs). The typical cluster radius satisfies the expected finite size scali ng form with a cluster size exponent close to that for a random graph. All our analytic results are confirmed by extensive numerical simulations of th e model. [S1063-651X(99)12412-7].