Characterizing the structure of small-world networks.

ABSTRACT

We give exact relations for small-world networks (SWN's) which are independent of the "degree distribution," i.e., the distribution of nearest-neighbor connections. For the original SWN model, we illustrate how these exact relations can be used to obtain approximations for the corresponding basic probability distribution. In the limit of large system sizes and small disorder, we use numerical studies to obtain a functional fit for this distribution. Finally, we obtain the scaling properties for the mean-square displacement of a random walker, which are determined by the scaling behavior of the underlying SWN.