Small world graphs: characterization and alternative constructions

Small world graphs are examples of random graphs which mimick empirically observed features of social networks. We propose an intrinsic definition of small world graphs, based on a probabilistic formulation of scaling properties of graph properties, which does not rely on an underlying lattice nor on any particular construction. Our definition is shown to encompass existing models of small world graphs, proposed by Watts and studied by Barbour & Reinert, which are based on random perturbations of a regular lattice. We also propose alternative constructions of small world graphs which are not based on lattices and study their scaling properties